* Re: [PATCH 06/10] AXFS: axfs_super.c
From: Arnd Bergmann @ 2008-08-22 19:49 UTC (permalink / raw)
To: Phillip Lougher
Cc: Jared Hulbert, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird, cotte, nickpiggin
In-Reply-To: <48AEF976.1010705@lougher.demon.co.uk>
On Friday 22 August 2008, Phillip Lougher wrote:
> 1. Support for > 4GB filesystems. In theory 2^64 bytes.
> 2. Compressed metadata
> 3. Inode timestamps
> 4. Hard-link support, and correct nlink counts
> 5. Sparse file support
> 6. Support for ". & ".." in readdir
> 7. Indexed directories for fast lookup
> 8. NFS exporting
> 9. No need to cache entire metadata in memory
>
> Squashfs has been optimised for block-based rotating media like hard
> disks, CDROMS. AXFS has been optimised for flash based media. Squashfs
> will outperform AXFS on rotating media, AXFS will outperform Squashfs on
> flash based media.
Ok, thanks for the list. I'm sure that sparse files are already
part of AXFS, and among the other things, I would consider some
to be AXFS bugs rather than squashfs features ("." in readdir, in
particular), but I get the point.
> Squashfs and AXFS should be seen as complementary filesystems, and there
> should be room in the Linux kernel for both.
>
> I don't see what your problem is here. I think AXFS is an extremely
> good filesystem and should be merged. But I don't see why this should
> lead to more Squashfs bashing.
Sorry, I didn't mean to be abusive. From first look, it appeared to do
everything that squashfs does, with less code, but you've made it clear
that there is need for both of them.
I would still expect axfs to replace cramfs for all practical purposes,
even though that was written by our Emperor Penguin ;-)
Arnd <><
^ permalink raw reply
* Re: [PATCH 05/10] AXFS: axfs_profiling.c
From: Arnd Bergmann @ 2008-08-22 19:38 UTC (permalink / raw)
To: Jared Hulbert
Cc: David Woodhouse, carsteno, Linux-kernel, linux-embedded,
linux-mtd, Jörn Engel
In-Reply-To: <6934efce0808221037u4548dd00q9ccd67545bfbcc8@mail.gmail.com>
On Friday 22 August 2008, you wrote:
> You mean to take this off list?
No, i replied to your mail that was sent just to me.
Putting everyone back on now
> > In 3, you create files with sysfs_create_file, and are fairly limited
> > with how you can use it. A structured file like you have in procfs
> > would not be allowed. File names are fixed, directory names can
> > be used to identify the mounted file systems. You can create symlinks
> > between your directory and other things in sysfs.
>
> What do you mean a structured file wouldn't be allowed? What's in them then?
sysfs files are meant to have just a single value. Some have a list of
values of the same type, but a file that needs a nontrivial parser
(even sscanf) is not allowed in sysfs, by convention.
There is also the technical limitation of the size to a single page,
which makes it hard to write variable size data.
> > In 4, you write a whole file system like debugfs (it's not as hard
> > as it sounds) and are free to do anything in there, but you can't
> > easily symlink to sysfs.
>
> Argh. No it might not be too bad to do to do, but it sounds like a
> maintenance hassle. Sounds like the best option though.
>
> Why did we decide debugfs is a bad fit?
It's basically the same as debugfs -- actually I once started a patch
to make it a single function call to instantiate a debugfs-like
file system, but I never finished that patch.
debugfs is a bad idea here because it is not meant for stable interfaces
but rather ad-hoc stuff. In a distribution kernel, debugfs is supposed
to be empty.
> > So where does a page show up in the profile if you have two identical
> > files and both are mapped?
>
> In which ever file was actually read. The kernel driver doesn't
> really know pages are redundant.
ok.
> > Will the kernel map them to the same page
> > but count the files separately, or will it show the same count for both?
>
> I count faults on pages in mmap() so I don't really care whether a
> page is mapped twice or just once. I'll count it every time you fault
> it even if it's the same physical page. It's the image builders job
> to figure out if there are redundant pages.
ok, makes sense.
I think there is still another option, which would be to generalize
the profiling interface so it can work with arbitrary file systems.
I'm sure that other people can benefit from that as well, e.g. for
optimizing boot times on disks. For such a general interface,
a per-file ioctl would fit best, and then file systems can implement
it if they want, or it can be moved into VFS.
Arnd <><
^ permalink raw reply
* Re: [PATCH 06/10] AXFS: axfs_super.c
From: Arnd Bergmann @ 2008-08-22 19:37 UTC (permalink / raw)
To: Jared Hulbert
Cc: Phillip Lougher, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird, cotte, nickpiggin
In-Reply-To: <6934efce0808221043i3d463ac2gb54b7dd4cfde4b81@mail.gmail.com>
On Friday 22 August 2008, Jared Hulbert wrote:
> > It certainly sounds like something for your medium-term TODO list,
> > although I wouldn't think of it as a show-stopper.
>
> Maybe. It more of a feature rather than a bug. It makes stat() and
> such fast. The trade off is RAM...
Yes. And if you implement it at some point later, it can well be
a mount option or an mkfs option in case it needs format changes.
Arnd <><
^ permalink raw reply
* Re: [PATCH 00/10] AXFS: Advanced XIP filesystem
From: Jamie Lokier @ 2008-08-22 18:43 UTC (permalink / raw)
To: Jared Hulbert
Cc: Greg Ungerer, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird, cotte, nickpiggin
In-Reply-To: <20080822183713.GC24179@shareable.org>
Jamie Lokier wrote:
> Jared Hulbert wrote:
> > What kind of NOR you using? That is not what I measure with fast
> > synchronous burst NOR's.
>
> I think the "fast" in "fast synchronous" gives it away :-)
>
> I'm using Spansion MirrorBit S29GL128N, which reads at about 0.6 MByte/s.
By the way, what speeds do you get on fast synchronous burst NORs - and
which chips are those?
Thanks,
-- Jamie
^ permalink raw reply
* Re: [PATCH 00/10] AXFS: Advanced XIP filesystem
From: Jamie Lokier @ 2008-08-22 18:37 UTC (permalink / raw)
To: Jared Hulbert
Cc: Greg Ungerer, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird, cotte, nickpiggin
In-Reply-To: <6934efce0808221116w76a662b0t954b0922b69d3232@mail.gmail.com>
Jared Hulbert wrote:
> On Fri, Aug 22, 2008 at 11:13 AM, Jamie Lokier <jamie@shareable.org> wrote:
> > Greg Ungerer wrote:
> >> One thing for sure is that many people who do non-MMU setups
> >> are interested in XIP to get the space savings. These are very
> >> often small devices with very constrained RAM and flash. (For
> >> whatever it is worth single NOR flash only boards are common in
> >> these smaller form factors :-)
> >
> > I'm using XIP on a device with 32MB RAM. The reason I use it is
> > _partly_ to save RAM, partly because programs start about 10 times
> > faster (reading NOR flash is slow and I keep the XIP region in RAM)
>
> What kind of NOR you using? That is not what I measure with fast
> synchronous burst NOR's.
I think the "fast" in "fast synchronous" gives it away :-)
I'm using Spansion MirrorBit S29GL128N, which reads at about 0.6 MByte/s.
Not because they're good, but because that's what the board I'm coding
for has on it. I presume they were cheap and familiar to the board
designers. (There is 32MB of RAM to play with after all.)
So start a sequence of Busybox processes from a shell script is noticable,
if it reads from NOR each time.
Oh, and it's a 166MHz ARM, so it's quite capable of decompressing
faster than the NOR can deliver.
-- Jamie
^ permalink raw reply
* Re: [PATCH 00/10] AXFS: Advanced XIP filesystem
From: Jared Hulbert @ 2008-08-22 18:16 UTC (permalink / raw)
To: Jamie Lokier
Cc: Greg Ungerer, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird, cotte, nickpiggin
In-Reply-To: <20080822181314.GB24179@shareable.org>
On Fri, Aug 22, 2008 at 11:13 AM, Jamie Lokier <jamie@shareable.org> wrote:
> Greg Ungerer wrote:
>> One thing for sure is that many people who do non-MMU setups
>> are interested in XIP to get the space savings. These are very
>> often small devices with very constrained RAM and flash. (For
>> whatever it is worth single NOR flash only boards are common in
>> these smaller form factors :-)
>
> I'm using XIP on a device with 32MB RAM. The reason I use it is
> _partly_ to save RAM, partly because programs start about 10 times
> faster (reading NOR flash is slow and I keep the XIP region in RAM)
What kind of NOR you using? That is not what I measure with fast
synchronous burst NOR's.
^ permalink raw reply
* Re: [PATCH 00/10] AXFS: Advanced XIP filesystem
From: Jamie Lokier @ 2008-08-22 18:13 UTC (permalink / raw)
To: Greg Ungerer
Cc: Jared Hulbert, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird, cotte, nickpiggin
In-Reply-To: <48AE0476.80109@snapgear.com>
Greg Ungerer wrote:
> One thing for sure is that many people who do non-MMU setups
> are interested in XIP to get the space savings. These are very
> often small devices with very constrained RAM and flash. (For
> whatever it is worth single NOR flash only boards are common in
> these smaller form factors :-)
I'm using XIP on a device with 32MB RAM. The reason I use it is
_partly_ to save RAM, partly because programs start about 10 times
faster (reading NOR flash is slow and I keep the XIP region in RAM)
and partly because it reduces memory fragmentation.
-- Jamie
^ permalink raw reply
* Re: [PATCH 03/10] AXFS: axfs.h
From: Jared Hulbert @ 2008-08-22 18:12 UTC (permalink / raw)
To: Geert Uytterhoeven
Cc: Arnd Bergmann, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird, cotte, nickpiggin
In-Reply-To: <Pine.LNX.4.64.0808221402170.17105@vixen.sonytel.be>
>> So do I understand right that 3 bytes is your minimum size, and going
>> smaller than that would not be helpful? Otherwise I would assume that
>> storing a '5' should only take one byte instead of three.
Right. But you need 3 bytes to store the maximum value 0x0a0000
If we had:
0x0000000000000003
0x00000000000000FF
0x000000000000000A
You would only need a 1 byte depth.
> From the paper, the minimum size (called `depth') is 1.
Correct the depth can be from 1 to 8 bytes. The depth is determined
by the maximum value in the array.
>> I don't unsterstand yet why you store the length of each word separate
>> from the word. Most variable-length codes store that implicitly in
>> the data itself, e.g. in the upper three bits, so that for storing
>> 0x5, 0x1001, 0xa0000, this could e.g. end up as 0x054010014a0000,
>> which is shorter than what you have, but not harder to decode.
>
> AFAIU, the length (`depth') of each word is not stored separate, as the
> depth is the same for all values in the same table.
That is correct. Each table has a single depth stored in the region descriptor.
^ permalink raw reply
* Re: [PATCH 00/10] AXFS: Advanced XIP filesystem
From: Jamie Lokier @ 2008-08-22 18:10 UTC (permalink / raw)
To: Greg Ungerer
Cc: Jared Hulbert, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird, cotte, nickpiggin
In-Reply-To: <48ADFE65.1050007@snapgear.com>
Greg Ungerer wrote:
>
> Jamie Lokier wrote:
> >Jared Hulbert wrote:
> >>The biggest improvement is in the way AXFS allows for each page to be XIP
> >>or
> >>not. First, a user collects information about which pages are accessed
> >>on a
> >>compressed image for each mmap()ed region from /proc/axfs/volume0. That
> >>'profile' is used as an input to the image builder. The resulting image
> >>has
> >>only the relevant pages uncompressed and XIP. The result is smaller
> >>memory
> >>sizes and faster launches.
> >
> >Sounds great, really nice idea.
> >
> >How does it fare with no MMU? Can the profiler and image builder lay
> >out the XIP pages in such a way that no-MMU mmaps can map those regions?
>
> The key for XIP on noMMU would be the ability to store a
> file as one complete contiguous chunk. Can AXFS do this?
Or more generally, the mmap'd parts of a file.
XIP doesn't mmap the whole file, it just maps the code and rodata.
The data segment is copied.
AXFS's magic for keeping parts of the file uncompressed, but parts
compressed, would be good for this - both for space saving, and also
because decompressing compressed data from NOR is faster than reading
uncompressed data.
-- Jamie
^ permalink raw reply
* Re: [PATCH 04/10] AXFS: axfs_inode.c
From: Jared Hulbert @ 2008-08-22 18:04 UTC (permalink / raw)
To: Jörn Engel
Cc: Phillip Lougher, Arnd Bergmann, Linux-kernel, linux-embedded,
linux-mtd, tim.bird, cotte, nickpiggin
In-Reply-To: <20080822171959.GA30977@logfs.org>
> Elsewhere in this maze of threads Arnd claimed to have tested the
> benefits of metadata compression - and it making little impact.
>
> My guess is that it would make a large impact if metadata would be a
> significant part of the filesystem image. Usually metadata is close
> enough to 0% to be mistaken for statistical noise. So compressing it
> makes a significant impact on an insignificant amount of data.
Like I said early it depends on the value you assign to significant.
For a fs sizes I started designing to 16MB-64MB if you have to track a
whole bunch of 8Byte numbers for every symlink, dev node, inode, and
page. It adds up quickly to a couple of MB, that can translate to
lots of money. Even at only an extra $0.25 a system * 12Million units
= $3Million.
^ permalink raw reply
* Re: [PATCH 06/10] AXFS: axfs_super.c
From: Jared Hulbert @ 2008-08-22 17:43 UTC (permalink / raw)
To: Arnd Bergmann
Cc: Phillip Lougher, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird, cotte, nickpiggin
In-Reply-To: <200808221852.38950.arnd@arndb.de>
> It certainly sounds like something for your medium-term TODO list,
> although I wouldn't think of it as a show-stopper.
Maybe. It more of a feature rather than a bug. It makes stat() and
such fast. The trade off is RAM...
^ permalink raw reply
* Re: [PATCH 06/10] AXFS: axfs_super.c
From: Jared Hulbert @ 2008-08-22 17:42 UTC (permalink / raw)
To: Phillip Lougher
Cc: Arnd Bergmann, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird, cotte, nickpiggin
In-Reply-To: <48AEF976.1010705@lougher.demon.co.uk>
> Squashfs and AXFS should be seen as complementary filesystems, and there
> should be room in the Linux kernel for both.
Exactly. We had different design assumptions. One is not _better_
than the other, they are just different.
^ permalink raw reply
* Re: [PATCH 07/10] AXFS: axfs_bdev.c
From: Jared Hulbert @ 2008-08-22 17:39 UTC (permalink / raw)
To: Bernhard Reutner-Fischer
Cc: Linux-kernel, linux-embedded, linux-mtd, Jörn Engel,
tim.bird, cotte, nickpiggin
In-Reply-To: <20080822125440.GA1396@mx.loc>
> mismatch between documentation and implementation WRT the function name ;)
oops.
>>+{
>>+ struct axfs_super *sbi = AXFS_SB(sb);
>>+ u64 boffset = AXFS_FSOFFSET_2_DEVOFFSET(sbi, fsoffset);
>>+ u64 blocks;
>>+ u64 blksize = sb->s_blocksize;
>>+ unsigned long dst;
>>+ unsigned long src;
>>+ sector_t block;
>>+ size_t bytes;
>>+ struct buffer_head *bh;
>>+ u64 copied = 0;
>>+
>>+ if (len == 0)
>>+ return 0;
>>+
>>+ blocks = len / blksize;
>>+ if ((len % blksize) > 0)
>>+ blocks += 1;
>>+
>>+ while (copied < len) {
>>+ /* Explicit casting for ARM linker errors. */
>
> did it try to emit some external div()? Is this still needed?
exactly. I haven't heard otherwise, it was a Freescale ARM11 build
that had the issue... I don't have the set up.
^ permalink raw reply
* Re: [PATCH 06/10] AXFS: axfs_super.c
From: Phillip Lougher @ 2008-08-22 17:37 UTC (permalink / raw)
To: Arnd Bergmann
Cc: Jared Hulbert, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird, cotte, nickpiggin
In-Reply-To: <200808221852.38950.arnd@arndb.de>
Arnd Bergmann wrote:
> On Friday 22 August 2008, Jared Hulbert wrote:
>>> This implies for block devices that the entire filesystem metadata has to be
>>> cached in RAM. This severely limits the size of AXFS filesystems when using
>>> block devices, or the else memory usage will be excessive.
>> This is where 64bit squashfs could be a better fit.
>
> Is this the only place where squashfs has a significant advantage?
> If so, you might want to change it in axfs eventually to make the
> decision easier for users ;-)
As you asked here's the list.
1. Support for > 4GB filesystems. In theory 2^64 bytes.
2. Compressed metadata
3. Inode timestamps
4. Hard-link support, and correct nlink counts
5. Sparse file support
6. Support for ". & ".." in readdir
7. Indexed directories for fast lookup
8. NFS exporting
9. No need to cache entire metadata in memory
Squashfs has been optimised for block-based rotating media like hard
disks, CDROMS. AXFS has been optimised for flash based media. Squashfs
will outperform AXFS on rotating media, AXFS will outperform Squashfs on
flash based media.
Squashfs and AXFS should be seen as complementary filesystems, and there
should be room in the Linux kernel for both.
I don't see what your problem is here. I think AXFS is an extremely
good filesystem and should be merged. But I don't see why this should
lead to more Squashfs bashing.
Phillip
^ permalink raw reply
* Re: [PATCH 04/10] AXFS: axfs_inode.c
From: Jörn Engel @ 2008-08-22 17:19 UTC (permalink / raw)
To: Phillip Lougher
Cc: Arnd Bergmann, jaredeh, Linux-kernel, linux-embedded, linux-mtd,
tim.bird, cotte, nickpiggin
In-Reply-To: <48AEF2A3.7020905@lougher.demon.co.uk>
On Fri, 22 August 2008 18:08:51 +0100, Phillip Lougher wrote:
>
> Squashfs stores significantly more metadata than cramfs. Remember
> cramfs has no support for filesystems > ~ 16Mbytes, no inode timestamps,
> truncates uid/gids, no hard-links, no nlink counts, no hashed
> directories, no unique inode numbers. If Squashfs didn't compress the
> metadata it would be significantly larger than cramfs.
Elsewhere in this maze of threads Arnd claimed to have tested the
benefits of metadata compression - and it making little impact.
My guess is that it would make a large impact if metadata would be a
significant part of the filesystem image. Usually metadata is close
enough to 0% to be mistaken for statistical noise. So compressing it
makes a significant impact on an insignificant amount of data.
Jörn
--
One of my most productive days was throwing away 1000 lines of code.
-- Ken Thompson.
^ permalink raw reply
* Re: [PATCH 04/10] AXFS: axfs_inode.c
From: Phillip Lougher @ 2008-08-22 17:08 UTC (permalink / raw)
To: Arnd Bergmann
Cc: jaredeh, Linux-kernel, linux-embedded, linux-mtd, Jörn Engel,
tim.bird, cotte, nickpiggin
In-Reply-To: <200808221200.26052.arnd@arndb.de>
Arnd Bergmann wrote:
> On Friday 22 August 2008, Phillip Lougher wrote:
>>> This looks very nice, but could use some comments about how the data is
>>> actually stored on disk. It took me some time to figure out that it actually
>>> allows to do tail merging into compressed blocks, which I was about to suggest
>>> you implement ;-). Cramfs doesn't have them, and I found that they are the
>>> main reason why squashfs compresses better than cramfs, besides the default
>>> block size, which you can change on either one.
>> Squashfs has much larger block sizes than cramfs (last time I looked it
>> was limited to 4K blocks), and it compresses the metadata which helps to
>> get better compression. But tail merging (fragments in Squashfs
>> terminology) is obviously a major reason why Squashfs gets good compression.
>
> The *default* block size in cramfs is smaller than in squashfs, but they both
> have user selectable block sizes. I found the impact of compressed metadata
> to be almost zero.
Squashfs stores significantly more metadata than cramfs. Remember
cramfs has no support for filesystems > ~ 16Mbytes, no inode timestamps,
truncates uid/gids, no hard-links, no nlink counts, no hashed
directories, no unique inode numbers. If Squashfs didn't compress the
metadata it would be significantly larger than cramfs.
Cheers
Phillip
^ permalink raw reply
* Re: [PATCH 06/10] AXFS: axfs_super.c
From: Arnd Bergmann @ 2008-08-22 16:52 UTC (permalink / raw)
To: Jared Hulbert
Cc: Phillip Lougher, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird, cotte, nickpiggin
In-Reply-To: <6934efce0808212005h30fa16d8w48833e8a0becfd8c@mail.gmail.com>
On Friday 22 August 2008, Jared Hulbert wrote:
> > This implies for block devices that the entire filesystem metadata has to be
> > cached in RAM. Â This severely limits the size of AXFS filesystems when using
> > block devices, or the else memory usage will be excessive.
>
> This is where 64bit squashfs could be a better fit.
Is this the only place where squashfs has a significant advantage?
If so, you might want to change it in axfs eventually to make the
decision easier for users ;-)
It certainly sounds like something for your medium-term TODO list,
although I wouldn't think of it as a show-stopper.
Arnd <><
^ permalink raw reply
* Re: [PATCH 00/10] AXFS: Advanced XIP filesystem
From: Jared Hulbert @ 2008-08-22 16:51 UTC (permalink / raw)
To: Geert Uytterhoeven
Cc: Linux-kernel, linux-embedded, linux-mtd, Jörn Engel,
tim.bird, cotte, nickpiggin
In-Reply-To: <Pine.LNX.4.64.0808221650500.17105@vixen.sonytel.be>
> The version in SVN seems to be slightly older than the one you submitted?
Oops. Okay I must have neglected to sync at the very end. Thanks.
I forgot, there is also a git repo at
git://git.infradead.org/users/jehulber/axfs.git
> Which platform(s) do you use for testing?
ARM, x86
> I gave AxFS a try on PS3 (ppc64, always use big-endian 64-bit for testing new
> code ;-).
Smart. Hmmm, If only I had a PS3....
> When mounting the image, I got the crash below:
>
> | attempt to access beyond end of device
> | loop0: rw=0, want=4920, limit=4912
> | [c00000000c1e34c0] [d000000000037974] .axfs_copy_block+0x8c/0x144 [axfs] (unreliable)
> | [c00000000c1e3580] [d000000000035f20] .axfs_copy_metadata+0x154/0x1cc [axfs]
> | [c00000000c1e3630] [d000000000035fd8] .axfs_verify_eofs_magic+0x40/0xa0 [axfs]
> | [c00000000c1e36c0] [d000000000036678] .axfs_fill_super+0x3c0/0x7c8 [axfs]
> | [c00000000c1e3780] [c0000000000d1670] .get_sb_bdev+0x154/0x1ec
> | [c00000000c1e3860] [d000000000037a94] .axfs_get_sb_bdev+0x34/0x6c [axfs]
> | [c00000000c1e38f0] [d000000000035d0c] .axfs_get_sb+0x320/0x394 [axfs]
> | [c00000000c1e3a00] [c0000000000d1318] .vfs_kern_mount+0x88/0x108
> | [c00000000c1e3ab0] [c0000000000d143c] .do_kern_mount+0x68/0x148
> | [c00000000c1e3b60] [c0000000000f0a10] .do_new_mount+0x90/0xf4
> | [c00000000c1e3c10] [c0000000000f0c5c] .do_mount+0x1e8/0x23c
> | [c00000000c1e3d60] [c000000000114778] .compat_sys_mount+0x21c/0x2ac
> | [c00000000c1e3e30] [c0000000000074dc] syscall_exit+0x0/0x40
Yeah we've had this problem before. I'm not so sure this is an endian
bug, though it is likely.
> When mounting (also on PS3) an image created on ia32, I get a different crash:
>
> | axfs: wrong magic
>
> So I guess some parts are not yet 64-bit or endian clean.
Can you run mkfs.axfs on the same trivial directory on both ia32 and
PPC64 and then get me the resulting images?
^ permalink raw reply
* Re: [PATCH 00/10] AXFS: Advanced XIP filesystem
From: Arnd Bergmann @ 2008-08-22 15:19 UTC (permalink / raw)
To: Geert Uytterhoeven
Cc: Jared Hulbert, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird, cotte, nickpiggin
In-Reply-To: <Pine.LNX.4.64.0808221650500.17105@vixen.sonytel.be>
On Friday 22 August 2008, Geert Uytterhoeven wrote:
> I gave AxFS a try on PS3 (ppc64, always use big-endian 64-bit for testing new
> code ;-).
> When mounting the image, I got the crash below:
>
> | attempt to access beyond end of device
> | loop0: rw=0, want=4920, limit=4912
> | Unable to handle kernel paging request for data at address 0x00000028
Offset 0x28 is buffer_head->b_data, so it seems like sb_bread returns NULL,
which it does for out of range block numbers. I guess axfs_copy_block
should check for that condition, as it can happen on malicious file system
images.
I agree that this is likely to get caused by an endianess bug.
A good help for finding endianess bugs is to use __be64 like data types
everywhere and test with sparse -D__CHECK_ENDIAN__.
Arnd
^ permalink raw reply
* Re: [PATCH 00/10] AXFS: Advanced XIP filesystem
From: Geert Uytterhoeven @ 2008-08-22 14:54 UTC (permalink / raw)
To: Jared Hulbert
Cc: Linux-kernel, linux-embedded, linux-mtd, Jörn Engel,
tim.bird, cotte, nickpiggin
In-Reply-To: <48AD00C4.6060302@gmail.com>
[-- Attachment #1: Type: TEXT/PLAIN, Size: 5922 bytes --]
Hi Jared,
On Wed, 20 Aug 2008, Jared Hulbert wrote:
> I'd like to get a first round of review on my AXFS filesystem. This is a simple
> See http://axfs.sourceforge.net for more info.
The version in SVN seems to be slightly older than the one you submitted?
Which platform(s) do you use for testing?
I gave AxFS a try on PS3 (ppc64, always use big-endian 64-bit for testing new
code ;-).
When mounting the image, I got the crash below:
| attempt to access beyond end of device
| loop0: rw=0, want=4920, limit=4912
| Unable to handle kernel paging request for data at address 0x00000028
| Faulting instruction address: 0xd000000000037988
| Oops: Kernel access of bad area, sig: 11 [#1]
| SMP NR_CPUS=2 PS3
| Modules linked in: axfs zlib_inflate nfsd exportfs dm_crypt dm_mod sg joydev evdev
| NIP: d000000000037988 LR: d000000000037974 CTR: 0000000000000000
| REGS: c00000000c1e3240 TRAP: 0300 Not tainted (2.6.27-rc4-dirty)
| MSR: 8000000000008032 <EE,IR,DR> CR: 24044482 XER: 20000000
| DAR: 0000000000000028, DSISR: 0000000040000000
| TASK = c0000000068d4e40[1744] 'mount' THREAD: c00000000c1e0000 CPU: 0
| GPR00: d000000000037974 c00000000c1e34c0 d000000000043f30 c00000000c1e36a0
| GPR04: 000000000000013e 000000000000013e c00000000c1e2eb0 0000000000000002
| GPR08: c00000000058de80 0000000000000001 c0000000068d4e40 c00000000c1e34c0
| GPR12: 8000000000008032 c000000000671300 0000000010020000 00000000ff80bec1
| GPR16: 0000000010023dc8 0000000010023db8 00000000ff80bed1 0000000010023e00
| GPR20: 0000000000000001 0000000010023e38 c00000000c1e36a0 c00000000c1d5000
| GPR24: 0000000000000000 0000000000000004 0000000000266000 0000000000000000
| GPR28: 0000000000001000 0000000000000004 d0000000000438e0 c00000000c1e34c0
| NIP [d000000000037988] .axfs_copy_block+0xa0/0x144 [axfs]
| LR [d000000000037974] .axfs_copy_block+0x8c/0x144 [axfs]
| Call Trace:
| [c00000000c1e34c0] [d000000000037974] .axfs_copy_block+0x8c/0x144 [axfs] (unreliable)
| [c00000000c1e3580] [d000000000035f20] .axfs_copy_metadata+0x154/0x1cc [axfs]
| [c00000000c1e3630] [d000000000035fd8] .axfs_verify_eofs_magic+0x40/0xa0 [axfs]
| [c00000000c1e36c0] [d000000000036678] .axfs_fill_super+0x3c0/0x7c8 [axfs]
| [c00000000c1e3780] [c0000000000d1670] .get_sb_bdev+0x154/0x1ec
| [c00000000c1e3860] [d000000000037a94] .axfs_get_sb_bdev+0x34/0x6c [axfs]
| [c00000000c1e38f0] [d000000000035d0c] .axfs_get_sb+0x320/0x394 [axfs]
| [c00000000c1e3a00] [c0000000000d1318] .vfs_kern_mount+0x88/0x108
| [c00000000c1e3ab0] [c0000000000d143c] .do_kern_mount+0x68/0x148
| [c00000000c1e3b60] [c0000000000f0a10] .do_new_mount+0x90/0xf4
| [c00000000c1e3c10] [c0000000000f0c5c] .do_mount+0x1e8/0x23c
| [c00000000c1e3d60] [c000000000114778] .compat_sys_mount+0x21c/0x2ac
| [c00000000c1e3e30] [c0000000000074dc] syscall_exit+0x0/0x40
| Instruction dump:
| 3b600000 409e0084 48000090 80b7001c e87701d0 7c84e392 48000799 e8410028
| 2fbb0000 7c781b78 7f3de040 7ec3b378 <e8980028> 409e002c 7f3dcb78 7c1ae392
| ---[ end trace 7f5bc7e7ad0c4386 ]---
When mounting (also on PS3) an image created on ia32, I get a different crash:
| axfs: wrong magic
^^^^^^^^^^^^^^^^^
| Unable to handle kernel paging request for data at address 0x000003a8
| Faulting instruction address: 0xd0000000000355f0
| Oops: Kernel access of bad area, sig: 11 [#1]
| SMP NR_CPUS=2 PS3
| Modules linked in: axfs zlib_inflate nfsd exportfs dm_crypt dm_mod sg joydev evdev
| NIP: d0000000000355f0 LR: c0000000000d1250 CTR: d0000000000355d0
| REGS: c00000000c0b73d0 TRAP: 0300 Not tainted (2.6.27-rc4-dirty)
| MSR: 8000000000008032 <EE,IR,DR> CR: 24044482 XER: 00000000
| DAR: 00000000000003a8, DSISR: 0000000040000000
| TASK = c000000006814b40[1745] 'mount' THREAD: c00000000c0b4000 CPU: 1
| GPR00: c0000000000d1250 c00000000c0b7650 d000000000043f30 c00000000652f800
| GPR04: c00000000652f8b8 c000000006815480 0000000000000002 c000000006815480
| GPR08: c000000006815480 0000000000000000 00000000000001ea 0000000000000000
| GPR12: d000000000037e68 c000000000671500 0000000010020000 00000000ffc18eee
| GPR16: 0000000010023d98 0000000010023d88 00000000ffc18efe 0000000010023db0
| GPR20: 0000000000000001 0000000010023dc8 c00000000634f280 c0000000065b5000
| GPR24: fffffffffffff000 d00000000003bd38 0000000000000000 d00000000003b278
| GPR28: c00000000652f800 c00000000652f800 c0000000005d66e8 c00000000c0b7650
| NIP [d0000000000355f0] .axfs_kill_super+0x20/0x9c [axfs]
| LR [c0000000000d1250] .deactivate_super+0xd4/0x114
| Call Trace:
| [c00000000c0b7650] [c0000000003d2c48] .down_write+0x5c/0xb8 (unreliable)
| [c00000000c0b76e0] [c0000000000d1250] .deactivate_super+0xd4/0x114
| [c00000000c0b7780] [c0000000000d1690] .get_sb_bdev+0x174/0x1ec
| [c00000000c0b7860] [d000000000037a94] .axfs_get_sb_bdev+0x34/0x6c [axfs]
| [c00000000c0b78f0] [d000000000035d0c] .axfs_get_sb+0x320/0x394 [axfs]
| [c00000000c0b7a00] [c0000000000d1318] .vfs_kern_mount+0x88/0x108
| [c00000000c0b7ab0] [c0000000000d143c] .do_kern_mount+0x68/0x148
| [c00000000c0b7b60] [c0000000000f0a10] .do_new_mount+0x90/0xf4
| [c00000000c0b7c10] [c0000000000f0c5c] .do_mount+0x1e8/0x23c
| [c00000000c0b7d60] [c000000000114778] .compat_sys_mount+0x21c/0x2ac
| [c00000000c0b7e30] [c0000000000074dc] syscall_exit+0x0/0x40
| Instruction dump:
| f9240030 ebebfff0 7d615b78 4e800020 f821ff71 7c0802a6 fba10078 7c7d1b78
| fbe10088 7c3f0b78 f80100a0 e9230470 <e80903a8> 2fa00000 409e0034 e80301d8
| ---[ end trace c19667cc5b6821ab ]---
So I guess some parts are not yet 64-bit or endian clean.
With kind regards,
Geert Uytterhoeven
Software Architect
Sony Techsoft Centre Europe
The Corporate Village · Da Vincilaan 7-D1 · B-1935 Zaventem · Belgium
Phone: +32 (0)2 700 8453
Fax: +32 (0)2 700 8622
E-mail: Geert.Uytterhoeven@sonycom.com
Internet: http://www.sony-europe.com/
A division of Sony Europe (Belgium) N.V.
VAT BE 0413.825.160 · RPR Brussels
Fortis · BIC GEBABEBB · IBAN BE41293037680010
^ permalink raw reply
* mkfs.axfs
From: Geert Uytterhoeven @ 2008-08-22 14:49 UTC (permalink / raw)
To: Jared Hulbert; +Cc: linux-embedded
[-- Attachment #1: Type: TEXT/PLAIN, Size: 1305 bytes --]
Hi Jared,
When compiling mkfs.axfs from SourceForge SVN (tried ia32, amd64, ppc64), I
get:
cc -g -I./ -O0 -c -o mkfs.axfs.o mkfs.axfs.c
In file included from ./linux/axfs.h:32,
from mkfs.axfs.c:58:
/usr/include/linux/time.h:9: error: redefinition of ‘struct timespec’
/usr/include/linux/time.h:15: error: redefinition of ‘struct timeval’
The patch below fixes this:
diff --git a/mkfs.axfs/trunk/linux/axfs.h b/mkfs.axfs/trunk/linux/axfs.h
index 6dc7c62..60ffd70 100644
--- a/mkfs.axfs/trunk/linux/axfs.h
+++ b/mkfs.axfs/trunk/linux/axfs.h
@@ -26,9 +26,9 @@
#ifdef __KERNEL__
#include <linux/rwsem.h>
-#endif
#include <linux/errno.h>
#include <linux/time.h>
+#endif
#define AXFS_MAGIC 0x48A0E4CD /* some random number */
#define AXFS_SIGNATURE "Advanced XIP FS"
BTW, there are still lots of suspicious warnings if you compile it with -Wall.
With kind regards,
Geert Uytterhoeven
Software Architect
Sony Techsoft Centre Europe
The Corporate Village · Da Vincilaan 7-D1 · B-1935 Zaventem · Belgium
Phone: +32 (0)2 700 8453
Fax: +32 (0)2 700 8622
E-mail: Geert.Uytterhoeven@sonycom.com
Internet: http://www.sony-europe.com/
A division of Sony Europe (Belgium) N.V.
VAT BE 0413.825.160 · RPR Brussels
Fortis · BIC GEBABEBB · IBAN BE41293037680010
^ permalink raw reply related
* Re: [PATCH 07/10] AXFS: axfs_bdev.c
From: Bernhard Reutner-Fischer @ 2008-08-22 12:54 UTC (permalink / raw)
To: Jared Hulbert
Cc: Linux-kernel, linux-embedded, linux-mtd, Jörn Engel,
tim.bird, cotte, nickpiggin
In-Reply-To: <48AD010B.6030209@gmail.com>
On Wed, Aug 20, 2008 at 10:45:47PM -0700, Jared Hulbert wrote:
>+/******************************************************************************
>+ *
>+ * axfs_copy_block_data
>+ *
>+ * Description: Helper function to read data from block device
>+ *
>+ * Parameters:
>+ * (IN) sb - pointer to super block structure.
>+ *
>+ * (IN) dst_addr - pointer to buffer into which data is to be read.
>+ *
>+ * (IN) boffset - offset within block device
>+ *
>+ * (IN) len - length of data to be read
>+ *
>+ * Returns:
>+ * 0 or error number
>+ *
>+ *****************************************************************************/
>+int axfs_copy_block(struct super_block *sb, void *dst_addr, u64 fsoffset,
>+ u64 len)
mismatch between documentation and implementation WRT the function name ;)
>+{
>+ struct axfs_super *sbi = AXFS_SB(sb);
>+ u64 boffset = AXFS_FSOFFSET_2_DEVOFFSET(sbi, fsoffset);
>+ u64 blocks;
>+ u64 blksize = sb->s_blocksize;
>+ unsigned long dst;
>+ unsigned long src;
>+ sector_t block;
>+ size_t bytes;
>+ struct buffer_head *bh;
>+ u64 copied = 0;
>+
>+ if (len == 0)
>+ return 0;
>+
>+ blocks = len / blksize;
>+ if ((len % blksize) > 0)
>+ blocks += 1;
>+
>+ while (copied < len) {
>+ /* Explicit casting for ARM linker errors. */
did it try to emit some external div()? Is this still needed?
^ permalink raw reply
* Re: [PATCH 06/10] AXFS: axfs_super.c
From: Bernhard Reutner-Fischer @ 2008-08-22 12:07 UTC (permalink / raw)
To: Jared Hulbert
Cc: Linux-kernel, linux-embedded, linux-mtd, Jörn Engel,
tim.bird, cotte, nickpiggin
In-Reply-To: <48AD0101.4020505@gmail.com>
On Wed, Aug 20, 2008 at 10:45:37PM -0700, Jared Hulbert wrote:
>+static int axfs_get_onmedia_super(struct super_block *sb)
>+{
>+ int err;
>+ struct axfs_super *sbi = AXFS_SB(sb);
>+ struct axfs_super_onmedia *sbo;
>+
>+ sbo = kmalloc(sizeof(*sbo), GFP_KERNEL);
>+ if (!sbo)
>+ return -ENOMEM;
>+
>+ axfs_copy_metadata(sb, (void *)sbo, 0, sizeof(*sbo));
>+
>+ /* Do sanity checks on the superblock */
>+ if (be32_to_cpu(sbo->magic) != AXFS_MAGIC) {
>+ printk(KERN_ERR "axfs: wrong magic\n");
>+ err = -EINVAL;
>+ goto out;
>+ }
>+
>+ /* verify the signiture is correct */
>+ if (strncmp(sbo->signature, AXFS_SIGNATURE, sizeof(AXFS_SIGNATURE))) {
>+ printk(KERN_ERR "axfs: wrong axfs signature,"
>+ " read %s, expected %s\n",
>+ sbo->signature, AXFS_SIGNATURE);
>+ err = -EINVAL;
>+ goto out;
>+ }
As Phillip mentioned for some other cases, just initialize err to
EINVAL.
>+
>+ sbi->magic = be32_to_cpu(sbo->magic);
>+ sbi->version_major = sbo->version_major;
>+ sbi->version_minor = sbo->version_minor;
>+ sbi->version_sub = sbo->version_sub;
>+ sbi->files = be64_to_cpu(sbo->files);
>+ sbi->size = be64_to_cpu(sbo->size);
>+ sbi->blocks = be64_to_cpu(sbo->blocks);
>+ sbi->mmap_size = be64_to_cpu(sbo->mmap_size);
>+ sbi->cblock_size = be32_to_cpu(sbo->cblock_size);
>+ sbi->timestamp.tv_sec = be64_to_cpu(sbo->timestamp);
>+ sbi->timestamp.tv_nsec = 0;
>+ sbi->compression_type = sbo->compression_type;
>+
>+ err = axfs_set_compression_type(sbi);
>+ if (err)
>+ goto out;
>+
>+ /* If no block or MTD device, adjust mmapable to cover all image */
>+ if (AXFS_NODEV(sb))
>+ sbi->mmap_size = sbi->size;
>+
>+ err = axfs_fill_region_descriptors(sb, sbo);
[as already mentioned the clipped snippet here is unneeded]
>+out:
>+ kfree(sbo);
>+ return err;
>+}
>+int axfs_verify_device_sizes(struct super_block *sb)
>+{
>+ struct axfs_super *sbi = AXFS_SB(sb);
>+ struct mtd_info *mtd0 = AXFS_MTD(sb);
>+ struct mtd_info *mtd1 = AXFS_MTD1(sb);
>+ int sndsize = sbi->size - sbi->mmap_size;
>+
>+ /* Whole FS on one device */
>+ if (mtd0 && !mtd1 && (mtd0->size < sbi->size)) {
>+ printk(KERN_ERR "axfs: ERROR: Filesystem extends beyond end of"
>+ "MTD! Filesystem cannot be safely mounted!\n");
missing space in "end ofMTD"
You're mixing the style of where you put such a space, so potential
errors are not easy to spot (manually).
e.g.:
>+ printk(KERN_ERR "axfs: ERROR: Mmap segment extends"
>+ " beyond end of MTD!");
>+ printk(KERN_ERR "mtd name: %s, mtd size: 0x%x, mmap "
>+ "size: 0x%llx",
>+ mtd0->name, mtd0->size, sbi->mmap_size);
>+static int axfs_check_options(char *options, struct axfs_super *sbi)
>+{
>+ unsigned long address = 0;
>+ char *iomem = NULL;
>+ unsigned long length = 0;
>+ char *p;
>+ int err = -EINVAL;
>+ substring_t args[MAX_OPT_ARGS];
>+
>+ if (!options)
>+ return 0;
>+
>+ if (!*options)
>+ return 0;
>+
>+ while ((p = strsep(&options, ",")) != NULL) {
>+ int token;
>+ if (!*p)
>+ continue;
>+
>+ token = match_token(p, tokens, args);
>+ switch (token) {
>+ case OPTION_SECOND_DEV:
>+ sbi->second_dev = match_strdup(&args[0]);
>+ if (!(sbi->second_dev)) {
>+ err = -ENOMEM;
>+ goto out;
>+ }
>+ if (!*(sbi->second_dev))
>+ goto bad_value;
>+ break;
>+ case OPTION_IOMEM:
>+ iomem = match_strdup(&args[0]);
>+ if (!(iomem)) {
>+ err = -ENOMEM;
>+ goto out;
>+ }
>+ if (!*iomem)
>+ goto bad_value;
>+ break;
>+ case OPTION_PHYSICAL_ADDRESS_LOWER_X:
>+ case OPTION_PHYSICAL_ADDRESS_UPPER_X:
>+ if (match_hex(&args[0], (int *)&address))
>+ goto out;
>+ if (!address)
>+ goto bad_value;
>+ break;
>+ default:
just:
goto bad_value;
>+ printk(KERN_ERR
>+ "axfs: unrecognized mount option \"%s\" "
>+ "or missing value\n", p);
>+ goto out;
>+ }
>+ }
>+
>+ if (iomem) {
>+ if (address)
>+ goto out;
>+ err = axfs_get_uml_address(iomem, &address, &length);
missing:
if (err)
goto out;
>+ kfree(iomem);
>+ sbi->iomem_size = length;
>+ sbi->virt_start_addr = address;
>+ }
>+
>+ sbi->phys_start_addr = address;
>+ return 0;
>+
>+bad_value:
>+ printk(KERN_ERR
>+ "axfs: unrecognized mount option \"%s\" "
>+ "or missing value\n", p);
>+out:
>+ if (iomem)
>+ kfree(iomem);
just kfree(iomem);
>+ return err;
>+}
>+
>+static int axfs_statfs(struct dentry *dentry, struct kstatfs *buf)
>+{
>+ struct axfs_super *sbi = AXFS_SB(dentry->d_sb);
>+
>+ buf->f_type = AXFS_MAGIC;
>+ buf->f_bsize = AXFS_PAGE_SIZE;
What will happen if i transfer the filesystem to a box with a different
pagesize?
>+ buf->f_blocks = sbi->blocks;
>+ buf->f_bfree = 0;
>+ buf->f_bavail = 0;
>+ buf->f_files = sbi->files;
>+ buf->f_ffree = 0;
>+ buf->f_namelen = AXFS_MAXPATHLEN;
>+ return 0;
>+}
I think i have seen the string "compessed" in one of your patches,
should be "compressed".
^ permalink raw reply
* Re: [PATCH 03/10] AXFS: axfs.h
From: Geert Uytterhoeven @ 2008-08-22 12:04 UTC (permalink / raw)
To: Arnd Bergmann
Cc: Jared Hulbert, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird, cotte, nickpiggin
In-Reply-To: <200808221327.37371.arnd@arndb.de>
[-- Attachment #1: Type: TEXT/PLAIN, Size: 2217 bytes --]
On Fri, 22 Aug 2008, Arnd Bergmann wrote:
> On Friday 22 August 2008, Jared Hulbert wrote:
> > If I have an array of u64 numbers tracking small numbers (a[0] = 1;
> > a[1] = 2;) just throwing that onmedia is a big waste.
> > (0x0000000000000001; 0x0000000000000002) Having different array types
> > for different images such as arrays of u8,u16,u32,u64 becomes less
> > efficient for 3,5,6 and 7 byte numbers, 3 bytes was a particularly
> > interesting size for me.
> >
> > All I'm doing is removing the totally unnecessary zeros and aligning by bytes.
> > Take an array of u64 like this :
> > 0x0000000000000005
> > 0x0000000000001001
> > 0x00000000000a0000
> >
> > I strip off the unneeded leading zeros:
> > 0x000005
> > 0x001001
> > 0x0a0000
> >
> > Then pack them to byte alignment:
> > 0x0000050010010a0000
> >
> > Sure it could be encoded more but that would make it harder to extract
> > the data. This way I can read the data in one, maybe two, cache
> > misses. A couple of shifts to deal with the alignment and endianness
> > and we are done.
>
> So do I understand right that 3 bytes is your minimum size, and going
> smaller than that would not be helpful? Otherwise I would assume that
> storing a '5' should only take one byte instead of three.
From the paper, the minimum size (called `depth') is 1.
> I don't unsterstand yet why you store the length of each word separate
> from the word. Most variable-length codes store that implicitly in
> the data itself, e.g. in the upper three bits, so that for storing
> 0x5, 0x1001, 0xa0000, this could e.g. end up as 0x054010014a0000,
> which is shorter than what you have, but not harder to decode.
AFAIU, the length (`depth') of each word is not stored separate, as the
depth is the same for all values in the same table.
With kind regards,
Geert Uytterhoeven
Software Architect
Sony Techsoft Centre Europe
The Corporate Village · Da Vincilaan 7-D1 · B-1935 Zaventem · Belgium
Phone: +32 (0)2 700 8453
Fax: +32 (0)2 700 8622
E-mail: Geert.Uytterhoeven@sonycom.com
Internet: http://www.sony-europe.com/
A division of Sony Europe (Belgium) N.V.
VAT BE 0413.825.160 · RPR Brussels
Fortis · BIC GEBABEBB · IBAN BE41293037680010
^ permalink raw reply
* Re: [PATCH 03/10] AXFS: axfs.h
From: Arnd Bergmann @ 2008-08-22 11:27 UTC (permalink / raw)
To: Jared Hulbert
Cc: Linux-kernel, linux-embedded, linux-mtd, Jörn Engel,
tim.bird, cotte, nickpiggin
In-Reply-To: <6934efce0808211540p237f2c52pd71c2b955b3f54a8@mail.gmail.com>
On Friday 22 August 2008, Jared Hulbert wrote:
> > This bytetable stuff looks overly complicated, both the data structure and
> > the access method. It seems like you are implementing your own custom Huffman
> > compression with this.
> >
> > Is the reasonn for the bytetable just to pack numbers efficiently, or do you
> > have a different intention?
>
> It looks more complicated than it is. I need a data structure that is
> 64bit capable, easily read-in-place (remember this is designed to be
> an XIP fs), and highly space efficient. Because it's XIP I didn't
> want something that required a lot of calculation nor something that
> made you incur a lot of cache misses. So yes I just want to pack
> numbers in an easily read-in-place fashion.
ok, that makes sense.
> If I have an array of u64 numbers tracking small numbers (a[0] = 1;
> a[1] = 2;) just throwing that onmedia is a big waste.
> (0x0000000000000001; 0x0000000000000002) Having different array types
> for different images such as arrays of u8,u16,u32,u64 becomes less
> efficient for 3,5,6 and 7 byte numbers, 3 bytes was a particularly
> interesting size for me.
>
> All I'm doing is removing the totally unnecessary zeros and aligning by bytes.
> Take an array of u64 like this :
> 0x0000000000000005
> 0x0000000000001001
> 0x00000000000a0000
>
> I strip off the unneeded leading zeros:
> 0x000005
> 0x001001
> 0x0a0000
>
> Then pack them to byte alignment:
> 0x0000050010010a0000
>
> Sure it could be encoded more but that would make it harder to extract
> the data. This way I can read the data in one, maybe two, cache
> misses. A couple of shifts to deal with the alignment and endianness
> and we are done.
So do I understand right that 3 bytes is your minimum size, and going
smaller than that would not be helpful? Otherwise I would assume that
storing a '5' should only take one byte instead of three.
I don't unsterstand yet why you store the length of each word separate
from the word. Most variable-length codes store that implicitly in
the data itself, e.g. in the upper three bits, so that for storing
0x5, 0x1001, 0xa0000, this could e.g. end up as 0x054010014a0000,
which is shorter than what you have, but not harder to decode.
> > Did you see a significant size benefit over simply storing all metadata as
> > uncompressed data structures like in cramfs?
>
> Yes. For some modest values of significant. In terms of the amount of
> space required to track the metadata it is more dramatic. For a small
> rootfs I can fit many of the data structures in an u8 array, while
> maintaining u64 compatibility. Compared to dumping u64 arrays onmedia
> that's an 8X savings. But it's an 8X savings of a smallish percentage
> of the image size. The difference is more pronounced on a smaller
> (2MB) filesystem I tested but it was only ~5% if memory serves me
> correct.
If you can save 5% on a real-world file system, you have convinced me.
> > Have you considered storing simple dentry/inode data in node_type==Compressed
> > nodes?
>
> Yes, I thought a lot about that. But I choose against it because I
> wanted read-in-place data structures for minimum RAM usage in the XIP
> case and I figure the way I do it would stat() faster.
ok.
Arnd <><
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox