home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_200 / 233_01 / dskrpk.doc < prev    next >
Text File  |  1987-06-30  |  9KB  |  226 lines
  1.                    Directory Repack
  2.  
  3.      Directory repack is written in 'C' and compiled against
  4. specifically Supersoft 'C'. Since Supersoft 'C' uses floating
  5. point functions to perform math, this program will not compile
  6. on other 'C' packages unless modifications are made to the source.
  7. Directory repack stored as DSKRPK.ARC contains the following files:
  8.  
  9.          DSKRPK.DOC ----- DESCRIPTION OF THE PROGRAM
  10.          DSKRPK.EXE ----- THE EXECUTABLE CODE
  11.          DSKRPK.C   ----- THE SOURCE CODE
  12.  
  13.       This program can be run as follows:
  14.  
  15.             dskrpk [drive spec] ---- where drive spec is optional.
  16.  
  17.      The purpose of dskrpk is to pack the root and all subdirectories.
  18. Packing simply removes all deleted files from the approiate directory
  19. cluster, moving valid entries up leaving no holes. In effect deleted
  20. files are scrubbed form the directory. New files are written on
  21. the end of the directory rather than embedded in previously deleted
  22. areas.
  23.  
  24.      I have included the source for this program such that any
  25. interested parties can update or just learn about file storage using
  26. the direct method of file access. The source file depicts Supersofts
  27. method of merging assembly language code into 'C' directly.
  28.  
  29.      The program has been tested against DSDD floppies, 10mb hard
  30. disks, and buffers are configured to handle up to 20mb drives.
  31. The program was developed to gain understanding of the MSDOS file
  32. structures, FATS, and directory/subdir organization. The experienced
  33. gained with this code will aid in the creation of another program
  34. which will analyze and unfragment the disk data area. Unfragmenting
  35. the data area organizes all files on continous sectors such that
  36. head movement is kept low leading to faster disk I/O.
  37.  
  38.      A word about public domain software. Program development is
  39. a long process taking many hours of research as well as development
  40. and debug.  I hope you will support our efforts by sending a small
  41. contribution of $5.00 to :
  42.  
  43.                   TPGS INC.
  44.                   14 Wells Road
  45.                   Flemington,NJ 08822
  46.                   data 201-782-7640
  47.                   voice 201-782-0639
  48.  
  49. * Exploring MSDOS file structures
  50. Richard a. Karas
  51. Fido 107/29
  52.  
  53.           Exploring MSDOS File Structures
  54.  
  55. Disks (floppy as well as hard's) are formatted or
  56. initialized under MSDOS Version 2.o to allow  fast and
  57. convenient access to files. MSDOS supports several methods
  58. of accessing files. The handle method, the File Control
  59. Block method, and the direct access method through
  60. directory and the File Allocation Table (FAT) search. The
  61. handle and FCB methods require you to access files
  62. through the operating system and their respective
  63. function calls, while the direct method enables you
  64. to access files as it implies, directly. To access
  65. files directly, a little knowledge of the way MSDOS
  66. formatts the disk is required.   MSDOS disks after
  67. formatting contain the following structures in
  68. sequence:
  69.  
  70. o  Reserve boot loader area.
  71.  
  72. o  First copy of the FAT.
  73.  
  74. o  Second copy of the FAT ( for recovery purposes).
  75.  
  76. o  Root directory.
  77.  
  78. o  Data area.
  79.  
  80. Utility programs read the reserved boot area where
  81. disk media data may be found. This data provides
  82. the program with information about the device.
  83. Typically byte offsets 11 through 29 have been set
  84. aside to define all the necessary attributes required.
  85.  
  86. Disk space is allocated in the data area only when
  87. required and is accomplished in one allocation unit
  88. at a time. An allocation unit is refered to as a cluster
  89. and is represented by one or more consecutive sectors.
  90. A sector is usually 512 bytes. A cluster will contain
  91. from 1 to x sectors depending upon the media. Some
  92. typical allocations are:
  93.  
  94. o  Double sided floppies 2 sectors/cluster.
  95.  
  96. o  10mb hard 8 sectors/cluster.
  97.  
  98. o  20mb hard 16 sectors/cluster.
  99.  
  100. This method of storage presents some problems
  101. to the  user (especially those running BBS systems)
  102. who store many small files.  Consider storing 100 files
  103. of text containing approximately  200 bytes each file
  104. on a 10mb hard disk (Like Fido stores messages). Figuring
  105. 8 sectors/cluster X 512 bytes/sector = 4096 bytes per
  106. allocation unit.  100 allocation units would be needed
  107. (providing each file only needs one allocation unit each)
  108. at 4K per representing 400K bytes of storage for 100 files.
  109. You are only actually storing 200 bytes X 100 files or
  110. 20K bytes of data ( a very big waste of space). DOS 3.1
  111. attempts to solve this problem by allowing the user
  112. to define the cluster size. Enough about problems,
  113. back to file storage techniques using the direct method
  114. (reference back Fido news issue).
  115.  
  116. When information is written to the disk, the system
  117. looks for the cluster that is closest to the beginning
  118. of the data area and available.  This criteria can
  119. easily be fulfilled by checking the FAT. The FAT maps
  120. every cluster of the data area and is in fact a large
  121. linked list to files occupying more than one cluster.
  122. FAT data is stored 1.5 bytes per cluster, with cluster #2
  123. defined as the start of the data area. The first two FAT
  124. entries represent system data, entry 3 through X actually
  125. map the entire disk.  The value of each FAT entry could be
  126. one of the following:
  127.  
  128. o  000H       Unused cluster.
  129.  
  130. o  002H-ff6H  Next cluster of data.
  131.  
  132. o  ff7H       Bad cluster.
  133.  
  134. o  ff8H-fffH  Last cluster of file.
  135.  
  136. The root directory is initially built at the time of disk
  137. format. It is a fixed value of clusters depending upon the
  138. size of the media. Each directory entry is 32 bytes in
  139. length and contains information required by the system to
  140. locate files.  Since directories other than the root
  141. directory are actual files, there is no limit to the
  142. number of entries they may contain.  Reference the DOS
  143. manual for a complete description of the fields of
  144. a directory entry.  For now all that you should know
  145. is that fields 00-07H contain the file name, 08-0aH
  146. contain the extension, and 1a-1bH contain the starting
  147. cluster number.
  148.  
  149. The following brief discussion describes file access
  150. using the direct method (assume root directory only):
  151.  
  152. 1.  The media data is read to obtain the necessary
  153. information as to number of sectors, where the
  154. root dir starts, how big it is, etc.
  155.  
  156. 2.  The Root directory is read.
  157.  
  158. 3.  Each 32 byte entry is scanned until the correct
  159. file is located.
  160.  
  161. 4.  The starting cluster number at offset 1a/1bH of
  162. that directory entry is obtained and converted
  163. to logical sector number.
  164.  
  165. 5.  X number of sectors per allocation is read to a
  166. transfer address starting at the sector calculated
  167. above. (X sect/allocation unit is a function of the
  168. media).
  169.  
  170. 6.  Next the FAT map is checked to see if additional
  171. clusters must be read. This is accomplished by
  172. converting the cluster just read from the directory
  173. entry to an offset value into the FAT. If the 1.5
  174. bytes representing the starting cluster contains
  175. data pointing to addiional clusters, the system
  176. will read that cluster.  This next mapped cluster
  177. entry will be checked and the process will continue
  178. until the last cluster is read.
  179.  
  180.  
  181. The following visually represents the process:
  182.  
  183.                   DIRECTORY (Entry #3)
  184.     ___________________________________________________
  185.    |     |     | Name.ext      |                   |    |
  186.    |  1  |  2  | start cluster----                 | X  |
  187.    |_____|_____|_____etc.______|_|_________________|____|
  188.                                  |
  189.                       ___________|______
  190.                      |                  |
  191.             _________|  Routine to      |
  192.            |         |  access data     |
  193.            |         |__________________|
  194.            |
  195.   _________|_
  196.  |          |
  197.  |          |         FILE ALLOCATION TABLE
  198.  |  ______2_|_____________5__________________________X__
  199.  | |     |     |        |    |                     |    |
  200.  | | sys |  5  |        | FFF|                     |    |
  201.  | |_____|_____|________|____|_____________________|____|
  202.  |           |_____________|
  203.  |
  204.  |____             DATA AREA
  205.  |  _|__________________________________________________
  206.  | |     |     |           |  _ |                  |    |
  207.  | |  2  |  3  |           |  5 |                  | X  |
  208.  | |_____|_____|___________|____|__________________|____|
  209.  |___________________________|
  210.  
  211.  
  212. The conversion of cluster number to logical sector and
  213. determining the byte offest into the FAT is simple. The
  214. method is written in any DOS manual near the system
  215. calls section. One trick which is not mentioned is that
  216. the formula to determine offset into the FAT table
  217. will only work if you operate on the table as if each
  218. byte were an entry ( that is if you read the table as
  219. bytes, and not words).
  220.  
  221. I hope this small article has been of some help to
  222. the readers in understanding some of the file storage
  223. techniques of the MSDOS operating system. One example
  224. of using this method of file access is depected in
  225. the public domain 'C' program DSKRPK.ARC located on
  226. Fido 107/29.