From 1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Sat, 16 Apr 2005 15:20:36 -0700 Subject: Linux-2.6.12-rc2 Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip! --- fs/befs/ChangeLog | 417 +++++++++++++++++++++ fs/befs/Makefile | 7 + fs/befs/TODO | 14 + fs/befs/attribute.c | 117 ++++++ fs/befs/befs.h | 154 ++++++++ fs/befs/befs_fs_types.h | 213 +++++++++++ fs/befs/btree.c | 788 +++++++++++++++++++++++++++++++++++++++ fs/befs/btree.h | 13 + fs/befs/datastream.c | 528 ++++++++++++++++++++++++++ fs/befs/datastream.h | 19 + fs/befs/debug.c | 283 ++++++++++++++ fs/befs/endian.h | 126 +++++++ fs/befs/inode.c | 53 +++ fs/befs/inode.h | 8 + fs/befs/io.c | 83 +++++ fs/befs/io.h | 9 + fs/befs/linuxvfs.c | 964 ++++++++++++++++++++++++++++++++++++++++++++++++ fs/befs/super.c | 112 ++++++ fs/befs/super.h | 8 + 19 files changed, 3916 insertions(+) create mode 100644 fs/befs/ChangeLog create mode 100644 fs/befs/Makefile create mode 100644 fs/befs/TODO create mode 100644 fs/befs/attribute.c create mode 100644 fs/befs/befs.h create mode 100644 fs/befs/befs_fs_types.h create mode 100644 fs/befs/btree.c create mode 100644 fs/befs/btree.h create mode 100644 fs/befs/datastream.c create mode 100644 fs/befs/datastream.h create mode 100644 fs/befs/debug.c create mode 100644 fs/befs/endian.h create mode 100644 fs/befs/inode.c create mode 100644 fs/befs/inode.h create mode 100644 fs/befs/io.c create mode 100644 fs/befs/io.h create mode 100644 fs/befs/linuxvfs.c create mode 100644 fs/befs/super.c create mode 100644 fs/befs/super.h (limited to 'fs/befs') diff --git a/fs/befs/ChangeLog b/fs/befs/ChangeLog new file mode 100644 index 00000000000..ce8c787916b --- /dev/null +++ b/fs/befs/ChangeLog @@ -0,0 +1,417 @@ +Version 0.92 (2002-03-29) +========== +* Minor cleanup. Ran Lindent on the sources. + +Version 0.92 (2002-03-27) +========== +* Fixed module makefile problem. It was not compiling all the correct + source files! +* Removed duplicated function definition +* Fixed potential null pointer dereference when reporting an error + +Version 0.91 (2002-03-26) +========== +* Oy! Fixed stupid bug that would cause an unresolved symbol error. + Thanks to Laszlo Boszormenyi for pointing this out to me. + +Version 0.9 (2002-03-14) +========== +* Added Sergey S. Kostyliov's patch to eliminate memcpy() overhead + from b+tree operations. Changes the befs_read_datastream() interface. + +* Segregated the functions that interface directly with the linux vfs + interface into their own file called linuxvfs.c. [WD] + +Version 0.64 (2002-02-07) +========== +* Did the string comparision really right this time (btree.c) [WD] + +* Fixed up some places where I assumed that a long int could hold + a pointer value. (btree.c) [WD] + +* Andrew Farnham 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 ] + +* 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 ] + +* Compile warning fix for namei.c. [Sergey S. Kostyliov ] + + +Version 0.62 +========== +* Fixed makefile for module install [WD] + + +Version 0.61 (2002-01-20) +========== +* Made functions in endian.h to do the correct byteswapping, no matter + the arch. [WD] + +* Abbandoned silly checks for a NULL superblock pointer in debug.c. [WD] + +* Misc code cleanups. Also cleanup of this changelog file. [WD] + +* Added byteswapping to all metadata reads from disk. + Uses the functions from endian.h [WD] + +* Remove the typedef of struct super_block to vfs_sb, as it offended + certain peoples' aesthetic sense. [WD] + +* Ditto with the befs_read_block() interface. [WD] + + +Version 0.6 (2001-12-15) +========== +* Cleanup of NLS functions (util.c) [WD] + +* Make directory lookup/read use the NLS if an iocharset is provided. [WD] + +* Fixed stupid bug where specifying the uid or gid mount options as '0' + would result in the filesystem using the on-disk uid and gid. [WD] + +* Added mount option to control debug printing. + The option is, simply enough, 'debug'. + (super.c, debug.c) [WD] + +* Removed notion of btree handle from btree.c. It was unnecessary, as the + linux VFS doesn't allow us to keep any state between calls. Updated + dir.c, namei.c befs_fs.h to account for it. [WD] + +* Improved handleing of overflow nodes when listing directories. + Now works for overflow nodes hanging off of nodes other than the root + node. This is the cleaner solution to Brent Miszalaski's problem. [WD] + +* Added new debug/warning/error print functions in debug.c. + More flexible. Will soon be controllable at mount time + (see TODO). [WD] + +* Rewrote datastream positon lookups. + (datastream.c) [WD] + +* Moved the TODO list to its own file. + + +Version 0.50 (2001-11-13) +========== +* Added workaround for mis-understanding of the nature of the b+trees used + in directories. A cleaner solution will come after I've thought about it + for a while. Thanks to Brent Miszalaski for finding and reporting this bug. + (btree.c) [WD] + +* Minor cleanups + +* Added test for "impossible" condition of empty internal nodes in + seekleaf() in btree.c [WD] + +* Implemented the abstracted read_block() in io.c [WD] + +* Cleaned up the inode validation in inode.c [WD] + +* Anton Altaparmakov figured out (by asking Linus :) ) what was causing the + hanging disk io problem. It turns out you need to have the sync_pages + callback defined in your address_space_ops, even if it just uses the + default linux-supplied implementation. Fixed. Works now. + (file.c) [WD] + +* Anton Altaparmakov and Christoph Hellwig alerted me to the fact that + filesystem code should be using GFP_NOFS instead of GFP_KERNEL as the + priority parameter to kmalloc(). Fixed. + (datastream.c, btree.c super.c inode.c) [WD] + +* Anton also told me that the blocksize is not allowed to be larger than + the page size in linux, which is 4k i386. Oops. Added a test for + (blocksize > PAGE_SIZE), and refuse to mount in that case. What this + practicaly means is that 8k blocksize volumes won't work without a major + restructuring of the driver (or an alpha or other 64bit hardware). [WD] + +* Cleaned up the befs_count_blocks() function. Much smarter now. + And somewhat smaller too. [WD] + +* Made inode allocations use a slab cache + (super.c inode.c) [WD] + +* Moved the freeing of the private inode section from put_inode() to + clear_inode(). This fixes a potential free twice type bug. Put_inode() + can be called multiple times for each inode struct. [WD] + +* Converted all non vfs-callback functions to use befs_sb_info as the + superblock type, rather than struct super_block. This is for + portablity. [WD] + +* Fixed a couple of compile warnings due to use of malloc.h, when slab.h + is the new way. (inode.c, super.c) [WD] + +* Fixed erronous includes of linux/befs_fs_i.h and linux/befs_fs_sb.h + in inode.c [WD] + +Version 0.45 (2001-10-29) +========== +* Added functions to get the private superblock and inode structures from + their enclosing public structures. Switched all references to the + private portions to use them. (many files) [WD] + +* Made read_super and read_inode allocate the private portions of those + structures into the generic pointer fields of the public structures + with kmalloc(). put_super and put_inode free them. This allows us not + to have to touch the definitions of the public structures in + include/linux/fs.h. Also, befs_inode_info is huge (becuase of the + symlink string). (super.c, inode.c, befs_fs.h) [WD] + +* Fixed a thinko that was corrupting file reads after the first block_run + is done being read. (datastream.c) [WD] + +* Removed fsync() hooks, since a read-only filesystem doesn't need them. + [Christoph Hellwig]. + +* Fixed befs_readlink() (symlink.c) [Christoph Hellwig]. + +* Removed all the Read-Write stuff. I'll redo it when it is time to add + write support (various files) [WD]. + +* Removed prototypes for functions who's definitions have been removed + (befs_fs.h) [WD]. + + +Version 0.4 (2001-10-28) +========== +* Made it an option to use the old non-pagecache befs_file_read() for + testing purposes. (fs/Config.in) + +* Fixed unused variable warnings when compiling without debugging. + +* Fixed a bug where the inode and super_block didn't get their blockbits + fields set (inode.c and super.c). + +* Release patch version 11. AKA befs-driver version 0.4. + +* Thats right. New versioning scheme. + I've done some serious testing on it now (on my box anyhow), and it + seems stable and not outragously slow. Existing features are more-or-less + correct (see TODO list). But it isn't 1.0 yet. I think 0.4 gives me some + headroom before the big 1.0. + + +2001-10-26 +========== +* Fixed date format in this file. Was I smoking crack? + +* Removed old datastream code from file.c, since it is nolonger used. + +* Generic_read_file() is now used to read regular file data. + It doesn't chew up the buffer cache (it does page io instead), and seems + to be about as fast (even though it has to look up each file block + indivdualy). And it knows about doing readahead, which is a major plus. + So it does i/o in much larger chunks. It is the correct linux way. It + uses befs_get_block() by way of befs_readpage() to find the disk offsets + of blocks, which in turn calls befs_fpos2brun() in datastream.c to do + the hard work of finding the disk block number. + +* Changed method of checking for a dirty filesystem in befs_read_super + (super.c). Now we check to see if log_start and log_end differ. If so, + the journal needs to be replayed, and the filesystem cannot be mounted. + +* Fixed an extra instance of MOD_DEC_USE_COUNT in super.c + +* Fixed a problem with reading the superblock on devices with large sector + sizes (such as cdroms) on linux 2.4.10 and up. + +2001-10-24 +========== +* Fix nasty bug in converting block numbers to struct befs_inode_addr. + Subtle, because the old version was only sometimes wrong. + Probably responsible for lots of problems. (inode.c) + +* Fix bug with reading an empty directory. (btree.c and dir.c) + +* This one looks good. Release patch version 10 + +2001-10-23 +========== +* Added btree searching function. + +* Use befs_btree_find in befs_lookup (namei.c) + +* Additional comments in btree.c + +2001-10-22 +========== +* Added B+tree reading functions (in btree.c). + Made befs_readdir() use them them instead of the cruft in index.c. + +2001-09-11 +========== +* Converted befs_read_file() to use the new datastream code. + +* Finally updated the README file. + +* Added many comments. + +* Posted version 6 + +* Removed byte-order conversion code. + I have no intention of supporting it, and it was very ugly. + Flow control with #ifdef (ugh). Maybe I'll redo it once + native byteorder works 100%. + +2001-09-10 +========== +* Finished implementing read_datastream() + +* made befs_read_brun() more general + Supports an offset to start at and a max bytes to read + Added a wrapper function to give the old call + +2001-09-30 +========== +* Discovered that the datastream handleing code in file.c is quite deficient + in several respects. For one thing, it doesn't deal with indirect blocks + +* Rewrote datastream handleing. + +* Created io.c, for io related functions. + Previously, the befs_bread() funtions lived in file.c + Created the befs_read_brun() function. + + +2001-09-07 +========== +* Made a function to actually count the number of fs blocks used by a file. + And helper functions. + (fs/befs/inode.c) + +2001-09-05 +========== +* Fixed a misunderstanding of the inode fields. + This fixed the problmem with wrong file sizes from du and others. + The i_blocks field of the inode struct is not the number of blocks for the + inode, it is the number of blocks for the file. Also, i_blksize is not + necessarily the size of the inode, although in practice it works out. + Changed to blocksize of filesystem. + (fs/befs/inode.c) + +* Permanently removed code that had been provisionally ifdefed out of befs_fs.h + +* Since we don't support access time, make that field zero, instead of + copying m_time. + (fs/befs/inode.c) + +* Added sanity check for inode reading + Make sure inode we got was the one we asked for. + (fs/befs/inode.c) + +* Code cleanup + Local pointers to commonly used structures in inode.c. + Got rid of abominations befs_iaddr2inode() and befs_inode2ino(). + Replaced with single function iaddr2blockno(). + (fs/befs/super.c) (fs/befs/inode.c) + +2001-09-01 +========== +* Fixed the problem with statfs where it would always claim the disk was + half full, due to improper understanding of the statfs fields. + (fs/befs/super.c) + +* Posted verion 4 of the patch + +2001-09-01 +========== +* Changed the macros in befs_fs.h to inline functions. + More readable. Typesafe. Better + (include/linux/befs_fs.h) + +* Moved type definitions from befs_fs.h to a new file, befs_fs_types.h + Because befs_fs_i.h and befs_fs_sb.h were including befs_fs.h for the + typedefs, and they are inlcuded in , which has definitions + that I want the inline functions in befs_fs.h to be able to see. Nasty + circularity. + (include/linux/befs_fs.h) + +2001-08-30 +========== +* Cleaned up some wording. + +* Added additional consitency checks on mount + Check block_size agrees with block_shift + Check flags == BEFS_CLEAN + (fs/befs/super.c) + +* Tell the kernel to only mount befs read-only. + By setting the MS_RDONLY flag in befs_read_super(). + Not that it was possible to write before. But now the kernel won't even try. + (fs/befs/super.c) + +* Got rid of kernel warning on mount. + The kernel doesn't like it if you call set_blocksize() on a device when + you have some of its blocks open. Moved the second set_blocksize() to the + very end of befs_read_super(), after we are done with the disk superblock. + (fs/befs/super.c) + +* Fixed wrong number of args bug in befs_dump_inode + (fs/befs/debug.c) + +* Solved lots of type mismatches in kprint()s + (everwhere) + +2001-08-27 +========== +* Cleaned up the fs/Config.in entries a bit, now slightly more descriptive. + +* BeFS depends on NLS, so I made activating BeFS enable the NLS questions + (fs/nls/Config.in) + +* Added Configure.help entries for CONFIG_BEFS_FS and CONFIG_DEBUG_BEFS + (Documentation/Configure.help) + +2001-08-?? +========== +* Removed superblock locking calls in befs_read_super(). In 2.4, the VFS + hands us a super_block struct that is already locked. + +2001-08-13 +========== +* Will Dyson is now attempting to maintain this module + Makoto Kato is original author.Daniel Berlin + also did some work on it (fixing it up for the later 2.3.x kernels, IIRC). + +* Fixed compile errors on 2.4.1 kernel (WD) + Resolve rejected patches + Accomodate changed NLS interface (util.h) + Needed to include in most files + Makefile changes + fs/Config.in changes + +* Tried to niceify the code using the ext2 fs as a guide + Declare befs_fs_type using the DECLARE_FSTYPE_DEV() macro + +* Made it a configure option to turn on debugging (fs/Config.in) + +* Compiles on 2.4.7 diff --git a/fs/befs/Makefile b/fs/befs/Makefile new file mode 100644 index 00000000000..2f370bd7a50 --- /dev/null +++ b/fs/befs/Makefile @@ -0,0 +1,7 @@ +# +# Makefile for the linux BeOS filesystem routines. +# + +obj-$(CONFIG_BEFS_FS) += befs.o + +befs-objs := datastream.o btree.o super.o inode.o debug.o io.o linuxvfs.o diff --git a/fs/befs/TODO b/fs/befs/TODO new file mode 100644 index 00000000000..3250921aa2e --- /dev/null +++ b/fs/befs/TODO @@ -0,0 +1,14 @@ +TODO +========== + +* Convert comments to the Kernel-Doc format. + +* Befs_fs.h has gotten big and messy. No reason not to break it up into + smaller peices. + +* See if Alexander Viro's option parser made it into the kernel tree. + Use that if we can. (include/linux/parser.h) + +* See if we really need separate types for on-disk and in-memory + representations of the superblock and inode. + diff --git a/fs/befs/attribute.c b/fs/befs/attribute.c new file mode 100644 index 00000000000..e329d727053 --- /dev/null +++ b/fs/befs/attribute.c @@ -0,0 +1,117 @@ +/* + * linux/fs/befs/attribute.c + * + * Copyright (C) 2002 Will Dyson + * + * Many thanks to Dominic Giampaolo, author of "Practical File System + * Design with the Be File System", for such a helpful book. + * + */ + +#include +#include +#include + +#include "befs.h" +#include "endian.h" + +#define SD_DATA(sd)\ + (void*)((char*)sd + sizeof(*sd) + (sd->name_size - sizeof(sd->name))) + +#define SD_NEXT(sd)\ + (befs_small_data*)((char*)sd + sizeof(*sd) + (sd->name_size - \ + sizeof(sd->name) + sd->data_size)) + +int +list_small_data(struct super_block *sb, befs_inode * inode, filldir_t filldir); + +befs_small_data * +find_small_data(struct super_block *sb, befs_inode * inode, + const char *name); +int +read_small_data(struct super_block *sb, befs_inode * inode, + befs_small_data * sdata, void *buf, size_t bufsize); + +/** + * + * + * + * + * + */ +befs_small_data * +find_small_data(struct super_block *sb, befs_inode * inode, const char *name) +{ + befs_small_data *sdata = inode->small_data; + + while (sdata->type != 0) { + if (strcmp(name, sdata->name) != 0) { + return sdata; + } + sdata = SD_NEXT(sdata); + } + return NULL; +} + +/** + * + * + * + * + * + */ +int +read_small_data(struct super_block *sb, befs_inode * inode, + const char *name, void *buf, size_t bufsize) +{ + befs_small_data *sdata; + + sdata = find_small_data(sb, inode, name); + if (sdata == NULL) + return BEFS_ERR; + else if (sdata->data_size > bufsize) + return BEFS_ERR; + + memcpy(buf, SD_DATA(sdata), sdata->data_size); + + return BEFS_OK; +} + +/** + * + * + * + * + * + */ +int +list_small_data(struct super_block *sb, befs_inode * inode) +{ + +} + +/** + * + * + * + * + * + */ +int +list_attr(struct super_block *sb, befs_inode * inode) +{ + +} + +/** + * + * + * + * + * + */ +int +read_attr(struct super_block *sb, befs_inode * inode) +{ + +} diff --git a/fs/befs/befs.h b/fs/befs/befs.h new file mode 100644 index 00000000000..057a2c3d73b --- /dev/null +++ b/fs/befs/befs.h @@ -0,0 +1,154 @@ +/* + * befs.h + * + * Copyright (C) 2001-2002 Will Dyson + * Copyright (C) 1999 Makoto Kato (m_kato@ga2.so-net.ne.jp) + */ + +#ifndef _LINUX_BEFS_H +#define _LINUX_BEFS_H + +#include "befs_fs_types.h" + +/* used in debug.c */ +#define BEFS_VERSION "0.9.3" + + +typedef u64 befs_blocknr_t; +/* + * BeFS in memory structures + */ + +typedef struct befs_mount_options { + gid_t gid; + uid_t uid; + int use_gid; + int use_uid; + int debug; + char *iocharset; +} befs_mount_options; + +typedef struct befs_sb_info { + u32 magic1; + u32 block_size; + u32 block_shift; + int byte_order; + befs_off_t num_blocks; + befs_off_t used_blocks; + u32 inode_size; + u32 magic2; + + /* Allocation group information */ + u32 blocks_per_ag; + u32 ag_shift; + u32 num_ags; + + /* jornal log entry */ + befs_block_run log_blocks; + befs_off_t log_start; + befs_off_t log_end; + + befs_inode_addr root_dir; + befs_inode_addr indices; + u32 magic3; + + befs_mount_options mount_opts; + struct nls_table *nls; + +} befs_sb_info; + +typedef struct befs_inode_info { + u32 i_flags; + u32 i_type; + + befs_inode_addr i_inode_num; + befs_inode_addr i_parent; + befs_inode_addr i_attribute; + + union { + befs_data_stream ds; + char symlink[BEFS_SYMLINK_LEN]; + } i_data; + + struct inode vfs_inode; + +} befs_inode_info; + +enum befs_err { + BEFS_OK, + BEFS_ERR, + BEFS_BAD_INODE, + BEFS_BT_END, + BEFS_BT_EMPTY, + BEFS_BT_MATCH, + BEFS_BT_PARMATCH, + BEFS_BT_NOT_FOUND +}; + + +/****************************/ +/* debug.c */ +void befs_error(const struct super_block *sb, const char *fmt, ...); +void befs_warning(const struct super_block *sb, const char *fmt, ...); +void befs_debug(const struct super_block *sb, const char *fmt, ...); + +void befs_dump_super_block(const struct super_block *sb, befs_super_block *); +void befs_dump_inode(const struct super_block *sb, befs_inode *); +void befs_dump_index_entry(const struct super_block *sb, befs_btree_super *); +void befs_dump_index_node(const struct super_block *sb, befs_btree_nodehead *); +/****************************/ + + +/* Gets a pointer to the private portion of the super_block + * structure from the public part + */ +static inline befs_sb_info * +BEFS_SB(const struct super_block *super) +{ + return (befs_sb_info *) super->s_fs_info; +} + +static inline befs_inode_info * +BEFS_I(const struct inode *inode) +{ + return list_entry(inode, struct befs_inode_info, vfs_inode); +} + +static inline befs_blocknr_t +iaddr2blockno(struct super_block *sb, befs_inode_addr * iaddr) +{ + return ((iaddr->allocation_group << BEFS_SB(sb)->ag_shift) + + iaddr->start); +} + +static inline befs_inode_addr +blockno2iaddr(struct super_block *sb, befs_blocknr_t blockno) +{ + befs_inode_addr iaddr; + iaddr.allocation_group = blockno >> BEFS_SB(sb)->ag_shift; + iaddr.start = + blockno - (iaddr.allocation_group << BEFS_SB(sb)->ag_shift); + iaddr.len = 1; + + return iaddr; +} + +static inline unsigned int +befs_iaddrs_per_block(struct super_block *sb) +{ + return BEFS_SB(sb)->block_size / sizeof (befs_inode_addr); +} + +static inline int +befs_iaddr_is_empty(befs_inode_addr * iaddr) +{ + return (!iaddr->allocation_group) && (!iaddr->start) && (!iaddr->len); +} + +static inline size_t +befs_brun_size(struct super_block *sb, befs_block_run run) +{ + return BEFS_SB(sb)->block_size * run.len; +} + +#endif /* _LINUX_BEFS_H */ diff --git a/fs/befs/befs_fs_types.h b/fs/befs/befs_fs_types.h new file mode 100644 index 00000000000..9095518e918 --- /dev/null +++ b/fs/befs/befs_fs_types.h @@ -0,0 +1,213 @@ +/* + * include/linux/befs_fs_types.h + * + * Copyright (C) 2001 Will Dyson (will@cs.earlham.edu) + * + * + * + * from linux/include/linux/befs_fs.h + * + * Copyright (C) 1999 Makoto Kato (m_kato@ga2.so-net.ne.jp) + * + */ + +#ifndef _LINUX_BEFS_FS_TYPES +#define _LINUX_BEFS_FS_TYPES + +#ifdef __KERNEL__ +#include +#endif /*__KERNEL__*/ + +#define PACKED __attribute__ ((__packed__)) + +/* + * Max name lengths of BFS + */ + +#define BEFS_NAME_LEN 255 + +#define BEFS_SYMLINK_LEN 144 +#define BEFS_NUM_DIRECT_BLOCKS 12 +#define B_OS_NAME_LENGTH 32 + +/* The datastream blocks mapped by the double-indirect + * block are always 4 fs blocks long. + * This eliminates the need for linear searches among + * the potentially huge number of indirect blocks + * + * Err. Should that be 4 fs blocks or 4k??? + * It matters on large blocksize volumes + */ +#define BEFS_DBLINDIR_BRUN_LEN 4 + +/* + * Flags of superblock + */ + +enum super_flags { + BEFS_BYTESEX_BE, + BEFS_BYTESEX_LE, + BEFS_CLEAN = 0x434c454e, + BEFS_DIRTY = 0x44495254, + BEFS_SUPER_MAGIC1 = 0x42465331, /* BFS1 */ + BEFS_SUPER_MAGIC2 = 0xdd121031, + BEFS_SUPER_MAGIC3 = 0x15b6830e, +}; + +#define BEFS_BYTEORDER_NATIVE 0x42494745 + +#define BEFS_SUPER_MAGIC BEFS_SUPER_MAGIC1 + +/* + * Flags of inode + */ + +#define BEFS_INODE_MAGIC1 0x3bbe0ad9 + +enum inode_flags { + BEFS_INODE_IN_USE = 0x00000001, + BEFS_ATTR_INODE = 0x00000004, + BEFS_INODE_LOGGED = 0x00000008, + BEFS_INODE_DELETED = 0x00000010, + BEFS_LONG_SYMLINK = 0x00000040, + BEFS_PERMANENT_FLAG = 0x0000ffff, + BEFS_INODE_NO_CREATE = 0x00010000, + BEFS_INODE_WAS_WRITTEN = 0x00020000, + BEFS_NO_TRANSACTION = 0x00040000, +}; +/* + * On-Disk datastructures of BeFS + */ + +typedef u64 befs_off_t; +typedef u64 befs_time_t; +typedef void befs_binode_etc; + +/* Block runs */ +typedef struct { + u32 allocation_group; + u16 start; + u16 len; +} PACKED befs_block_run; + +typedef befs_block_run befs_inode_addr; + +/* + * The Superblock Structure + */ +typedef struct { + char name[B_OS_NAME_LENGTH]; + u32 magic1; + u32 fs_byte_order; + + u32 block_size; + u32 block_shift; + + befs_off_t num_blocks; + befs_off_t used_blocks; + + u32 inode_size; + + u32 magic2; + u32 blocks_per_ag; + u32 ag_shift; + u32 num_ags; + + u32 flags; + + befs_block_run log_blocks; + befs_off_t log_start; + befs_off_t log_end; + + u32 magic3; + befs_inode_addr root_dir; + befs_inode_addr indices; + +} PACKED befs_super_block; + +/* + * Note: the indirect and dbl_indir block_runs may + * be longer than one block! + */ +typedef struct { + befs_block_run direct[BEFS_NUM_DIRECT_BLOCKS]; + befs_off_t max_direct_range; + befs_block_run indirect; + befs_off_t max_indirect_range; + befs_block_run double_indirect; + befs_off_t max_double_indirect_range; + befs_off_t size; +} PACKED befs_data_stream; + +/* Attribute */ +typedef struct { + u32 type; + u16 name_size; + u16 data_size; + char name[1]; +} PACKED befs_small_data; + +/* Inode structure */ +typedef struct { + u32 magic1; + befs_inode_addr inode_num; + u32 uid; + u32 gid; + u32 mode; + u32 flags; + befs_time_t create_time; + befs_time_t last_modified_time; + befs_inode_addr parent; + befs_inode_addr attributes; + u32 type; + + u32 inode_size; + u32 etc; /* not use */ + + union { + befs_data_stream datastream; + char symlink[BEFS_SYMLINK_LEN]; + } data; + + u32 pad[4]; /* not use */ + befs_small_data small_data[1]; +} PACKED befs_inode; + +/* + * B+tree superblock + */ + +#define BEFS_BTREE_MAGIC 0x69f6c2e8 + +enum btree_types { + BTREE_STRING_TYPE = 0, + BTREE_INT32_TYPE = 1, + BTREE_UINT32_TYPE = 2, + BTREE_INT64_TYPE = 3, + BTREE_UINT64_TYPE = 4, + BTREE_FLOAT_TYPE = 5, + BTREE_DOUBLE_TYPE = 6 +}; + +typedef struct { + u32 magic; + u32 node_size; + u32 max_depth; + u32 data_type; + befs_off_t root_node_ptr; + befs_off_t free_node_ptr; + befs_off_t max_size; +} PACKED befs_btree_super; + +/* + * Header stucture of each btree node + */ +typedef struct { + befs_off_t left; + befs_off_t right; + befs_off_t overflow; + u16 all_key_count; + u16 all_key_length; +} PACKED befs_btree_nodehead; + +#endif /* _LINUX_BEFS_FS_TYPES */ diff --git a/fs/befs/btree.c b/fs/befs/btree.c new file mode 100644 index 00000000000..76e21979940 --- /dev/null +++ b/fs/befs/btree.c @@ -0,0 +1,788 @@ +/* + * linux/fs/befs/btree.c + * + * Copyright (C) 2001-2002 Will Dyson + * + * Licensed under the GNU GPL. See the file COPYING for details. + * + * 2002-02-05: Sergey S. Kostyliov added binary search withing + * btree nodes. + * + * Many thanks to: + * + * Dominic Giampaolo, author of "Practical File System + * Design with the Be File System", for such a helpful book. + * + * Marcus J. Ranum, author of the b+tree package in + * comp.sources.misc volume 10. This code is not copied from that + * work, but it is partially based on it. + * + * Makoto Kato, author of the original BeFS for linux filesystem + * driver. + */ + +#include +#include +#include +#include +#include + +#include "befs.h" +#include "btree.h" +#include "datastream.h" +#include "endian.h" + +/* + * The btree functions in this file are built on top of the + * datastream.c interface, which is in turn built on top of the + * io.c interface. + */ + +/* Befs B+tree structure: + * + * The first thing in the tree is the tree superblock. It tells you + * all kinds of useful things about the tree, like where the rootnode + * is located, and the size of the nodes (always 1024 with current version + * of BeOS). + * + * The rest of the tree consists of a series of nodes. Nodes contain a header + * (struct befs_btree_nodehead), the packed key data, an array of shorts + * containing the ending offsets for each of the keys, and an array of + * befs_off_t values. In interior nodes, the keys are the ending keys for + * the childnode they point to, and the values are offsets into the + * datastream containing the tree. + */ + +/* Note: + * + * The book states 2 confusing things about befs b+trees. First, + * it states that the overflow field of node headers is used by internal nodes + * to point to another node that "effectively continues this one". Here is what + * I believe that means. Each key in internal nodes points to another node that + * contains key values less than itself. Inspection reveals that the last key + * in the internal node is not the last key in the index. Keys that are + * greater than the last key in the internal node go into the overflow node. + * I imagine there is a performance reason for this. + * + * Second, it states that the header of a btree node is sufficient to + * distinguish internal nodes from leaf nodes. Without saying exactly how. + * After figuring out the first, it becomes obvious that internal nodes have + * overflow nodes and leafnodes do not. + */ + +/* + * 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 + */ +typedef struct { + befs_btree_nodehead head; /* head of node converted to cpu byteorder */ + struct buffer_head *bh; + befs_btree_nodehead *od_node; /* on disk node */ +} befs_btree_node; + +/* local constants */ +static const befs_off_t befs_bt_inval = 0xffffffffffffffffULL; + +/* local functions */ +static int befs_btree_seekleaf(struct super_block *sb, befs_data_stream * ds, + befs_btree_super * bt_super, + befs_btree_node * this_node, + befs_off_t * node_off); + +static int befs_bt_read_super(struct super_block *sb, befs_data_stream * ds, + befs_btree_super * sup); + +static int befs_bt_read_node(struct super_block *sb, befs_data_stream * ds, + befs_btree_node * node, befs_off_t node_off); + +static int befs_leafnode(befs_btree_node * node); + +static u16 *befs_bt_keylen_index(befs_btree_node * node); + +static befs_off_t *befs_bt_valarray(befs_btree_node * node); + +static char *befs_bt_keydata(befs_btree_node * node); + +static int befs_find_key(struct super_block *sb, befs_btree_node * node, + const char *findkey, befs_off_t * value); + +static char *befs_bt_get_key(struct super_block *sb, 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. + * + * On success, returns BEFS_OK and *@sup contains the btree superblock, + * in cpu byte order. + * + * On failure, BEFS_ERR is returned. + */ +static int +befs_bt_read_super(struct super_block *sb, befs_data_stream * ds, + befs_btree_super * sup) +{ + struct buffer_head *bh = NULL; + befs_btree_super *od_sup = NULL; + + befs_debug(sb, "---> befs_btree_read_super()"); + + bh = befs_read_datastream(sb, ds, 0, NULL); + + if (!bh) { + befs_error(sb, "Couldn't read index header."); + goto error; + } + od_sup = (befs_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); + sup->free_node_ptr = fs64_to_cpu(sb, od_sup->free_node_ptr); + sup->max_size = fs64_to_cpu(sb, od_sup->max_size); + + brelse(bh); + if (sup->magic != BEFS_BTREE_MAGIC) { + befs_error(sb, "Index header has bad magic."); + goto error; + } + + befs_debug(sb, "<--- befs_btree_read_super()"); + return BEFS_OK; + + error: + befs_debug(sb, "<--- befs_btree_read_super() ERROR"); + 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 called 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, befs_data_stream * ds, + befs_btree_node * node, befs_off_t node_off) +{ + uint off = 0; + + befs_debug(sb, "---> befs_bt_read_node()"); + + if (node->bh) + brelse(node->bh); + + node->bh = befs_read_datastream(sb, ds, node_off, &off); + if (!node->bh) { + befs_error(sb, "befs_bt_read_node() failed to read " + "node at %Lu", node_off); + befs_debug(sb, "<--- befs_bt_read_node() ERROR"); + + 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, "<--- befs_btree_read_node()"); + 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 sucess, 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 + * actuall value stored with the key. + */ +int +befs_btree_find(struct super_block *sb, befs_data_stream * ds, + const char *key, befs_off_t * value) +{ + befs_btree_node *this_node = NULL; + befs_btree_super bt_super; + befs_off_t node_off; + int res; + + befs_debug(sb, "---> befs_btree_find() Key: %s", 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 = (befs_btree_node *) kmalloc(sizeof (befs_btree_node), + GFP_NOFS); + if (!this_node) { + befs_error(sb, "befs_btree_find() failed to allocate %u " + "bytes of memory", sizeof (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 %Lu", node_off); + goto error_alloc; + } + + while (!befs_leafnode(this_node)) { + res = befs_find_key(sb, this_node, key, &node_off); + if (res == BEFS_BT_NOT_FOUND) + node_off = this_node->head.overflow; + /* if no match, go to overflow node */ + if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) { + befs_error(sb, "befs_btree_find() failed to read " + "node at %Lu", node_off); + goto error_alloc; + } + } + + /* at the correct leaf node now */ + + res = befs_find_key(sb, this_node, key, value); + + brelse(this_node->bh); + kfree(this_node); + + if (res != BEFS_BT_MATCH) { + befs_debug(sb, "<--- befs_btree_find() Key %s not found", key); + *value = 0; + return BEFS_BT_NOT_FOUND; + } + befs_debug(sb, "<--- befs_btree_find() Found key %s, value %Lu", + key, *value); + return BEFS_OK; + + error_alloc: + kfree(this_node); + error: + *value = 0; + befs_debug(sb, "<--- befs_btree_find() ERROR"); + return BEFS_ERR; +} + +/** + * befs_find_key - Search for a key within a node + * @sb: Filesystem superblock + * @node: Node to find the key within + * @key: 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 no exact match, finds first key in node that is greater + * (alphabetically) than the search key and returns BEFS_BT_PARMATCH + * (for partial match, I guess). Can you think of something better to + * call it? + * + * If no key was a match or greater than the search key, return + * BEFS_BT_NOT_FOUND. + * + * Use binary search instead of a linear. + */ +static int +befs_find_key(struct super_block *sb, befs_btree_node * node, + const char *findkey, befs_off_t * value) +{ + int first, last, mid; + int eq; + u16 keylen; + int findkey_len; + char *thiskey; + befs_off_t *valarray; + + befs_debug(sb, "---> befs_find_key() %s", findkey); + + *value = 0; + + findkey_len = strlen(findkey); + + /* if node can not contain key, just skeep 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, "<--- befs_find_key() %s not found", findkey); + return BEFS_BT_NOT_FOUND; + } + + 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, "<--- befs_find_key() found %s at %d", + thiskey, mid); + + *value = fs64_to_cpu(sb, valarray[mid]); + return BEFS_BT_MATCH; + } + if (eq > 0) + last = mid - 1; + else + first = mid + 1; + } + if (eq < 0) + *value = fs64_to_cpu(sb, valarray[mid + 1]); + else + *value = fs64_to_cpu(sb, valarray[mid]); + befs_debug(sb, "<--- befs_find_key() found %s at %d", thiskey, mid); + return BEFS_BT_PARMATCH; +} + +/** + * 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 + * + * Heres 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 charecters 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, befs_data_stream * ds, + loff_t key_no, size_t bufsize, char *keybuf, size_t * keysize, + befs_off_t * value) +{ + befs_btree_node *this_node; + befs_btree_super bt_super; + befs_off_t node_off = 0; + int cur_key; + befs_off_t *valarray; + char *keystart; + u16 keylen; + int res; + + uint key_sum = 0; + + befs_debug(sb, "---> befs_btree_read()"); + + if (befs_bt_read_super(sb, ds, &bt_super) != BEFS_OK) { + befs_error(sb, + "befs_btree_read() failed to read index superblock"); + goto error; + } + + if ((this_node = (befs_btree_node *) + kmalloc(sizeof (befs_btree_node), GFP_NOFS)) == NULL) { + befs_error(sb, "befs_btree_read() failed to allocate %u " + "bytes of memory", sizeof (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, "<--- befs_btree_read() Tree is EMPTY"); + 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, + "<--- befs_btree_read() END of keys at %Lu", + 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, "befs_btree_read() failed to read " + "node at %Lu", 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 [%Lu,%d]: keysize %d", node_off, cur_key, keylen); + + if (bufsize < keylen + 1) { + befs_error(sb, "befs_btree_read() keybuf too small (%u) " + "for key of size %d", bufsize, keylen); + brelse(this_node->bh); + goto error_alloc; + }; + + strncpy(keybuf, keystart, keylen); + *value = fs64_to_cpu(sb, valarray[cur_key]); + *keysize = keylen; + keybuf[keylen] = '\0'; + + befs_debug(sb, "Read [%Lu,%d]: Key \"%.*s\", Value %Lu", node_off, + cur_key, keylen, keybuf, *value); + + brelse(this_node->bh); + kfree(this_node); + + befs_debug(sb, "<--- befs_btree_read()"); + + return BEFS_OK; + + error_alloc: + kfree(this_node); + + error: + *keysize = 0; + *value = 0; + befs_debug(sb, "<--- befs_btree_read() ERROR"); + 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, befs_data_stream * ds, + befs_btree_super * bt_super, befs_btree_node * this_node, + befs_off_t * node_off) +{ + + befs_debug(sb, "---> befs_btree_seekleaf()"); + + if (befs_bt_read_node(sb, ds, this_node, *node_off) != BEFS_OK) { + befs_error(sb, "befs_btree_seekleaf() failed to read " + "node at %Lu", *node_off); + goto error; + } + befs_debug(sb, "Seekleaf to root node %Lu", *node_off); + + if (this_node->head.all_key_count == 0 && befs_leafnode(this_node)) { + befs_debug(sb, "<--- befs_btree_seekleaf() Tree is EMPTY"); + return BEFS_BT_EMPTY; + } + + while (!befs_leafnode(this_node)) { + + if (this_node->head.all_key_count == 0) { + befs_debug(sb, "befs_btree_seekleaf() encountered " + "an empty interior node: %Lu. Using Overflow " + "node: %Lu", *node_off, + this_node->head.overflow); + *node_off = this_node->head.overflow; + } else { + befs_off_t *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, "befs_btree_seekleaf() failed to read " + "node at %Lu", *node_off); + goto error; + } + + befs_debug(sb, "Seekleaf to child node %Lu", *node_off); + } + befs_debug(sb, "Node %Lu is a leaf node", *node_off); + + return BEFS_OK; + + error: + befs_debug(sb, "<--- befs_btree_seekleaf() ERROR"); + 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(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 u16 * +befs_bt_keylen_index(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 (u16 *) ((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 befs_off_t * +befs_bt_valarray(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 (u16); + + return (befs_off_t *) (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(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, befs_btree_node * node, + int index, u16 * keylen) +{ + int prev_key_end; + char *keystart; + u16 *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 + * @kelen2: 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 00000000000..92e781e5f30 --- /dev/null +++ b/fs/befs/btree.h @@ -0,0 +1,13 @@ +/* + * btree.h + * + */ + + +int befs_btree_find(struct super_block *sb, befs_data_stream * ds, + const char *key, befs_off_t * value); + +int befs_btree_read(struct super_block *sb, 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 00000000000..785f6b2d5d1 --- /dev/null +++ b/fs/befs/datastream.c @@ -0,0 +1,528 @@ +/* + * linux/fs/befs/datastream.c + * + * Copyright (C) 2001 Will Dyson + * + * Based on portions of file.c by Makoto Kato + * + * Many thanks to Dominic Giampaolo, author of "Practical File System + * Design with the Be File System", for such a helpful book. + * + */ + +#include +#include +#include +#include + +#include "befs.h" +#include "datastream.h" +#include "io.h" +#include "endian.h" + +const befs_inode_addr BAD_IADDR = { 0, 0, 0 }; + +static int befs_find_brun_direct(struct super_block *sb, + befs_data_stream * data, + befs_blocknr_t blockno, befs_block_run * run); + +static int befs_find_brun_indirect(struct super_block *sb, + befs_data_stream * data, + befs_blocknr_t blockno, + befs_block_run * run); + +static int befs_find_brun_dblindirect(struct super_block *sb, + 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: datastrem 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, befs_data_stream * ds, + befs_off_t pos, uint * off) +{ + struct buffer_head *bh = NULL; + befs_block_run run; + befs_blocknr_t block; /* block coresponding to pos */ + + befs_debug(sb, "---> befs_read_datastream() %Lu", 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", + block); + befs_debug(sb, "<--- befs_read_datastream() ERROR"); + return NULL; + } + bh = befs_bread_iaddr(sb, run); + if (!bh) { + befs_error(sb, "BeFS: Error reading block %lu from datastream", + block); + return NULL; + } + + befs_debug(sb, "<--- befs_read_datastream() read data, starting at %Lu", + pos); + + return bh; +} + +/* + * 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. + * + * 2001-11-15 Will Dyson + */ +int +befs_fblock2brun(struct super_block *sb, 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", fblock); + err = BEFS_ERR; + } + return err; +} + +/** + * befs_read_lsmylink - read long symlink from datastream. + * @sb: Filesystem superblock + * @ds: Datastrem to read from + * @buf: Buffer in wich 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, befs_data_stream * ds, void *buff, + befs_off_t len) +{ + befs_off_t bytes_read = 0; /* bytes readed */ + u16 plen; + struct buffer_head *bh = NULL; + befs_debug(sb, "---> befs_read_lsymlink() length: %Lu", 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 %Lu", bytes_read); + befs_debug(sb, "<--- befs_read_lsymlink() ERROR"); + 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, "<--- befs_read_lsymlink() read %u bytes", 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, befs_data_stream * ds) +{ + befs_blocknr_t blocks; + befs_blocknr_t datablocks; /* File data blocks */ + befs_blocknr_t metablocks; /* FS metadata blocks */ + befs_sb_info *befs_sb = BEFS_SB(sb); + + befs_debug(sb, "---> befs_count_blocks()"); + + 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 mapps + 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, "<--- befs_count_blocks() %u blocks", blocks); + + return blocks; +} + +/* + 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. + + sb: the superblock + data: the datastream + blockno: the blocknumber to find + run: The found run is passed back through this pointer + + 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 lenght members + of the block run, so that blockno is the start and len is + still valid (the run ends in the same place). + + 2001-11-15 Will Dyson +*/ +static int +befs_find_brun_direct(struct super_block *sb, befs_data_stream * data, + befs_blocknr_t blockno, befs_block_run * run) +{ + int i; + befs_block_run *array = data->direct; + befs_blocknr_t sum; + befs_blocknr_t max_block = + data->max_direct_range >> BEFS_SB(sb)->block_shift; + + befs_debug(sb, "---> befs_find_brun_direct(), find %lu", blockno); + + if (blockno > max_block) { + befs_error(sb, "befs_find_brun_direct() passed block outside of" + "direct region"); + return BEFS_ERR; + } + + 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, "---> befs_find_brun_direct(), " + "found %lu at direct[%d]", blockno, i); + return BEFS_OK; + } + } + + befs_debug(sb, "---> befs_find_brun_direct() ERROR"); + return BEFS_ERR; +} + +/* + 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. + + sb: the superblock + data: the datastream + blockno: the blocknumber to find + run: The found run is passed back through this pointer + + 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. + + 2001-11-15 Will Dyson +*/ +static int +befs_find_brun_indirect(struct super_block *sb, + 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_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, "---> befs_find_brun_indirect(), find %lu", 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 = befs_bread(sb, indirblockno + i); + if (indirblock == NULL) { + befs_debug(sb, + "---> befs_find_brun_indirect() failed to " + "read disk block %lu from the indirect brun", + indirblockno + i); + return BEFS_ERR; + } + + array = (befs_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, + "<--- befs_find_brun_indirect() found " + "file block %lu at indirect[%d]", + blockno, j + (i * arraylen)); + return BEFS_OK; + } + sum += len; + } + + brelse(indirblock); + } + + /* Only fallthrough is an error */ + befs_error(sb, "BeFS: befs_find_brun_indirect() failed to find " + "file block %lu", blockno); + + befs_debug(sb, "<--- befs_find_brun_indirect() ERROR"); + return BEFS_ERR; +} + +/* + 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. + + sb: the superblock + data: the datastream + blockno: the blocknumber to find + run: The found run is passed back through this pointer + + 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. + + 2001-11-15 Will Dyson +*/ +static int +befs_find_brun_dblindirect(struct super_block *sb, + 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_inode_addr *iaddr_array = NULL; + befs_sb_info *befs_sb = BEFS_SB(sb); + + befs_blocknr_t indir_start_blk = + data->max_indirect_range >> befs_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, "---> befs_find_brun_dblindirect() find %lu", 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 " + "befs_read_brun_dblindirect(), %d, is outside the range " + "of the double-indirect block", dblindir_indx); + return BEFS_ERR; + } + + dbl_indir_block = + befs_bread(sb, iaddr2blockno(sb, &data->double_indirect) + + dbl_which_block); + if (dbl_indir_block == NULL) { + befs_error(sb, "befs_read_brun_dblindirect() couldn't read the " + "double-indirect block at blockno %lu", + iaddr2blockno(sb, + &data->double_indirect) + + dbl_which_block); + brelse(dbl_indir_block); + return BEFS_ERR; + } + + dbl_block_indx = + dblindir_indx - (dbl_which_block * befs_iaddrs_per_block(sb)); + iaddr_array = (befs_inode_addr *) dbl_indir_block->b_data; + indir_run = fsrun_to_cpu(sb, iaddr_array[dbl_block_indx]); + brelse(dbl_indir_block); + iaddr_array = NULL; + + /* 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 " + "befs_read_brun_dblindirect(), %d, is outside the range " + "of the indirect block", indir_indx); + return BEFS_ERR; + } + + indir_block = + befs_bread(sb, iaddr2blockno(sb, &indir_run) + which_block); + if (indir_block == NULL) { + befs_error(sb, "befs_read_brun_dblindirect() couldn't read the " + "indirect block at blockno %lu", + iaddr2blockno(sb, &indir_run) + which_block); + brelse(indir_block); + return BEFS_ERR; + } + + block_indx = indir_indx - (which_block * befs_iaddrs_per_block(sb)); + iaddr_array = (befs_inode_addr *) indir_block->b_data; + *run = fsrun_to_cpu(sb, iaddr_array[block_indx]); + brelse(indir_block); + iaddr_array = NULL; + + 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", + 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 00000000000..45e8a3c9824 --- /dev/null +++ b/fs/befs/datastream.h @@ -0,0 +1,19 @@ +/* + * datastream.h + * + */ + +struct buffer_head *befs_read_datastream(struct super_block *sb, + befs_data_stream * ds, befs_off_t pos, + uint * off); + +int befs_fblock2brun(struct super_block *sb, befs_data_stream * data, + befs_blocknr_t fblock, befs_block_run * run); + +size_t befs_read_lsymlink(struct super_block *sb, befs_data_stream * data, + void *buff, befs_off_t len); + +befs_blocknr_t befs_count_blocks(struct super_block *sb, 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 00000000000..875cc0aa318 --- /dev/null +++ b/fs/befs/debug.c @@ -0,0 +1,283 @@ +/* + * 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 + */ + +#ifdef __KERNEL__ + +#include +#include +#include +#include +#include + +#endif /* __KERNEL__ */ + +#include "befs.h" +#include "endian.h" + +#define ERRBUFSIZE 1024 + +void +befs_error(const struct super_block *sb, const char *fmt, ...) +{ + va_list args; + char *err_buf = (char *) kmalloc(ERRBUFSIZE, GFP_KERNEL); + if (err_buf == NULL) { + printk(KERN_ERR "could not allocate %d bytes\n", ERRBUFSIZE); + return; + } + + va_start(args, fmt); + vsnprintf(err_buf, ERRBUFSIZE, fmt, args); + va_end(args); + + printk(KERN_ERR "BeFS(%s): %s\n", sb->s_id, err_buf); + kfree(err_buf); +} + +void +befs_warning(const struct super_block *sb, const char *fmt, ...) +{ + va_list args; + char *err_buf = (char *) kmalloc(ERRBUFSIZE, GFP_KERNEL); + if (err_buf == NULL) { + printk(KERN_ERR "could not allocate %d bytes\n", ERRBUFSIZE); + return; + } + + va_start(args, fmt); + vsnprintf(err_buf, ERRBUFSIZE, fmt, args); + va_end(args); + + printk(KERN_WARNING "BeFS(%s): %s\n", sb->s_id, err_buf); + + kfree(err_buf); +} + +void +befs_debug(const struct super_block *sb, const char *fmt, ...) +{ +#ifdef CONFIG_BEFS_DEBUG + + va_list args; + char *err_buf = NULL; + + if (BEFS_SB(sb)->mount_opts.debug) { + err_buf = (char *) kmalloc(ERRBUFSIZE, GFP_KERNEL); + if (err_buf == NULL) { + printk(KERN_ERR "could not allocate %d bytes\n", + ERRBUFSIZE); + return; + } + + va_start(args, fmt); + vsnprintf(err_buf, ERRBUFSIZE, fmt, args); + va_end(args); + + printk(KERN_DEBUG "BeFS(%s): %s\n", sb->s_id, err_buf); + + kfree(err_buf); + } + +#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 %Lu", + fs64_to_cpu(sb, inode->create_time)); + befs_debug(sb, " last_modified_time %Lu", + 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(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 %Lu", + 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 %Lu", + 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 %Lu", + fs64_to_cpu(sb, + inode->data.datastream. + max_double_indirect_range)); + + befs_debug(sb, " size %Lu", + 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 %Lu", fs64_to_cpu(sb, sup->num_blocks)); + befs_debug(sb, " used_blocks %Lu", fs64_to_cpu(sb, sup->used_blocks)); + + 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 %Ld", fs64_to_cpu(sb, sup->log_start)); + befs_debug(sb, " log_end %Ld", 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_block_run run) +{ +#ifdef CONFIG_BEFS_DEBUG + + run = fsrun_to_cpu(sb, run); + + befs_debug(sb, "[%u, %hu, %hu]", + run.allocation_group, run.start, run.len); + +#endif //CONFIG_BEFS_DEBUG +} +#endif /* 0 */ + +void +befs_dump_index_entry(const struct super_block *sb, befs_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 00000000000..9ecaea4e332 --- /dev/null +++ b/fs/befs/endian.h @@ -0,0 +1,126 @@ +/* + * linux/fs/befs/endian.h + * + * Copyright (C) 2001 Will Dyson + * + * Partially based on similar funtions in the sysv driver. + */ + +#ifndef LINUX_BEFS_ENDIAN +#define LINUX_BEFS_ENDIAN + +#include +#include "befs.h" + +static inline u64 +fs64_to_cpu(const struct super_block *sb, u64 n) +{ + if (BEFS_SB(sb)->byte_order == BEFS_BYTESEX_LE) + return le64_to_cpu(n); + else + return be64_to_cpu(n); +} + +static inline u64 +cpu_to_fs64(const struct super_block *sb, u64 n) +{ + if (BEFS_SB(sb)->byte_order == BEFS_BYTESEX_LE) + return cpu_to_le64(n); + else + return cpu_to_be64(n); +} + +static inline u32 +fs32_to_cpu(const struct super_block *sb, u32 n) +{ + if (BEFS_SB(sb)->byte_order == BEFS_BYTESEX_LE) + return le32_to_cpu(n); + else + return be32_to_cpu(n); +} + +static inline u32 +cpu_to_fs32(const struct super_block *sb, u32 n) +{ + if (BEFS_SB(sb)->byte_order == BEFS_BYTESEX_LE) + return cpu_to_le32(n); + else + return cpu_to_be32(n); +} + +static inline u16 +fs16_to_cpu(const struct super_block *sb, u16 n) +{ + if (BEFS_SB(sb)->byte_order == BEFS_BYTESEX_LE) + return le16_to_cpu(n); + else + return be16_to_cpu(n); +} + +static inline u16 +cpu_to_fs16(const struct super_block *sb, u16 n) +{ + if (BEFS_SB(sb)->byte_order == BEFS_BYTESEX_LE) + return cpu_to_le16(n); + else + return cpu_to_be16(n); +} + +/* Composite types below here */ + +static inline befs_block_run +fsrun_to_cpu(const struct super_block *sb, befs_block_run n) +{ + befs_block_run run; + + if (BEFS_SB(sb)->byte_order == BEFS_BYTESEX_LE) { + run.allocation_group = le32_to_cpu(n.allocation_group); + run.start = le16_to_cpu(n.start); + run.len = le16_to_cpu(n.len); + } else { + run.allocation_group = be32_to_cpu(n.allocation_group); + run.start = be16_to_cpu(n.start); + run.len = be16_to_cpu(n.len); + } + return run; +} + +static inline befs_block_run +cpu_to_fsrun(const struct super_block *sb, befs_block_run n) +{ + befs_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, befs_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 00000000000..d41c9247ae8 --- /dev/null +++ b/fs/befs/inode.c @@ -0,0 +1,53 @@ +/* + * inode.c + * + * Copyright (C) 2001 Will Dyson + */ + +#include + +#include "befs.h" +#include "inode.h" +#include "endian.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", 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", + inode, 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", 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 00000000000..9dc7fd9b757 --- /dev/null +++ b/fs/befs/inode.h @@ -0,0 +1,8 @@ +/* + * 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 00000000000..ddef98aa255 --- /dev/null +++ b/fs/befs/io.c @@ -0,0 +1,83 @@ +/* + * linux/fs/befs/io.c + * + * Copyright (C) 2001 Will Dyson + +#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. -Will Dyson + * + */ + +struct buffer_head * +befs_bread_iaddr(struct super_block *sb, befs_inode_addr iaddr) +{ + struct buffer_head *bh = NULL; + befs_blocknr_t block = 0; + befs_sb_info *befs_sb = BEFS_SB(sb); + + befs_debug(sb, "---> Enter befs_read_iaddr() " + "[%u, %hu, %hu]", + 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, "befs_read_iaddr: offset = %lu", block); + + bh = sb_bread(sb, block); + + if (bh == NULL) { + befs_error(sb, "Failed to read block %lu", block); + goto error; + } + + befs_debug(sb, "<--- befs_read_iaddr()"); + return bh; + + error: + befs_debug(sb, "<--- befs_read_iaddr() ERROR"); + return NULL; +} + +struct buffer_head * +befs_bread(struct super_block *sb, befs_blocknr_t block) +{ + struct buffer_head *bh = NULL; + + befs_debug(sb, "---> Enter befs_read() %Lu", block); + + bh = sb_bread(sb, block); + + if (bh == NULL) { + befs_error(sb, "Failed to read block %lu", block); + goto error; + } + + befs_debug(sb, "<--- befs_read()"); + + return bh; + + error: + befs_debug(sb, "<--- befs_read() ERROR"); + return NULL; +} diff --git a/fs/befs/io.h b/fs/befs/io.h new file mode 100644 index 00000000000..9b78266b6aa --- /dev/null +++ b/fs/befs/io.h @@ -0,0 +1,9 @@ +/* + * io.h + */ + +struct buffer_head *befs_bread_iaddr(struct super_block *sb, + befs_inode_addr iaddr); + +struct buffer_head *befs_bread(struct super_block *sb, befs_blocknr_t block); + diff --git a/fs/befs/linuxvfs.c b/fs/befs/linuxvfs.c new file mode 100644 index 00000000000..de5bb280a82 --- /dev/null +++ b/fs/befs/linuxvfs.c @@ -0,0 +1,964 @@ +/* + * linux/fs/befs/linuxvfs.c + * + * Copyright (C) 2001 Will Dyson +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "befs.h" +#include "btree.h" +#include "inode.h" +#include "datastream.h" +#include "super.h" +#include "io.h" +#include "endian.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 *, void *, filldir_t); +static int befs_get_block(struct inode *, sector_t, struct buffer_head *, int); +static int befs_readpage(struct file *file, struct page *page); +static sector_t befs_bmap(struct address_space *mapping, sector_t block); +static struct dentry *befs_lookup(struct inode *, struct dentry *, struct nameidata *); +static void befs_read_inode(struct inode *ino); +static struct inode *befs_alloc_inode(struct super_block *sb); +static void befs_destroy_inode(struct inode *inode); +static int befs_init_inodecache(void); +static void befs_destroy_inodecache(void); +static int befs_follow_link(struct dentry *, struct nameidata *); +static void befs_put_link(struct dentry *, struct nameidata *); +static int befs_utf2nls(struct super_block *sb, const char *in, int in_len, + char **out, int *out_len); +static int befs_nls2utf(struct super_block *sb, const char *in, int in_len, + char **out, int *out_len); +static void befs_put_super(struct super_block *); +static int befs_remount(struct super_block *, int *, char *); +static int befs_statfs(struct super_block *, struct kstatfs *); +static int parse_options(char *, befs_mount_options *); + +static const struct super_operations befs_sops = { + .read_inode = befs_read_inode, /* initialize & read inode */ + .alloc_inode = befs_alloc_inode, /* allocate a new inode */ + .destroy_inode = befs_destroy_inode, /* deallocate an inode */ + .put_super = befs_put_super, /* uninit super */ + .statfs = befs_statfs, /* statfs */ + .remount_fs = befs_remount, +}; + +/* slab cache for befs_inode_info objects */ +static kmem_cache_t *befs_inode_cachep; + +static struct file_operations befs_dir_operations = { + .read = generic_read_dir, + .readdir = befs_readdir, +}; + +static struct inode_operations befs_dir_inode_operations = { + .lookup = befs_lookup, +}; + +static struct file_operations befs_file_operations = { + .llseek = default_llseek, + .read = generic_file_read, + .mmap = generic_file_readonly_mmap, +}; + +static struct address_space_operations befs_aops = { + .readpage = befs_readpage, + .sync_page = block_sync_page, + .bmap = befs_bmap, +}; + +static struct inode_operations befs_symlink_inode_operations = { + .readlink = generic_readlink, + .follow_link = befs_follow_link, + .put_link = befs_put_link, +}; + +/* + * Called by generic_file_read() to read a page of data + * + * In turn, simply calls a generic block read function and + * passes it the address of befs_get_block, for mapping file + * positions to disk blocks. + */ +static int +befs_readpage(struct file *file, struct page *page) +{ + return block_read_full_page(page, befs_get_block); +} + +static sector_t +befs_bmap(struct address_space *mapping, sector_t block) +{ + return generic_block_bmap(mapping, block, befs_get_block); +} + +/* + * Generic function to map a file position (block) to a + * disk offset (passed back in bh_result). + * + * Used by many higher level functions. + * + * Calls befs_fblock2brun() in datastream.c to do the real work. + * + * -WD 10-26-01 + */ + +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 = 0; + ulong disk_off; + + befs_debug(sb, "---> befs_get_block() for inode %lu, block %ld", + inode->i_ino, block); + + if (block < 0) { + befs_error(sb, "befs_get_block() was asked for a block " + "number less than zero: block %ld in inode %lu", + block, inode->i_ino); + return -EIO; + } + + if (create) { + befs_error(sb, "befs_get_block() was asked to write to " + "block %ld in inode %lu", block, inode->i_ino); + return -EPERM; + } + + res = befs_fblock2brun(sb, ds, block, &run); + if (res != BEFS_OK) { + befs_error(sb, + "<--- befs_get_block() for inode %lu, block " + "%ld ERROR", inode->i_ino, block); + return -EFBIG; + } + + disk_off = (ulong) iaddr2blockno(sb, &run); + + map_bh(bh_result, inode->i_sb, disk_off); + + befs_debug(sb, "<--- befs_get_block() for inode %lu, block %ld, " + "disk address %lu", inode->i_ino, block, disk_off); + + return 0; +} + +static struct dentry * +befs_lookup(struct inode *dir, struct dentry *dentry, struct nameidata *nd) +{ + struct inode *inode = NULL; + struct super_block *sb = dir->i_sb; + 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, "---> befs_lookup() " + "name %s inode %ld", dentry->d_name.name, 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, "<--- befs_lookup() ERROR"); + return ERR_PTR(ret); + } + ret = befs_btree_find(sb, ds, utfname, &offset); + kfree(utfname); + + } else { + ret = befs_btree_find(sb, ds, dentry->d_name.name, &offset); + } + + if (ret == BEFS_BT_NOT_FOUND) { + befs_debug(sb, "<--- befs_lookup() %s not found", + dentry->d_name.name); + return ERR_PTR(-ENOENT); + + } else if (ret != BEFS_OK || offset == 0) { + befs_warning(sb, "<--- befs_lookup() Error"); + return ERR_PTR(-ENODATA); + } + + inode = iget(dir->i_sb, (ino_t) offset); + if (!inode) + return ERR_PTR(-EACCES); + + d_add(dentry, inode); + + befs_debug(sb, "<--- befs_lookup()"); + + return NULL; +} + +static int +befs_readdir(struct file *filp, void *dirent, filldir_t filldir) +{ + struct inode *inode = filp->f_dentry->d_inode; + struct super_block *sb = inode->i_sb; + befs_data_stream *ds = &BEFS_I(inode)->i_data.ds; + befs_off_t value; + int result; + size_t keysize; + unsigned char d_type; + char keybuf[BEFS_NAME_LEN + 1]; + char *nlsname; + int nlsnamelen; + const char *dirname = filp->f_dentry->d_name.name; + + befs_debug(sb, "---> befs_readdir() " + "name %s, inode %ld, filp->f_pos %Ld", + dirname, inode->i_ino, filp->f_pos); + + result = befs_btree_read(sb, ds, filp->f_pos, BEFS_NAME_LEN + 1, + keybuf, &keysize, &value); + + if (result == BEFS_ERR) { + befs_debug(sb, "<--- befs_readdir() ERROR"); + befs_error(sb, "IO error reading %s (inode %lu)", + dirname, inode->i_ino); + return -EIO; + + } else if (result == BEFS_BT_END) { + befs_debug(sb, "<--- befs_readdir() END"); + return 0; + + } else if (result == BEFS_BT_EMPTY) { + befs_debug(sb, "<--- befs_readdir() Empty directory"); + return 0; + } + + d_type = DT_UNKNOWN; + + /* Convert to NLS */ + if (BEFS_SB(sb)->nls) { + result = + befs_utf2nls(sb, keybuf, keysize, &nlsname, &nlsnamelen); + if (result < 0) { + befs_debug(sb, "<--- befs_readdir() ERROR"); + return result; + } + result = filldir(dirent, nlsname, nlsnamelen, filp->f_pos, + (ino_t) value, d_type); + kfree(nlsname); + + } else { + result = filldir(dirent, keybuf, keysize, filp->f_pos, + (ino_t) value, d_type); + } + + filp->f_pos++; + + befs_debug(sb, "<--- befs_readdir() filp->f_pos %Ld", filp->f_pos); + + return 0; +} + +static struct inode * +befs_alloc_inode(struct super_block *sb) +{ + struct befs_inode_info *bi; + bi = (struct befs_inode_info *)kmem_cache_alloc(befs_inode_cachep, + SLAB_KERNEL); + if (!bi) + return NULL; + return &bi->vfs_inode; +} + +static void +befs_destroy_inode(struct inode *inode) +{ + kmem_cache_free(befs_inode_cachep, BEFS_I(inode)); +} + +static void init_once(void * foo, kmem_cache_t * cachep, unsigned long flags) +{ + struct befs_inode_info *bi = (struct befs_inode_info *) foo; + + if ((flags & (SLAB_CTOR_VERIFY|SLAB_CTOR_CONSTRUCTOR)) == + SLAB_CTOR_CONSTRUCTOR) { + inode_init_once(&bi->vfs_inode); + } +} + +static void +befs_read_inode(struct inode *inode) +{ + struct buffer_head *bh = NULL; + befs_inode *raw_inode = NULL; + + struct super_block *sb = inode->i_sb; + befs_sb_info *befs_sb = BEFS_SB(sb); + befs_inode_info *befs_ino = NULL; + + befs_debug(sb, "---> befs_read_inode() " "inode = %lu", inode->i_ino); + + 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 = befs_bread(sb, inode->i_ino); + if (!bh) { + befs_error(sb, "unable to read inode block - " + "inode = %lu", inode->i_ino); + goto unaquire_none; + } + + raw_inode = (befs_inode *) bh->b_data; + + befs_dump_inode(sb, raw_inode); + + if (befs_check_inode(sb, raw_inode, inode->i_ino) != BEFS_OK) { + befs_error(sb, "Bad inode: %lu", inode->i_ino); + goto unaquire_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 : (uid_t) fs32_to_cpu(sb, raw_inode->uid); + inode->i_gid = befs_sb->mount_opts.use_gid ? + befs_sb->mount_opts.gid : (gid_t) fs32_to_cpu(sb, raw_inode->gid); + + inode->i_nlink = 1; + + /* + * BEFS's time is 64 bits, but current VFS is 32 bits... + * BEFS don't have access time. Nor inode change time. VFS + * doesn't have creation time. + * Also, the lower 16 bits of the last_modified_time and + * create_time are just a counter to help ensure uniqueness + * for indexing purposes. (PFD, page 54) + */ + + inode->i_mtime.tv_sec = + fs64_to_cpu(sb, raw_inode->last_modified_time) >> 16; + inode->i_mtime.tv_nsec = 0; /* lower 16 bits are not a time */ + inode->i_ctime = inode->i_mtime; + inode->i_atime = inode->i_mtime; + inode->i_blksize = befs_sb->block_size; + + 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; + strncpy(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 = &befs_file_operations; + } 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)) { + inode->i_op = &befs_symlink_inode_operations; + } else { + befs_error(sb, "Inode %lu is not a regular file, " + "directory or symlink. THAT IS WRONG! BeFS has no " + "on disk special files", inode->i_ino); + goto unaquire_bh; + } + + brelse(bh); + befs_debug(sb, "<--- befs_read_inode()"); + return; + + unaquire_bh: + brelse(bh); + + unaquire_none: + make_bad_inode(inode); + befs_debug(sb, "<--- befs_read_inode() - Bad inode"); + return; +} + +/* Initialize the inode cache. Called at fs setup. + * + * Taken from NFS implementation by Al Viro. + */ +static int +befs_init_inodecache(void) +{ + befs_inode_cachep = kmem_cache_create("befs_inode_cache", + sizeof (struct befs_inode_info), + 0, SLAB_RECLAIM_ACCOUNT, + init_once, NULL); + if (befs_inode_cachep == NULL) { + printk(KERN_ERR "befs_init_inodecache: " + "Couldn't initalize inode slabcache\n"); + return -ENOMEM; + } + + return 0; +} + +/* Called at fs teardown. + * + * Taken from NFS implementation by Al Viro. + */ +static void +befs_destroy_inodecache(void) +{ + if (kmem_cache_destroy(befs_inode_cachep)) + printk(KERN_ERR "befs_destroy_inodecache: " + "not all structures were freed\n"); +} + +/* + * 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_follow_link(struct dentry *dentry, struct nameidata *nd) +{ + befs_inode_info *befs_ino = BEFS_I(dentry->d_inode); + char *link; + + if (befs_ino->i_flags & BEFS_LONG_SYMLINK) { + struct super_block *sb = dentry->d_sb; + befs_data_stream *data = &befs_ino->i_data.ds; + befs_off_t len = data->size; + + befs_debug(sb, "Follow long symlink"); + + link = kmalloc(len, GFP_NOFS); + if (!link) { + link = ERR_PTR(-ENOMEM); + } else if (befs_read_lsymlink(sb, data, link, len) != len) { + kfree(link); + befs_error(sb, "Failed to read entire long symlink"); + link = ERR_PTR(-EIO); + } + } else { + link = befs_ino->i_data.symlink; + } + + nd_set_link(nd, link); + return 0; +} + +static void befs_put_link(struct dentry *dentry, struct nameidata *nd) +{ + befs_inode_info *befs_ino = BEFS_I(dentry->d_inode); + if (befs_ino->i_flags & BEFS_LONG_SYMLINK) { + char *p = nd_get_link(nd); + if (!IS_ERR(p)) + kfree(p); + } +} + +/* + * UTF-8 to NLS charset convert routine + * + * + * Changed 8/10/01 by Will Dyson. Now use 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; + wchar_t uni; + int unilen, utflen; + char *result; + int maxlen = in_len; /* The utf8->nls conversion can't make more chars */ + + befs_debug(sb, "---> utf2nls()"); + + if (!nls) { + befs_error(sb, "befs_utf2nls called with no NLS table loaded"); + return -EINVAL; + } + + *out = result = kmalloc(maxlen, GFP_NOFS); + if (!*out) { + befs_error(sb, "befs_utf2nls() cannot allocate memory"); + *out_len = 0; + return -ENOMEM; + } + + for (i = o = 0; i < in_len; i += utflen, o += unilen) { + + /* convert from UTF-8 to Unicode */ + utflen = utf8_mbtowc(&uni, &in[i], in_len - i); + if (utflen < 0) { + goto conv_err; + } + + /* convert from Unicode to nls */ + unilen = nls->uni2char(uni, &result[o], in_len - o); + if (unilen < 0) { + goto conv_err; + } + } + result[o] = '\0'; + *out_len = o; + + befs_debug(sb, "<--- utf2nls()"); + + 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, "<--- utf2nls()"); + kfree(result); + return -EILSEQ; +} + +/** + * befs_nls2utf - Convert NLS string to utf8 encodeing + * @sb: Superblock + * @src: Input string buffer in NLS format + * @srclen: Length of input string in bytes + * @dest: The output string in UTF8 format + * @destlen: Length of the output buffer + * + * Converts input string @src, which is in the format of the loaded NLS map, + * into a utf8 string. + * + * The destination string @dest is allocated by this function and the caller is + * responsible for freeing it with kfree() + * + * On return, *@destlen is the length of @dest in bytes. + * + * On success, the return value is the number of utf8 characters written to + * the output buffer @dest. + * + * 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; + int maxlen = 3 * in_len; + + befs_debug(sb, "---> nls2utf()\n"); + + if (!nls) { + befs_error(sb, "befs_nls2utf called with no NLS table loaded."); + return -EINVAL; + } + + *out = result = kmalloc(maxlen, GFP_NOFS); + if (!*out) { + befs_error(sb, "befs_nls2utf() cannot allocate memory"); + *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 = utf8_wctomb(&result[o], uni, 3); + if (utflen <= 0) { + goto conv_err; + } + } + + result[o] = '\0'; + *out_len = o; + + befs_debug(sb, "<--- nls2utf()"); + + return i; + + conv_err: + befs_error(sb, "Name using charecter set %s contains a charecter that " + "cannot be converted to unicode.", nls->charset); + befs_debug(sb, "<--- nls2utf()"); + kfree(result); + return -EILSEQ; +} + +/** + * Use the + * + */ +enum { + Opt_uid, Opt_gid, Opt_charset, Opt_debug, Opt_err, +}; + +static match_table_t befs_tokens = { + {Opt_uid, "uid=%d"}, + {Opt_gid, "gid=%d"}, + {Opt_charset, "iocharset=%s"}, + {Opt_debug, "debug"}, + {Opt_err, NULL} +}; + +static int +parse_options(char *options, befs_mount_options * opts) +{ + char *p; + substring_t args[MAX_OPT_ARGS]; + int option; + + /* Initialize options */ + opts->uid = 0; + opts->gid = 0; + opts->use_uid = 0; + opts->use_gid = 0; + opts->iocharset = NULL; + opts->debug = 0; + + if (!options) + return 1; + + while ((p = strsep(&options, ",")) != NULL) { + int token; + if (!*p) + continue; + + token = match_token(p, befs_tokens, args); + switch (token) { + case Opt_uid: + if (match_int(&args[0], &option)) + return 0; + if (option < 0) { + printk(KERN_ERR "BeFS: Invalid uid %d, " + "using default\n", option); + break; + } + opts->uid = option; + opts->use_uid = 1; + break; + case Opt_gid: + if (match_int(&args[0], &option)) + return 0; + if (option < 0) { + printk(KERN_ERR "BeFS: Invalid gid %d, " + "using default\n", option); + break; + } + opts->gid = option; + opts->use_gid = 1; + break; + case Opt_charset: + kfree(opts->iocharset); + opts->iocharset = match_strdup(&args[0]); + if (!opts->iocharset) { + printk(KERN_ERR "BeFS: allocation failure for " + "iocharset string\n"); + return 0; + } + break; + case Opt_debug: + opts->debug = 1; + break; + default: + printk(KERN_ERR "BeFS: Unrecognized mount option \"%s\" " + "or missing value\n", p); + return 0; + } + } + return 1; +} + +/* This function has the responsibiltiy of getting the + * filesystem ready for unmounting. + * Basicly, we free everything that we allocated in + * befs_read_inode + */ +static void +befs_put_super(struct super_block *sb) +{ + if (BEFS_SB(sb)->mount_opts.iocharset) { + kfree(BEFS_SB(sb)->mount_opts.iocharset); + BEFS_SB(sb)->mount_opts.iocharset = NULL; + } + + if (BEFS_SB(sb)->nls) { + unload_nls(BEFS_SB(sb)->nls); + BEFS_SB(sb)->nls = NULL; + } + + if (sb->s_fs_info) { + kfree(sb->s_fs_info); + sb->s_fs_info = NULL; + } + return; +} + +/* Allocate private field of the superblock, fill it. + * + * Finish filling the public superblock fields + * Make the root directory + * Load a set of NLS translations if needed. + */ +static int +befs_fill_super(struct super_block *sb, void *data, int silent) +{ + struct buffer_head *bh; + befs_sb_info *befs_sb; + befs_super_block *disk_sb; + struct inode *root; + + const unsigned long sb_block = 0; + const off_t x86_sb_off = 512; + + sb->s_fs_info = kmalloc(sizeof (*befs_sb), GFP_KERNEL); + if (sb->s_fs_info == NULL) { + printk(KERN_ERR + "BeFS(%s): Unable to allocate memory for private " + "portion of superblock. Bailing.\n", sb->s_id); + goto unaquire_none; + } + befs_sb = BEFS_SB(sb); + memset(befs_sb, 0, sizeof(befs_sb_info)); + + if (!parse_options((char *) data, &befs_sb->mount_opts)) { + befs_error(sb, "cannot parse mount options"); + goto unaquire_priv_sbp; + } + + befs_debug(sb, "---> befs_fill_super()"); + +#ifndef CONFIG_BEFS_RW + if (!(sb->s_flags & MS_RDONLY)) { + befs_warning(sb, + "No write support. Marking filesystem read-only"); + sb->s_flags |= MS_RDONLY; + } +#endif /* CONFIG_BEFS_RW */ + + /* + * 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 hardsect size for the device. But we also need to read at + * least 1k to get the second 512 bytes of the volume. + * -WD 10-26-01 + */ + sb_min_blocksize(sb, 1024); + + if (!(bh = sb_bread(sb, sb_block))) { + befs_error(sb, "unable to read superblock"); + goto unaquire_priv_sbp; + } + + /* account for offset of super block on x86 */ + disk_sb = (befs_super_block *) bh->b_data; + if ((le32_to_cpu(disk_sb->magic1) == BEFS_SUPER_MAGIC1) || + (be32_to_cpu(disk_sb->magic1) == BEFS_SUPER_MAGIC1)) { + 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) + goto unaquire_bh; + + befs_dump_super_block(sb, disk_sb); + + brelse(bh); + + if (befs_check_sb(sb) != BEFS_OK) + goto unaquire_priv_sbp; + + if( befs_sb->num_blocks > ~((sector_t)0) ) { + befs_error(sb, "blocks count: %Lu " + "is larger than the host can use", + befs_sb->num_blocks); + goto unaquire_priv_sbp; + } + + /* + * set up enough so that it can read an inode + * Fill in kernel superblock fields from private sb + */ + sb->s_magic = BEFS_SUPER_MAGIC; + /* Set real blocksize of fs */ + sb_set_blocksize(sb, (ulong) befs_sb->block_size); + sb->s_op = (struct super_operations *) &befs_sops; + root = iget(sb, iaddr2blockno(sb, &(befs_sb->root_dir))); + sb->s_root = d_alloc_root(root); + if (!sb->s_root) { + iput(root); + befs_error(sb, "get root inode failed"); + goto unaquire_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; +/*****************/ + unaquire_bh: + brelse(bh); + + unaquire_priv_sbp: + kfree(sb->s_fs_info); + + unaquire_none: + sb->s_fs_info = NULL; + return -EINVAL; +} + +static int +befs_remount(struct super_block *sb, int *flags, char *data) +{ + if (!(*flags & MS_RDONLY)) + return -EINVAL; + return 0; +} + +static int +befs_statfs(struct super_block *sb, struct kstatfs *buf) +{ + + befs_debug(sb, "---> befs_statfs()"); + + 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_namelen = BEFS_NAME_LEN; + + befs_debug(sb, "<--- befs_statfs()"); + + return 0; +} + +static struct super_block * +befs_get_sb(struct file_system_type *fs_type, int flags, const char *dev_name, + void *data) +{ + return get_sb_bdev(fs_type, flags, dev_name, data, befs_fill_super); +} + +static struct file_system_type befs_fs_type = { + .owner = THIS_MODULE, + .name = "befs", + .get_sb = befs_get_sb, + .kill_sb = kill_block_super, + .fs_flags = FS_REQUIRES_DEV, +}; + +static int __init +init_befs_fs(void) +{ + int err; + + printk(KERN_INFO "BeFS version: %s\n", BEFS_VERSION); + + err = befs_init_inodecache(); + if (err) + goto unaquire_none; + + err = register_filesystem(&befs_fs_type); + if (err) + goto unaquire_inodecache; + + return 0; + +unaquire_inodecache: + befs_destroy_inodecache(); + +unaquire_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 00000000000..4557acbac52 --- /dev/null +++ b/fs/befs/super.c @@ -0,0 +1,112 @@ +/* + * super.c + * + * Copyright (C) 2001-2002 Will Dyson + * + * Licensed under the GNU GPL. See the file COPYING for details. + * + */ + +#include + +#include "befs.h" +#include "super.h" +#include "endian.h" + +/** + * load_befs_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) +{ + befs_sb_info *befs_sb = BEFS_SB(sb); + + /* Check the byte order of the filesystem */ + if (le32_to_cpu(disk_sb->fs_byte_order) == BEFS_BYTEORDER_NATIVE) + befs_sb->byte_order = BEFS_BYTESEX_LE; + else if (be32_to_cpu(disk_sb->fs_byte_order) == BEFS_BYTEORDER_NATIVE) + 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->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) +{ + 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; + } + + if (befs_sb->log_start != befs_sb->log_end) { + 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 00000000000..dc4556376a2 --- /dev/null +++ b/fs/befs/super.h @@ -0,0 +1,8 @@ +/* + * super.h + */ + +int befs_load_sb(struct super_block *sb, befs_super_block * disk_sb); + +int befs_check_sb(struct super_block *sb); + -- cgit v1.2.3