Return to BSD News archive
Path: euryale.cc.adfa.oz.au!newshost.anu.edu.au!harbinger.cc.monash.edu.au!news.cs.su.oz.au!inferno.mpx.com.au!goliath.apana.org.au!news.syd.connect.com.au!news.mel.connect.com.au!munnari.OZ.AU!news.ecn.uoknor.edu!news.ysu.edu!usenet.ins.cwru.edu!gatech!usenet.eel.ufl.edu!newsfeed.internetmci.com!swrinde!sdd.hp.com!hamblin.math.byu.edu!park.uvsc.edu!usenet
From: Terry Lambert <terry@lambert.org>
Newsgroups: comp.unix.bsd.freebsd.misc,comp.os.linux.misc
Subject: Re: Filesystem fragmentation
Date: 13 Feb 1996 02:31:23 GMT
Organization: Utah Valley State College, Orem, Utah
Lines: 74
Message-ID: <4fot5r$art@park.uvsc.edu>
References: <4f1j28$et1@news1.halcyon.com> <31151A16.524C07ED@trenton.edu>
NNTP-Posting-Host: hecate.artisoft.com
Xref: euryale.cc.adfa.oz.au comp.unix.bsd.freebsd.misc:14156 comp.os.linux.misc:87886
Mark Neill <neill@trenton.edu> wrote:
>
> Tim Smith wrote:
> >
> > My understanding is that both FreeBSD (and BSD in general) and Linux
> > filesystems are resistant to becoming fragmented. Still, suppose I
> > ran a program that did the following:
[ ... attempt at an algorithm (incorrectly) thought to be likely
to cause fragmentation ... ]
There is fragmentation, and there is fragmentation.
One type of fragmentation is unused percentage of allocation
units on disk.
UFS is *highly* resistant to this type of fragmentation, because
it has sub-block-sized allocation units (you can, of course,
override this when building a file system if you intentionally
want to build a fragable FS... just as you can shhot yourself
in the foot by aming a gun at it and pulling the trigger; in both
cases, you must intend the injury for it to occur).
The second type of fragmentation is based on how much time it
takes to get the next block in a sequential operation.
UFS has clusters and it has cylinder groups to resolve this
problem.
It is possible to build a file system with a single cylinder
group; floppies are typically built this way, as media which
is typically used for transportation or archival, not active
storage (we are back to aiming at our foot here).
Both cylinder groups and clusters can fail when the usability
of the hashed allocation policy drops below a certain "acceptable"
amount. Typically, this happens when a file system is full --
that is, the file system iself is "full" and then the (default: 8%)
reserve is intentioanlly exhauseted by the administrator.
Files created during this intentional misuse of the file system
are created in hash collision conditions, and are not as
efficiently laid out. The system warns of this by syslog'ing
a message to the effect "changing from time to space optimization"
(and back, if the administrator regains his or her senses).
The "defragmentation" procedure for the files created during
the "failure" periods (easily identified by a bounded "find"
given the system log files to identify modification time ranges)
is to free up space on the drive so that the hash is once again
efficient, and then simply copy the files, deleting the original
file afterward, and renaming the file back. Since the allocation
by the copy program will occur in non hash-starvation circumstances,
the files will be "fixed".
This is all described in the original FFS paper on the Usenix
FTP server, ftp.sage.usenix.org, and has been available in one
form or another since 1985 or earlier -- more than 10 *years*.
For information on why hash algorithm efficiency decreases to
an unacceptable level after a certain "fill" is reached, I
suggest reading Knuth's "Sorting and Searching".
Terry Lambert
terry@cs.weber.edu
---
Any opinions in this posting are my own and not those of my present
or previous employers.