The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/ufs/ffs/

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

Name Size Last modified (GMT) Description
Back Parent directory 2023-01-29 20:54:29
File README 15059 bytes 2023-01-29 20:54:29
File README.softupdates 717 bytes 2023-01-29 20:54:29
C file ffs_alloc.c 46742 bytes 2023-01-29 20:54:29
C file ffs_balloc.c 10706 bytes 2023-01-29 20:54:29
C file ffs_extern.h 5815 bytes 2023-01-29 20:54:29
C file ffs_inode.c 15422 bytes 2023-01-29 20:54:29
C file ffs_softdep.c 134453 bytes 2023-01-29 20:54:29
C file ffs_softdep_stub.c 5621 bytes 2023-01-29 20:54:29
C file ffs_subr.c 6381 bytes 2023-01-29 20:54:29
C file ffs_tables.c 5873 bytes 2023-01-29 20:54:29
C file ffs_vfsops.c 34084 bytes 2023-01-29 20:54:29
C file ffs_vnops.c 7679 bytes 2023-01-29 20:54:29
C file fs.h 21986 bytes 2023-01-29 20:54:29
C file softdep.h 27527 bytes 2023-01-29 20:54:29

    1 Introduction
    2 
    3 This package constitutes the alpha distribution of the soft update
    4 code updates for the fast filesystem.
    5 
    6 For More information on what Soft Updates is, see:
    7 http://www.ece.cmu.edu/~ganger/papers/CSE-TR-254-95/
    8 
    9 Status
   10 
   11 My `filesystem torture tests' (described below) run for days without
   12 a hitch (no panic's, hangs, filesystem corruption, or memory leaks).
   13 However, I have had several panic's reported to me by folks that
   14 are field testing the code which I have not yet been able to
   15 reproduce or fix. Although these panic's are rare and do not cause
   16 filesystem corruption, the code should only be put into production
   17 on systems where the system administrator is aware that it is being
   18 run, and knows how to turn it off if problems arise. Thus, you may
   19 hand out this code to others, but please ensure that this status
   20 message is included with any distributions. Please also include
   21 the file ffs_softdep.stub.c in any distributions so that folks that
   22 cannot abide by the need to redistribute source will not be left
   23 with a kernel that will not link. It will resolve all the calls
   24 into the soft update code and simply ignores the request to enable
   25 them. Thus you will be able to ensure that your other hooks have
   26 not broken anything and that your kernel is softdep-ready for those
   27 that wish to use them. Please report problems back to me with
   28 kernel backtraces of panics if possible. This is massively complex
   29 code, and people only have to have their filesystems hosed once or
   30 twice to avoid future changes like the plague. I want to find and
   31 fix as many bugs as soon as possible so as to get the code rock
   32 solid before it gets widely released. Please report any bugs that
   33 you uncover to mckusick@mckusick.com.
   34 
   35 Performance
   36 
   37 Running the Andrew Benchmarks yields the following raw data:
   38 
   39         Phase   Normal  Softdep     What it does
   40           1       3s      <1s       Creating directories
   41           2       8s       4s       Copying files
   42           3       6s       6s       Recursive directory stats
   43           4       8s       9s       Scanning each file
   44           5      25s      25s       Compilation
   45 
   46         Normal:  19.9u 29.2s 0:52.8 135+630io
   47         Softdep: 20.3u 28.5s 0:47.8 103+363io
   48 
   49 Another interesting datapoint are my `filesystem torture tests'.
   50 They consist of 1000 runs of the andrew benchmarks, 1000 copy and
   51 removes of /etc with randomly selected pauses of 0-60 seconds
   52 between each copy and remove, and 500 find from / with randomly
   53 selected pauses of 100 seconds between each run). The run of the
   54 torture test compares as follows:
   55 
   56 With soft updates: writes: 6 sync, 1,113,686 async; run time 19hr, 50min
   57 Normal filesystem: writes: 1,459,147 sync, 487,031 async; run time 27hr, 15min
   58 
   59 The upshot is 42% less I/O and 28% shorter running time.
   60 
   61 Another interesting test point is a full MAKEDEV. Because it runs
   62 as a shell script, it becomes mostly limited by the execution speed
   63 of the machine on which it runs. Here are the numbers:
   64 
   65 With soft updates:
   66 
   67         labrat# time ./MAKEDEV std
   68         2.2u 32.6s 0:34.82 100.0% 0+0k 11+36io 0pf+0w
   69 
   70         labrat# ls | wc
   71              522     522    3317
   72 
   73 Without soft updates:
   74 
   75         labrat# time ./MAKEDEV std
   76         2.0u 40.5s 0:42.53 100.0% 0+0k 11+1221io 0pf+0w
   77 
   78         labrat# ls | wc
   79              522     522    3317
   80 
   81 Of course, some of the system time is being pushed
   82 to the syncer process, but that is a different story.
   83 
   84 To show a benchmark designed to highlight the soft update code
   85 consider a tar of zero-sized files and an rm -rf of a directory tree
   86 that has at least 50 files or so at each level. Running a test with
   87 a directory tree containing 28 directories holding 202 empty files
   88 produces the following numbers:
   89 
   90 With soft updates:
   91 tar: 0.0u 0.5s 0:00.65 76.9% 0+0k 0+44io 0pf+0w (0 sync, 33 async writes)
   92 rm: 0.0u 0.2s 0:00.20 100.0% 0+0k 0+37io 0pf+0w (0 sync, 72 async writes)
   93 
   94 Normal filesystem:
   95 tar: 0.0u 1.1s 0:07.27 16.5% 0+0k 60+586io 0pf+0w (523 sync, 0 async writes)
   96 rm:  0.0u 0.5s 0:01.84 29.3% 0+0k 0+318io 0pf+0w (258 sync, 65 async writes)
   97 
   98 The large reduction in writes is because inodes are clustered, so
   99 most of a block gets allocated, then the whole block is written
  100 out once rather than having the same block written once for each
  101 inode allocated from it.  Similarly each directory block is written
  102 once rather than once for each new directory entry. Effectively
  103 what the update code is doing is allocating a bunch of inodes
  104 and directory entries without writing anything, then ensuring that
  105 the block containing the inodes is written first followed by the
  106 directory block that references them.  If there were data in the
  107 files it would further ensure that the data blocks were written
  108 before their inodes claimed them.
  109 
  110 Copyright Restrictions
  111 
  112 Please familiarize yourself with the copyright restrictions
  113 contained at the top of either the sys/ufs/ffs/softdep.h or
  114 sys/ufs/ffs/ffs_softdep.c file. The key provision is similar
  115 to the one used by the DB 2.0 package and goes as follows:
  116 
  117     Redistributions in any form must be accompanied by information
  118     on how to obtain complete source code for any accompanying
  119     software that uses the this software. This source code must
  120     either be included in the distribution or be available for
  121     no more than the cost of distribution plus a nominal fee,
  122     and must be freely redistributable under reasonable
  123     conditions. For an executable file, complete source code
  124     means the source code for all modules it contains. It does
  125     not mean source code for modules or files that typically
  126     accompany the operating system on which the executable file
  127     runs, e.g., standard library modules or system header files.
  128 
  129 The idea is to allow those of you freely redistributing your source
  130 to use it while retaining for myself the right to peddle it for
  131 money to the commercial UNIX vendors. Note that I have included a
  132 stub file ffs_softdep.c.stub that is freely redistributable so that
  133 you can put in all the necessary hooks to run the full soft updates
  134 code, but still allow vendors that want to maintain proprietary
  135 source to have a working system. I do plan to release the code with
  136 a `Berkeley style' copyright once I have peddled it around to the
  137 commercial vendors.  If you have concerns about this copyright,
  138 feel free to contact me with them and we can try to resolve any
  139 difficulties.
  140 
  141 Soft Dependency Operation
  142 
  143 The soft update implementation does NOT require ANY changes
  144 to the on-disk format of your filesystems. Furthermore it is
  145 not used by default for any filesystems. It must be enabled on
  146 a filesystem by filesystem basis by running tunefs to set a
  147 bit in the superblock indicating that the filesystem should be
  148 managed using soft updates. If you wish to stop using
  149 soft updates due to performance or reliability reasons,
  150 you can simply run tunefs on it again to turn off the bit and
  151 revert to normal operation. The additional dynamic memory load
  152 placed on the kernel malloc arena is approximately equal to
  153 the amount of memory used by vnodes plus inodes (for a system
  154 with 1000 vnodes, the additional peak memory load is about 300K).
  155 
  156 Kernel Changes
  157 
  158 There are two new changes to the kernel functionality that are not
  159 contained in in the soft update files. The first is a `trickle
  160 sync' facility running in the kernel as process 3.  This trickle
  161 sync process replaces the traditional `update' program (which should
  162 be commented out of the /etc/rc startup script). When a vnode is
  163 first written it is placed 30 seconds down on the trickle sync
  164 queue. If it still exists and has dirty data when it reaches the
  165 top of the queue, it is sync'ed.  This approach evens out the load
  166 on the underlying I/O system and avoids writing short-lived files.
  167 The papers on trickle-sync tend to favor aging based on buffers
  168 rather than files. However, I sync on file age rather than buffer
  169 age because the data structures are much smaller as there are
  170 typically far fewer files than buffers. Although this can make the
  171 I/O spikey when a big file times out, it is still much better than
  172 the wholesale sync's that were happening before. It also adapts
  173 much better to the soft update code where I want to control
  174 aging to improve performance (inodes age in 10 seconds, directories
  175 in 15 seconds, files in 30 seconds). This ensures that most
  176 dependencies are gone (e.g., inodes are written when directory
  177 entries want to go to disk) reducing the amount of rollback that
  178 is needed.
  179 
  180 The other main kernel change is to split the vnode freelist into
  181 two separate lists.  One for vnodes that are still being used to
  182 identify buffers and the other for those vnodes no longer identifying
  183 any buffers.  The latter list is used by getnewvnode in preference
  184 to the former.
  185 
  186 Packaging of Kernel Changes
  187 
  188 The sys subdirectory contains the changes and additions to the
  189 kernel. My goal in writing this code was to minimize the changes
  190 that need to be made to the kernel. Thus, most of the new code
  191 is contained in the two new files softdep.h and ffs_softdep.c.
  192 The rest of the kernel changes are simply inserting hooks to
  193 call into these two new files. Although there has been some
  194 structural reorganization of the filesystem code to accommodate
  195 gathering the information required by the soft update code,
  196 the actual ordering of filesystem operations when soft updates
  197 are disabled is unchanged.
  198 
  199 The kernel changes are packaged as a set of diffs. As I am
  200 doing my development in BSD/OS, the diffs are relative to the
  201 BSD/OS versions of the files. Because BSD/OS recently had
  202 4.4BSD-Lite2 merged into it, the Lite2 files are a good starting
  203 point for figuring out the changes. There are 40 files that
  204 require change plus the two new files. Most of these files have
  205 only a few lines of changes in them. However, four files have
  206 fairly extensive changes: kern/vfs_subr.c, ufs/ufs/ufs_lookup.c,
  207 ufs/ufs/ufs_vnops.c, and ufs/ffs/ffs_alloc.c. For these four
  208 files, I have provided the original Lite2 version, the Lite2
  209 version with the diffs merged in, and the diffs between the
  210 BSD/OS and merged version. Even so, I expect that there will
  211 be some difficulty in doing the merge; I am certainly willing
  212 to assist in helping get the code merged into your system.
  213 
  214 Packaging of Utility Changes
  215 
  216 The utilities subdirectory contains the changes and additions
  217 to the utilities. There are diffs to three utilities enclosed:
  218 
  219     tunefs - add a flag to enable and disable soft updates
  220 
  221     mount - print out whether soft updates are enabled and
  222             also statistics on number of sync and async writes
  223 
  224     fsck - tighter checks on acceptable errors and a slightly
  225            different policy for what to put in lost+found on
  226            filesystems using soft updates
  227 
  228 In addition you should recompile vmstat so as to get reports
  229 on the 13 new memory types used by the soft update code.
  230 It is not necessary to use the new version of fsck, however it
  231 would aid in my debugging if you do. Also, because of the time
  232 lag between deleting a directory entry and the inode it
  233 references, you will find a lot more files showing up in your
  234 lost+found if you do not use the new version. Note that the
  235 new version checks for the soft update flag in the superblock
  236 and only uses the new algorithms if it is set. So, it will run
  237 unchanged on the filesystems that are not using soft updates.
  238 
  239 Operation
  240 
  241 Once you have booted a kernel that incorporates the soft update
  242 code and installed the updated utilities, do the following:
  243 
  244 1) Comment out the update program in /etc/rc.
  245 
  246 2) Run `tunefs -n enable' on one or more test filesystems.
  247 
  248 3) Mount these filesystems and then type `mount' to ensure that
  249    they have been enabled for soft updates.
  250 
  251 4) Copy the test directory to a softdep filesystem, chdir into
  252    it and run `./doit'. You may want to check out each of the
  253    three subtests individually first: doit1 - andrew benchmarks,
  254    doit2 - copy and removal of /etc, doit3 - find from /.
  255 
  256 ====
  257 Additional notes from Feb 13
  258 
  259 hen removing huge directories of files, it is possible to get
  260 the incore state arbitrarily far ahead of the disk. Maintaining
  261 all the associated depedency information can exhaust the kernel
  262 malloc arena. To avoid this senario, I have put some limits on
  263 the soft update code so that it will not be allowed to rampage
  264 through all of the kernel memory. I enclose below the relevant
  265 patches to vnode.h and vfs_subr.c (which allow the soft update
  266 code to speed up the filesystem syncer process). I have also
  267 included the diffs for ffs_softdep.c. I hope to make a pass over
  268 ffs_softdep.c to isolate the differences with my standard version
  269 so that these diffs are less painful to incorporate.
  270 
  271 Since I know you like to play with tuning, I have put the relevant
  272 knobs on sysctl debug variables. The tuning knobs can be viewed
  273 with `sysctl debug' and set with `sysctl -w debug.<name>=value'.
  274 The knobs are as follows:
  275 
  276         debug.max_softdeps - limit on any given resource
  277         debug.tickdelay - ticks to delay before allocating
  278         debug.max_limit_hit - number of times tickdelay imposed
  279         debug.rush_requests - number of rush requests to filesystem syncer
  280 
  281 The max_softdeps limit is derived from vnodesdesired which in
  282 turn is sized based on the amount of memory on the machine.
  283 When the limit is hit, a process requesting a resource first
  284 tries to speed up the filesystem syncer process. Such a
  285 request is recorded as a rush_request. After syncdelay / 2 
  286 unserviced rush requests (typically 15) are in the filesystem
  287 syncers queue (i.e., it is more than 15 seconds behind in its 
  288 work), the process requesting the memory is put to sleep for
  289 tickdelay seconds. Such a delay is recorded in max_limit_hit.
  290 Following this delay it is granted its memory without further
  291 delay. I have tried the following experiments in which I
  292 delete an MH directory containing 16,703 files:
  293 
  294 Run #                   1               2               3
  295 
  296 max_softdeps         4496            4496            4496
  297 tickdelay        100 == 1 sec   20 == 0.2 sec   2 == 0.02 sec
  298 max_limit_hit    16 == 16 sec   27 == 5.4 sec   203 == 4.1 sec
  299 rush_requests         147             102              93
  300 run time             57 sec          46 sec          45 sec
  301 I/O's                 781             859             936
  302 
  303 When run with no limits, it completes in 40 seconds. So, the
  304 time spent in delay is directly added to the bottom line.
  305 Shortening the tick delay does cut down the total running time,
  306 but at the expense of generating more total I/O operations
  307 due to the rush orders being sent to the filesystem syncer.
  308 Although the number of rush orders decreases with a shorter
  309 tick delay, there are more requests in each order, hence the
  310 increase in I/O count. Also, although the I/O count does rise
  311 with a shorter delay, it is still at least an order of magnitude 
  312 less than without soft updates. Anyway, you may want to play
  313 around with these value to see what works best and to see if
  314 you can get an insight into how best to tune them. If you get
  315 out of memory panic's, then you have max_softdeps set too high.
  316 The max_limit_hit and rush_requests show be reset to zero
  317 before each run. The minimum legal value for tickdelay is 2
  318 (if you set it below that, the code will use 2).
  319 
  320 

[ source navigation ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.