Documentation/filesystems/aufs/design/02struct.txt

   1
   2 # Copyright (C) 2005-2011 Junjiro R. Okajima
   3 #
   4 # This program is free software; you can redistribute it and/or modify
   5 # it under the terms of the GNU General Public License as published by
   6 # the Free Software Foundation; either version 2 of the License, or
   7 # (at your option) any later version.
   8 #
   9 # This program is distributed in the hope that it will be useful,
  10 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 # GNU General Public License for more details.
  13 #
  14 # You should have received a copy of the GNU General Public License
  15 # along with this program; if not, write to the Free Software
  16 # Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17
  18 Basic Aufs Internal Structure
  19
  20 Superblock/Inode/Dentry/File Objects
  21 ----------------------------------------------------------------------
  22 As like an ordinary filesystem, aufs has its own
  23 superblock/inode/dentry/file objects. All these objects have a
  24 dynamically allocated array and store the same kind of pointers to the
  25 lower filesystem, branch.
  26 For example, when you build a union with one readwrite branch and one
  27 readonly, mounted /au, /rw and /ro respectively.
  28 - /au = /rw + /ro
  29 - /ro/fileA exists but /rw/fileA
  30
  31 Aufs lookup operation finds /ro/fileA and gets dentry for that. These
  32 pointers are stored in a aufs dentry. The array in aufs dentry will be,
  33 - [0] = NULL
  34 - [1] = /ro/fileA
  35
  36 This style of an array is essentially same to the aufs
  37 superblock/inode/dentry/file objects.
  38
  39 Because aufs supports manipulating branches, ie. add/delete/change
  40 dynamically, these objects has its own generation. When branches are
  41 changed, the generation in aufs superblock is incremented. And a
  42 generation in other object are compared when it is accessed.
  43 When a generation in other objects are obsoleted, aufs refreshes the
  44 internal array.
  45
  46
  47 Superblock
  48 ----------------------------------------------------------------------
  49 Additionally aufs superblock has some data for policies to select one
  50 among multiple writable branches, XIB files, pseudo-links and kobject.
  51 See below in detail.
  52 About the policies which supports copy-down a directory, see policy.txt
  53 too.
  54
  55
  56 Branch and XINO(External Inode Number Translation Table)
  57 ----------------------------------------------------------------------
  58 Every branch has its own xino (external inode number translation table)
  59 file. The xino file is created and unlinked by aufs internally. When two
  60 members of a union exist on the same filesystem, they share the single
  61 xino file.
  62 The struct of a xino file is simple, just a sequence of aufs inode
  63 numbers which is indexed by the lower inode number.
  64 In the above sample, assume the inode number of /ro/fileA is i111 and
  65 aufs assigns the inode number i999 for fileA. Then aufs writes 999 as
  66 4(8) bytes at 111 * 4(8) bytes offset in the xino file.
  67
  68 When the inode numbers are not contiguous, the xino file will be sparse
  69 which has a hole in it and doesn't consume as much disk space as it
  70 might appear. If your branch filesystem consumes disk space for such
  71 holes, then you should specify 'xino=' option at mounting aufs.
  72
  73 Also a writable branch has three kinds of "whiteout bases". All these
  74 are existed when the branch is joined to aufs and the names are
  75 whiteout-ed doubly, so that users will never see their names in aufs
  76 hierarchy.
  77 1. a regular file which will be linked to all whiteouts.
  78 2. a directory to store a pseudo-link.
  79 3. a directory to store an "orphan-ed" file temporary.
  80
  81 1. Whiteout Base
  82    When you remove a file on a readonly branch, aufs handles it as a
  83    logical deletion and creates a whiteout on the upper writable branch
  84    as a hardlink of this file in order not to consume inode on the
  85    writable branch.
  86 2. Pseudo-link Dir
  87    See below, Pseudo-link.
  88 3. Step-Parent Dir
  89    When "fileC" exists on the lower readonly branch only and it is
  90    opened and removed with its parent dir, and then user writes
  91    something into it, then aufs copies-up fileC to this
  92    directory. Because there is no other dir to store fileC. After
  93    creating a file under this dir, the file is unlinked.
  94
  95 Because aufs supports manipulating branches, ie. add/delete/change
  96 dynamically, a branch has its own id. When the branch order changes, aufs
  97 finds the new index by searching the branch id.
  98
  99
 100 Pseudo-link
 101 ----------------------------------------------------------------------
 102 Assume "fileA" exists on the lower readonly branch only and it is
 103 hardlinked to "fileB" on the branch. When you write something to fileA,
 104 aufs copies-up it to the upper writable branch. Additionally aufs
 105 creates a hardlink under the Pseudo-link Directory of the writable
 106 branch. The inode of a pseudo-link is kept in aufs super_block as a
 107 simple list. If fileB is read after unlinking fileA, aufs returns
 108 filedata from the pseudo-link instead of the lower readonly
 109 branch. Because the pseudo-link is based upon the inode, to keep the
 110 inode number by xino (see above) is important.
 111
 112 All the hardlinks under the Pseudo-link Directory of the writable branch
 113 should be restored in a proper location later. Aufs provides a utility
 114 to do this. The userspace helpers executed at remounting and unmounting
 115 aufs by default.
 116 During this utility is running, it puts aufs into the pseudo-link
 117 maintenance mode. In this mode, only the process which began the
 118 maintenance mode (and its child processes) is allowed to operate in
 119 aufs. Some other processes which are not related to the pseudo-link will
 120 be allowed to run too, but the rest have to return an error or wait
 121 until the maintenance mode ends. If a process already acquires an inode
 122 mutex (in VFS), it has to return an error.
 123
 124
 125 XIB(external inode number bitmap)
 126 ----------------------------------------------------------------------
 127 Addition to the xino file per a branch, aufs has an external inode number
 128 bitmap in a superblock object. It is also a file such like a xino file.
 129 It is a simple bitmap to mark whether the aufs inode number is in-use or
 130 not.
 131 To reduce the file I/O, aufs prepares a single memory page to cache xib.
 132
 133 Aufs implements a feature to truncate/refresh both of xino and xib to
 134 reduce the number of consumed disk blocks for these files.
 135
 136
 137 Virtual or Vertical Dir, and Readdir in Userspace
 138 ----------------------------------------------------------------------
 139 In order to support multiple layers (branches), aufs readdir operation
 140 constructs a virtual dir block on memory. For readdir, aufs calls
 141 vfs_readdir() internally for each dir on branches, merges their entries
 142 with eliminating the whiteout-ed ones, and sets it to file (dir)
 143 object. So the file object has its entry list until it is closed. The
 144 entry list will be updated when the file position is zero and becomes
 145 old. This decision is made in aufs automatically.
 146
 147 The dynamically allocated memory block for the name of entries has a
 148 unit of 512 bytes (by default) and stores the names contiguously (no
 149 padding). Another block for each entry is handled by kmem_cache too.
 150 During building dir blocks, aufs creates hash list and judging whether
 151 the entry is whiteouted by its upper branch or already listed.
 152 The merged result is cached in the corresponding inode object and
 153 maintained by a customizable life-time option.
 154
 155 Some people may call it can be a security hole or invite DoS attack
 156 since the opened and once readdir-ed dir (file object) holds its entry
 157 list and becomes a pressure for system memory. But I'd say it is similar
 158 to files under /proc or /sys. The virtual files in them also holds a
 159 memory page (generally) while they are opened. When an idea to reduce
 160 memory for them is introduced, it will be applied to aufs too.
 161 For those who really hate this situation, I've developed readdir(3)
 162 library which operates this merging in userspace. You just need to set
 163 LD_PRELOAD environment variable, and aufs will not consume no memory in
 164 kernel space for readdir(3).
 165
 166
 167 Workqueue
 168 ----------------------------------------------------------------------
 169 Aufs sometimes requires privilege access to a branch. For instance,
 170 in copy-up/down operation. When a user process is going to make changes
 171 to a file which exists in the lower readonly branch only, and the mode
 172 of one of ancestor directories may not be writable by a user
 173 process. Here aufs copy-up the file with its ancestors and they may
 174 require privilege to set its owner/group/mode/etc.
 175 This is a typical case of a application character of aufs (see
 176 Introduction).
 177
 178 Aufs uses workqueue synchronously for this case. It creates its own
 179 workqueue. The workqueue is a kernel thread and has privilege. Aufs
 180 passes the request to call mkdir or write (for example), and wait for
 181 its completion. This approach solves a problem of a signal handler
 182 simply.
 183 If aufs didn't adopt the workqueue and changed the privilege of the
 184 process, and if the mkdir/write call arises SIGXFSZ or other signal,
 185 then the user process might gain a privilege or the generated core file
 186 was owned by a superuser.
 187
 188 Also aufs uses the system global workqueue ("events" kernel thread) too
 189 for asynchronous tasks, such like handling inotify/fsnotify, re-creating a
 190 whiteout base and etc. This is unrelated to a privilege.
 191 Most of aufs operation tries acquiring a rw_semaphore for aufs
 192 superblock at the beginning, at the same time waits for the completion
 193 of all queued asynchronous tasks.
 194
 195
 196 Whiteout
 197 ----------------------------------------------------------------------
 198 The whiteout in aufs is very similar to Unionfs's. That is represented
 199 by its filename. UnionMount takes an approach of a file mode, but I am
 200 afraid several utilities (find(1) or something) will have to support it.
 201
 202 Basically the whiteout represents "logical deletion" which stops aufs to
 203 lookup further, but also it represents "dir is opaque" which also stop
 204 lookup.
 205
 206 In aufs, rmdir(2) and rename(2) for dir uses whiteout alternatively.
 207 In order to make several functions in a single systemcall to be
 208 revertible, aufs adopts an approach to rename a directory to a temporary
 209 unique whiteouted name.
 210 For example, in rename(2) dir where the target dir already existed, aufs
 211 renames the target dir to a temporary unique whiteouted name before the
 212 actual rename on a branch and then handles other actions (make it opaque,
 213 update the attributes, etc). If an error happens in these actions, aufs
 214 simply renames the whiteouted name back and returns an error. If all are
 215 succeeded, aufs registers a function to remove the whiteouted unique
 216 temporary name completely and asynchronously to the system global
 217 workqueue.
 218
 219
 220 Copy-up
 221 ----------------------------------------------------------------------
 222 It is a well-known feature or concept.
 223 When user modifies a file on a readonly branch, aufs operate "copy-up"
 224 internally and makes change to the new file on the upper writable branch.
 225 When the trigger systemcall does not update the timestamps of the parent
 226 dir, aufs reverts it after copy-up.