summaryrefslogtreecommitdiff
path: root/Documentation
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@linux-foundation.org>2016-12-16 10:24:44 -0800
committerLinus Torvalds <torvalds@linux-foundation.org>2016-12-16 10:24:44 -0800
commit9a19a6db37ee0b7a6db796b3dcd6bb6e7237d6ea (patch)
tree614d68498eea1c6f9120cae07806f916fd9776bc /Documentation
parentbd9999cd6a5eb899504ce14c1f70c5479143bbbc (diff)
parentc4364f837caf618c2fdb51a2e132cf29dfd1fffa (diff)
Merge branch 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/viro/vfs
Pull vfs updates from Al Viro: - more ->d_init() stuff (work.dcache) - pathname resolution cleanups (work.namei) - a few missing iov_iter primitives - copy_from_iter_full() and friends. Either copy the full requested amount, advance the iterator and return true, or fail, return false and do _not_ advance the iterator. Quite a few open-coded callers converted (and became more readable and harder to fuck up that way) (work.iov_iter) - several assorted patches, the big one being logfs removal * 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/viro/vfs: logfs: remove from tree vfs: fix put_compat_statfs64() does not handle errors namei: fold should_follow_link() with the step into not-followed link namei: pass both WALK_GET and WALK_MORE to should_follow_link() namei: invert WALK_PUT logics namei: shift interpretation of LOOKUP_FOLLOW inside should_follow_link() namei: saner calling conventions for mountpoint_last() namei.c: get rid of user_path_parent() switch getfrag callbacks to ..._full() primitives make skb_add_data,{_nocache}() and skb_copy_to_page_nocache() advance only on success [iov_iter] new primitives - copy_from_iter_full() and friends don't open-code file_inode() ceph: switch to use of ->d_init() ceph: unify dentry_operations instances lustre: switch to use of ->d_init()
Diffstat (limited to 'Documentation')
-rw-r--r--Documentation/filesystems/00-INDEX2
-rw-r--r--Documentation/filesystems/logfs.txt241
2 files changed, 0 insertions, 243 deletions
diff --git a/Documentation/filesystems/00-INDEX b/Documentation/filesystems/00-INDEX
index f66e748fc5e4..b7bd6c9009cc 100644
--- a/Documentation/filesystems/00-INDEX
+++ b/Documentation/filesystems/00-INDEX
@@ -87,8 +87,6 @@ jfs.txt
- info and mount options for the JFS filesystem.
locks.txt
- info on file locking implementations, flock() vs. fcntl(), etc.
-logfs.txt
- - info on the LogFS flash filesystem.
mandatory-locking.txt
- info on the Linux implementation of Sys V mandatory file locking.
ncpfs.txt
diff --git a/Documentation/filesystems/logfs.txt b/Documentation/filesystems/logfs.txt
deleted file mode 100644
index bca42c22a143..000000000000
--- a/Documentation/filesystems/logfs.txt
+++ /dev/null
@@ -1,241 +0,0 @@
-
-The LogFS Flash Filesystem
-==========================
-
-Specification
-=============
-
-Superblocks
------------
-
-Two superblocks exist at the beginning and end of the filesystem.
-Each superblock is 256 Bytes large, with another 3840 Bytes reserved
-for future purposes, making a total of 4096 Bytes.
-
-Superblock locations may differ for MTD and block devices. On MTD the
-first non-bad block contains a superblock in the first 4096 Bytes and
-the last non-bad block contains a superblock in the last 4096 Bytes.
-On block devices, the first 4096 Bytes of the device contain the first
-superblock and the last aligned 4096 Byte-block contains the second
-superblock.
-
-For the most part, the superblocks can be considered read-only. They
-are written only to correct errors detected within the superblocks,
-move the journal and change the filesystem parameters through tunefs.
-As a result, the superblock does not contain any fields that require
-constant updates, like the amount of free space, etc.
-
-Segments
---------
-
-The space in the device is split up into equal-sized segments.
-Segments are the primary write unit of LogFS. Within each segments,
-writes happen from front (low addresses) to back (high addresses. If
-only a partial segment has been written, the segment number, the
-current position within and optionally a write buffer are stored in
-the journal.
-
-Segments are erased as a whole. Therefore Garbage Collection may be
-required to completely free a segment before doing so.
-
-Journal
---------
-
-The journal contains all global information about the filesystem that
-is subject to frequent change. At mount time, it has to be scanned
-for the most recent commit entry, which contains a list of pointers to
-all currently valid entries.
-
-Object Store
-------------
-
-All space except for the superblocks and journal is part of the object
-store. Each segment contains a segment header and a number of
-objects, each consisting of the object header and the payload.
-Objects are either inodes, directory entries (dentries), file data
-blocks or indirect blocks.
-
-Levels
-------
-
-Garbage collection (GC) may fail if all data is written
-indiscriminately. One requirement of GC is that data is separated
-roughly according to the distance between the tree root and the data.
-Effectively that means all file data is on level 0, indirect blocks
-are on levels 1, 2, 3 4 or 5 for 1x, 2x, 3x, 4x or 5x indirect blocks,
-respectively. Inode file data is on level 6 for the inodes and 7-11
-for indirect blocks.
-
-Each segment contains objects of a single level only. As a result,
-each level requires its own separate segment to be open for writing.
-
-Inode File
-----------
-
-All inodes are stored in a special file, the inode file. Single
-exception is the inode file's inode (master inode) which for obvious
-reasons is stored in the journal instead. Instead of data blocks, the
-leaf nodes of the inode files are inodes.
-
-Aliases
--------
-
-Writes in LogFS are done by means of a wandering tree. A naïve
-implementation would require that for each write or a block, all
-parent blocks are written as well, since the block pointers have
-changed. Such an implementation would not be very efficient.
-
-In LogFS, the block pointer changes are cached in the journal by means
-of alias entries. Each alias consists of its logical address - inode
-number, block index, level and child number (index into block) - and
-the changed data. Any 8-byte word can be changes in this manner.
-
-Currently aliases are used for block pointers, file size, file used
-bytes and the height of an inodes indirect tree.
-
-Segment Aliases
----------------
-
-Related to regular aliases, these are used to handle bad blocks.
-Initially, bad blocks are handled by moving the affected segment
-content to a spare segment and noting this move in the journal with a
-segment alias, a simple (to, from) tupel. GC will later empty this
-segment and the alias can be removed again. This is used on MTD only.
-
-Vim
----
-
-By cleverly predicting the life time of data, it is possible to
-separate long-living data from short-living data and thereby reduce
-the GC overhead later. Each type of distinc life expectency (vim) can
-have a separate segment open for writing. Each (level, vim) tupel can
-be open just once. If an open segment with unknown vim is encountered
-at mount time, it is closed and ignored henceforth.
-
-Indirect Tree
--------------
-
-Inodes in LogFS are similar to FFS-style filesystems with direct and
-indirect block pointers. One difference is that LogFS uses a single
-indirect pointer that can be either a 1x, 2x, etc. indirect pointer.
-A height field in the inode defines the height of the indirect tree
-and thereby the indirection of the pointer.
-
-Another difference is the addressing of indirect blocks. In LogFS,
-the first 16 pointers in the first indirect block are left empty,
-corresponding to the 16 direct pointers in the inode. In ext2 (maybe
-others as well) the first pointer in the first indirect block
-corresponds to logical block 12, skipping the 12 direct pointers.
-So where ext2 is using arithmetic to better utilize space, LogFS keeps
-arithmetic simple and uses compression to save space.
-
-Compression
------------
-
-Both file data and metadata can be compressed. Compression for file
-data can be enabled with chattr +c and disabled with chattr -c. Doing
-so has no effect on existing data, but new data will be stored
-accordingly. New inodes will inherit the compression flag of the
-parent directory.
-
-Metadata is always compressed. However, the space accounting ignores
-this and charges for the uncompressed size. Failing to do so could
-result in GC failures when, after moving some data, indirect blocks
-compress worse than previously. Even on a 100% full medium, GC may
-not consume any extra space, so the compression gains are lost space
-to the user.
-
-However, they are not lost space to the filesystem internals. By
-cheating the user for those bytes, the filesystem gained some slack
-space and GC will run less often and faster.
-
-Garbage Collection and Wear Leveling
-------------------------------------
-
-Garbage collection is invoked whenever the number of free segments
-falls below a threshold. The best (known) candidate is picked based
-on the least amount of valid data contained in the segment. All
-remaining valid data is copied elsewhere, thereby invalidating it.
-
-The GC code also checks for aliases and writes then back if their
-number gets too large.
-
-Wear leveling is done by occasionally picking a suboptimal segment for
-garbage collection. If a stale segments erase count is significantly
-lower than the active segments' erase counts, it will be picked. Wear
-leveling is rate limited, so it will never monopolize the device for
-more than one segment worth at a time.
-
-Values for "occasionally", "significantly lower" are compile time
-constants.
-
-Hashed directories
-------------------
-
-To satisfy efficient lookup(), directory entries are hashed and
-located based on the hash. In order to both support large directories
-and not be overly inefficient for small directories, several hash
-tables of increasing size are used. For each table, the hash value
-modulo the table size gives the table index.
-
-Tables sizes are chosen to limit the number of indirect blocks with a
-fully populated table to 0, 1, 2 or 3 respectively. So the first
-table contains 16 entries, the second 512-16, etc.
-
-The last table is special in several ways. First its size depends on
-the effective 32bit limit on telldir/seekdir cookies. Since logfs
-uses the upper half of the address space for indirect blocks, the size
-is limited to 2^31. Secondly the table contains hash buckets with 16
-entries each.
-
-Using single-entry buckets would result in birthday "attacks". At
-just 2^16 used entries, hash collisions would be likely (P >= 0.5).
-My math skills are insufficient to do the combinatorics for the 17x
-collisions necessary to overflow a bucket, but testing showed that in
-10,000 runs the lowest directory fill before a bucket overflow was
-188,057,130 entries with an average of 315,149,915 entries. So for
-directory sizes of up to a million, bucket overflows should be
-virtually impossible under normal circumstances.
-
-With carefully chosen filenames, it is obviously possible to cause an
-overflow with just 21 entries (4 higher tables + 16 entries + 1). So
-there may be a security concern if a malicious user has write access
-to a directory.
-
-Open For Discussion
-===================
-
-Device Address Space
---------------------
-
-A device address space is used for caching. Both block devices and
-MTD provide functions to either read a single page or write a segment.
-Partial segments may be written for data integrity, but where possible
-complete segments are written for performance on simple block device
-flash media.
-
-Meta Inodes
------------
-
-Inodes are stored in the inode file, which is just a regular file for
-most purposes. At umount time, however, the inode file needs to
-remain open until all dirty inodes are written. So
-generic_shutdown_super() may not close this inode, but shouldn't
-complain about remaining inodes due to the inode file either. Same
-goes for mapping inode of the device address space.
-
-Currently logfs uses a hack that essentially copies part of fs/inode.c
-code over. A general solution would be preferred.
-
-Indirect block mapping
-----------------------
-
-With compression, the block device (or mapping inode) cannot be used
-to cache indirect blocks. Some other place is required. Currently
-logfs uses the top half of each inode's address space. The low 8TB
-(on 32bit) are filled with file data, the high 8TB are used for
-indirect blocks.
-
-One problem is that 16TB files created on 64bit systems actually have
-data in the top 8TB. But files >16TB would cause problems anyway, so
-only the limit has changed.