[lkml]   [2008]   [Aug]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: [PATCH 03/10] AXFS: axfs.h
> 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.

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 :

I strip off the unneeded leading zeros:

Then pack them to byte alignment:

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.

> 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

> 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.

 \ /
  Last update: 2008-08-22 00:43    [W:0.131 / U:0.284 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site