home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / os / linux / 9511 < prev    next >
Encoding:
Text File  |  1992-08-31  |  2.5 KB  |  64 lines
  1. Newsgroups: comp.os.linux
  2. Path: sparky!uunet!munnari.oz.au!news.hawaii.edu!spectra!oles
  3. From: oles@spectra (Shawn Oles)
  4. Subject: Re: Stacker like file system
  5. Message-ID: <1992Aug31.204242.5948@news.Hawaii.Edu>
  6. Sender: root@news.Hawaii.Edu (News Service)
  7. Nntp-Posting-Host: spectra.eng.hawaii.edu
  8. Organization: University of Hawaii, Dept. of Electrical Engineering
  9. References: <1992Aug28.075627.13395@infko.uucp> <BtpF3M.2xn.2@cs.cmu.edu> <1992Aug31.124612.1328@ifi.informatik.uni-stuttgart.de>
  10. Date: Mon, 31 Aug 1992 20:42:42 GMT
  11. Lines: 51
  12.  
  13. In article <1992Aug31.124612.1328@ifi.informatik.uni-stuttgart.de> weberj@dia.informatik.uni-stuttgart.de (Weber) writes:
  14. >I think there is a way to implement a stacker like file
  15. >system without having to change much of the kernel.
  16. >
  17. >Hook the low-level routines for reading/writing one block
  18. >from/to disk and insert a compression algorithm between.
  19. >
  20. > natural-size  -----> compression ----> compressed block
  21. >               <----- decompression <--
  22. >
  23. >blocks have a "random" size <= 4K and you encounter the same
  24. >problems as with memory management. To write you have to look
  25. >for a fitting free space on the free list by doing some of the
  26. >XXX-fit strategies. If there is not enough free space at one
  27. >continuous location you even may have to do a kind of garbage 
  28. >collection.
  29.  
  30. You hit the nail on the head.   Indeed, variable sized blocks is
  31. what makes a compressed file system harder then a normal files system.
  32.  
  33. In ACF (automatically compressed format) I am handling this by 
  34. allocating what I call mini-blocks to represent the compressed block.
  35. Right now I divide each physical block up into 8 mini-blocks.  
  36. Mini-blocks are clustered together into a sector, which is made 
  37. up of 8 blocks or 64 mini-blocks.
  38.  
  39. A compressed block is represented by a sector pointer, and up to 8
  40. mini-blocks which are all allocated within the same sector.   An in
  41. core sector map containing the availability of mini-blocks is
  42. maintained for each sector. (This suplements a bit map structure,
  43. which is used to allocate the actual mini-blocks. 1bit for each
  44. miniblock).
  45.  
  46. A smaller mini-block size might be appropriate, but this is tunable
  47. parameter.  I think stacker uses a similar scheme, but there are
  48. 16 mini-blocks in a real block. 
  49.  
  50. >But what should df tell? I think the double of the physical
  51.  
  52. You can predict the availability of free space by maintaining
  53. the current compression stats;
  54. >-- 
  55. >
  56. >Juergen G. Weber
  57. >Student am Institut fuer Informatik
  58. >Universitaet Stuttgart - Germany
  59.  
  60.  
  61. -- 
  62.  
  63. -shawn
  64.