Re: [PATCH V2 10/16] Squashfs: cache operations

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



Jörn Engel wrote:
On Wed, 29 October 2008 01:49:56 +0000, Phillip Lougher wrote:
+/*
+ * Blocks in Squashfs are compressed.  To avoid repeatedly decompressing
+ * recently accessed data Squashfs uses two small metadata and fragment caches.
+ *
+ * This file implements a generic cache implementation used for both caches,
+ * plus functions layered ontop of the generic cache implementation to
+ * access the metadata and fragment caches.
+ */

I tend to agree with Andrew that a lot of this should be done by the
page cache instead.  One of the problems seems to be that your blocksize
can exceed page size and there really isn't any infrastructure to deal
with such cases yet.  Bufferheads deal with blocks smaller than a page,
not the other way around.


I thought about using the page cache, but, the fact that blocksizes exceed the page cache size is only one of a number of reasons why I prefer the current solution, there is also simplicity and speed to consider.

There are three types of compressed block in Squashfs: datablocks, fragments, and metadata blocks. Of these datablocks (by far the largest number of blocks) are decompressed and pushed into the page cache, and are not otherwise cached by Squashfs. This, obviously (?), is because they contain data for only one file, and so at time of access there is a readily available address space to push the data into.

Metadata and fragment blocks are different in that when accessed and decompressed (say for an inode or for a particular tail-end block) they will contain metadata or tail-ends for other files. This data could be thrown away but due to locality of reference it makes sense to temporarily cache it in-case a near future file access references the data. But it doesn't make much sense to cache it more than temporarily, much of the data will probably not be reused, and it exists compressed in the buffer cache.

The squashfs cache is therefore designed to cache only the last couple of metadata and fragment blocks. It is also designed to be simple and extremely fast. The maximum size of the metadata cache is only 64 KiB.

Simplicity and speed is extremely important. The squashfs_metadata_read() wrapper around the cache is designed to step through the metadata a structure at a time (20 or so bytes), updating the read position in the metadata each call, with more metadata cache blocks being read and decompressed as necessary. The common case where the metadata is already in the cache (because we're stepping through it 20 or so bytes at a time), is designed to be extremely fast - a spinlock and array search only. I recently optimised the cache to use spinlocks rather than mutexes and reduced the lock holding time (necessary to move to spinlocks), and this resulted in a 20%+ speed improvement in reading squashfs filesystems.

Given the above using an address space in the page cache will result in greater complexity, more memory overhead, and much slower operation. There's a number of reasons for this.

1. The amount and life-span of the data stored in the page cache is outside of Squashfs' control. As explained above it only makes sense to temporarily cache the last couple of metadata and fragment blocks. Using the page cache (if a 'large' address space is used) for these keeps more of them around for longer than necessary, and will potentially cause more worthy datablocks to be flushed on memory pressure.

2. The address space will be caching uncompressed data, the squashfs references to this data are the compressed locations within the filesystem. There doesn't exist a one-to-one linear mapping from compressed location to decompressed location in the address space. This means a lookup table still needs to be used to store the mapping from compressed location to decompressed location in the address space. Now this lookup table (however implemented) is itself at least as complex as my current cache implementation.

3. Once the locations of the decompressed pages in the address space have been found, they'll need to be looked up in the page cache, and this has to be done for every 4K page. With the default fragment size of 128 KiB this means 32 separate lookups. Somewhat slower than one spinlock and array search per 128 KiB block in the squashfs cache implementation.

Comments, especially those of the form "you've got this completely wrong, and you can use the page cache like this, which will be simpler and faster than your current implementation" welcome :) I'm not adverse to using the page cache, but I can't see how it will be simpler or faster than the current implementation.

Phillip
--
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[Index of Archives]     [Linux Ext4 Filesystem]     [Union Filesystem]     [Filesystem Testing]     [Ceph Users]     [Ecryptfs]     [AutoFS]     [Kernel Newbies]     [Share Photos]     [Security]     [Netfilter]     [Bugtraq]     [Yosemite News]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux Cachefs]     [Reiser Filesystem]     [Linux RAID]     [Samba]     [Device Mapper]     [CEPH Development]
  Powered by Linux