home *** CD-ROM | disk | FTP | other *** search
/ PC-Online 1996 May / PCOnline_05_1996.bin / linux / source / kernel-s / v1.1 / umsdos-0.001 < prev    next >
Text File  |  1995-10-10  |  6KB  |  167 lines
  1. UMSDOS is part of the kernel distribution (since 1.1.36). Many
  2. have complained that it was somewhat slow. Many more accepted that
  3. it had to be slow, but so useful: acceptable tradeoff.
  4.  
  5. Good news! There was a very good reason why Umsdos (and msdos fs)
  6. was slow. This is history :-)
  7.  
  8. I will explain why it was slow, how I solve it, give some benchmarks
  9. and tell you what you can do to help me test it.
  10.  
  11. Please note that I am already running this on my production
  12. machine, so it surely works! It is fully compatible with the
  13. umsdos 0.3 file layout.
  14.  
  15. History:
  16. ========
  17.  
  18. Umsdos run piggyback on the Msdos file system driver written
  19. a long long time ago by Werner Almesberger. It was rock
  20. solid when I started Umsdos back in november 1992. At that
  21. time the buffer cache of Linux was only manipulating 1k blocks.
  22.  
  23. It simply splits a disk in 1k blocks and there were no mean for
  24. a file system driver to read or write anything else than full
  25. block. Since blocks are 1k large (2 512 bytes disk sector), each
  26. start on an even sector number.
  27.  
  28. The FAT msdos file system organises files in clusters. Clusters
  29. are generally 2k, 4k or 8k on a hard drive. And here is the
  30. bad news. The first cluster on a hard drive start on an odd sector
  31. number. This produces this strange relation
  32.  
  33.                 |--- B1---|--- B2---|--- B3---|--- B4---|--- B5---|
  34. linux blocks    |-S1- -S2-|-S1- -S2-|-S1- -S2-|-S1- -S2-|-S1- -S2|
  35. DOS clusters     -S4-|-S1- -S2- -S3- -S4-|-S1- -S2- -S3- -S4-|
  36.                      |-------file1-------|-------file2-------|
  37.  
  38. So one DOS cluster (2k) span 2 1k blocks ? Wrong! it spans 3. For
  39. example, one cluster of "file1" touch the half end of "B1"
  40. "B2" completly and the first half of block "B3".
  41.  
  42. Given the fact that the msdos driver in linux can only read or write
  43. whole 1k block, we get the following problem. Here are the operations
  44. needed to write a full cluster of "file1".
  45.  
  46.     read B1
  47.     fill the last half of B1 with the first sector of the cluster
  48.     write B1
  49.     write B2 with sector 2 and 3 of the clustor
  50.     read B3
  51.     fill the first half of B3 with sector 4 of the cluster
  52.     write B3
  53.  
  54. It has to be like this because, for one, the first sector of block
  55. B1 may belong to another file. The current msdos file system driver
  56. do read every sector before writing it. This is what kills performance.
  57.  
  58. The fix:
  59. --------
  60.  
  61. At the time the msdos fs was done, linux was not flexible enough.
  62. Now it is possible to control at the file system level the size
  63. of the blocks in the buffer cache, and this for each file system.
  64. independantly.
  65.  
  66. The trick was rather simple: Use a block size of 512. A 2k cluster
  67. will then span 4 full blocks. If we overwrite completly a cluster
  68. we have no need to read any block from the disk.
  69.  
  70. This fix has numerous advantages beside speed.
  71.  
  72.     It makes the msdos fs simpler.
  73.     It make "bmap" always available, so
  74.         No special mmap handling anymore.
  75.             Use less memory to run programs because
  76.             they run directly in the buffer cache.
  77.         No special trick for swap file.
  78.         LILO can be used in a msdos fs (I have not tried it though).
  79.             Very useful for those who use OS/2 and Linux in the same
  80.             partition.
  81.  
  82. I have also introduced some support for read ahead. Most of the
  83. changes were done in linux/fs/msdos/*.c
  84.  
  85. I have made the minimal changes requiered to make both umsdos and
  86. the msdos fs loadable modules. This is included in the patch.
  87.  
  88. Some benchmarks:
  89. ---------------
  90.  
  91. I did not do very scientific benchmarks. I have made many tests
  92. and many measurements. I think that one test I have done reflects
  93. the real benefit of my work. I have simply done a recursive copy
  94. of the linux kernel (with object files) into another directory.
  95. This test excercise different things
  96.  
  97.     Copy a large number of small file (958)
  98.         A lot of file creation, lot of access time
  99.         update.
  100.     Copy a large amount of data (10meg) so
  101.         So real disk activity has to occur (overrun the cache)
  102.  
  103. To give an idea, I have also run the test on DOS and OS/2
  104. on exactly the same data (same partition, same everything,
  105. different utilities though).
  106.  
  107. Here are the results. Test1 demontrates a copy to a target
  108. directory in the same partition. Test2 use a target directory
  109. in a different partition, forcing longer seek of the disk.
  110. The results are in seconds.
  111.  
  112.                                     test1       test2
  113.  
  114. DOS with BUFFER=50                  117         124
  115. Standard umsdos 0.4 in 1.1.57       99          136
  116. OS/2 with 1024k disk cache          70
  117. DOS with disk cache                 58          46
  118.     (hyperdisk with 1024k)
  119. New improve Umsdos 0.5              43          43
  120. New improve msdos                   32          32
  121.  
  122. On DOS and OS/2 I have use xcopy. On linux, I have used
  123. "tar cf - linux | (cd dir; tar xvf -)". You will note that
  124. I have used the v option for the second tar to be fair, since
  125. xcopy has no silent mode. I did get the same result
  126. with a "cp -R ..." however.
  127.  
  128. As you see, the performance improvement is drastic, especially
  129. for test2. I suspect this is the typical case, where you read
  130. something from one end of the disk and write something else
  131. away on the disk. Umsdos 0.4, by forcing a read before write
  132. was defeating the usefulness of the cache (delay write). As you
  133. see, test2 and test1 give the same result with umsdos 0.5.
  134.  
  135. I did not include results from EXT2. I had little time to
  136. do a fair test. My little attempt to replicate the condition
  137. of the test in a EXT2 partition have shown that EXT2 was slower
  138. both for reading and writing. Much slower... I have no explanation
  139. for this.
  140.  
  141. I would be nice to run a nice serious benchmark suite. From my
  142. benchmark we can only conclude that Umsdos is not slow anymore.
  143.  
  144. How to test it ?
  145. ---------------
  146.  
  147. I have upload the following files to
  148. sunsite.unc.edu:/pub/Linux/ALPHA/umsdos
  149.  
  150.     umsdos-0.5-diff
  151.     umsdos-0.5-diff.lsm
  152.     umsdos-0.5-diff.README (this text).
  153.  
  154. The patch was made relative to 1.1.57 + small notify_change
  155. buglet fix. Get the latest kernel (1.1.59) kernel and apply
  156. the patch
  157.  
  158.     cd /usr/src/linux
  159.     patch -p1 </usr/src/umsdos-0.5-diff
  160.  
  161. run it, beat it, test it and please email me about anything
  162. even to say "hello, it works".
  163.  
  164. Keep in mind that this is "file system stuff". A backup is always
  165. a good idea.
  166.  
  167.