Date: Mon, 5 Feb 1996 17:47:48 +0100 (MET) From: Luigi Rizzo <luigi@labinfo.iet.unipi.it> To: rnordier@iafrica.com (Robert Nordier) Cc: hackers@freebsd.org Subject: Re: Some thoughts on FAT filesystems Message-ID: <199602051647.RAA21430@labinfo.iet.unipi.it> In-Reply-To: <199602051456.QAA00587@eac.iafrica.com> from "Robert Nordier" at Feb 5, 96 04:56:09 pm
next in thread | previous in thread | raw e-mail | index | archive | help
> On Mon, 5 Feb 1996, Luigi Rizzo wrote: > > > Assuming a cluster size of 4K (which is nice > > because it has the same size as a page), then a 4K portion of the > > FAT suffices for 8MB of data. > > OK. Giving 2048 clusters per group and one 16-bit (presumably) FAT > portion per CG. But where is the FAT located: next to the CG, or at > the start of the partition? the real FAT must be at the beginning of the partition. A copy can be located next to the CG. > > (Apparently next to the CG -- see below.) > > > For efficiency, when the FS loads this FAT portion in memory (or > > at the first write) it could also build a "free list" of clusters > > in the CG, so as to speed up allocations. > > Would a free list hold any advantage? Why not just scan your FAT > copy for the next 0 (ie. free cluster)? This could be handled using > a single 80x86 'scas' op. Don't event think about it: non portable machine code, trashing the cache with many useless memory accessess... :) The free list gives you constant time access to a free block. > > Also for efficiency, > > writes to the FAT should not be done too frequently, because of > > their cost. > > Write to disk, presumably. So are we controlling caching ourselves? yes if we can. Otherwise, resort to the LRU cache of memory pages. > > When creating new files, one should privilege locality within the > > CG, much like it is done in the FFS. Of course, when the CG fills > > up, or the disk is heavily fragmented (read: has been written by > > DOS) one might have to use blocks in different CGs. > > How are you planning to link the CG chain from one FAT to another? they are part of a same file, see the description under "RECOVERY" > > CACHING and WRITES: > > The caching policy might not be much different from that of FFS: try to > > keep in memory the FAT copies first, do not immediately go to the disk > > for data blocks as they might have a short lifetime, etc. > > > RECOVERY: > > using delayed writes to the FAT might lead to bad inconsistencies to > > the filesystem in case of power failures. One possible approach could > > be the following: > > 1) create a "special" file in the root directory, with fixed size and > > structure. This file uses exactly one cluster per CG, say at the > > beginning of the CG, where the portion of the FAT for that CG is > > saved. > > Is this (effectively) the second copy of the FAT? Next to the first? > > > Writing to this cluster is cheaper than writing to the FAT > > because of physical contiguity. > > I don't get it. Aren't they next to each other? > > > Also, there is no risk of corruption > > of this file because its structure does not change, hence > > modifications to its content do not require changing the FAT or the > > directory entry (unless one wants to update the modification times; > > but this is not very important). > > I still don't see what this file gets you that a FAT copy doesn't. (How > is a file of unchanging structure/size any different from a FAT?) You > could just as well say, "No risk of corruption to the FAT, because > modifications do not require changing the FAT." Or not? > > > 2) When the FS is updated, modifications to the FAT are written to this > > local FAT first, and then, at a convenient time, dumped to the > > ordinary FAT. > > Do the FAT portions (collectively) constitute the ordinary FAT? > > > 3) Recovery after a crash: first check for the existence of the > > "special" file, then look for inconsistencies between the regular > > FAT and this special file, and try to reconstruct things. > > Still seems just like two FAT copies to me. > > > Not many new ideas, as you can see, just trying to see if known > > technology can be reused. > > I'm probably missing something obvious, but I don't quite see how it all > ties together.... I'll try to rephrase it: some utility program creates a special file, called "C:\FASTFAT" with the following features: + same size as a single FAT; + its clusters are spread in the disk, one at the beginning of each CG + its size does not change with time. C:\FASTFAT contains a verbatim copy of the FAT. The fast FAT filesystem tries to keep FAT blocks in memory, writes critical things to C:\FASTFAT (of use during recoveries) and updates the standard FATs (those at the beginning of the disk) every 30 seconds or whenever a sync() is requested. If the system does not crash, C:\FASTFAT for an umounted filesystem contains the same data of the two FATs on the disk. If there is a crash, C:\FASTFAT, if it exists, should contain more up-to-date information (there is no danger to loose C:\FASTFAT because it is at fixed locations and its structure does not change with time). Did I make it sufficiently clear now ? Luigi ==================================================================== Luigi Rizzo Dip. di Ingegneria dell'Informazione email: luigi@iet.unipi.it Universita' di Pisa tel: +39-50-568533 via Diotisalvi 2, 56126 PISA (Italy) fax: +39-50-568522 http://www.iet.unipi.it/~luigi/ ====================================================================
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199602051647.RAA21430>