* 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
* Re: [PATCH 04/10] AXFS: axfs_inode.c
From: Arnd Bergmann @ 2008-08-22 10:00 UTC (permalink / raw)
To: Phillip Lougher
Cc: jaredeh, Linux-kernel, linux-embedded, linux-mtd, Jörn Engel,
tim.bird, cotte, nickpiggin
In-Reply-To: <48AE22F5.3000309@lougher.demon.co.uk>
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. I hacked up a mksquashfs to avoid tail merging, and found
that the image size for squashfs and cramfs is practically identical if you
use the same block size and no tail merging.
> The AXFS code is rather obscure but it doesn't look to me that it does
> tail merging. The following code wouldn't work if the block in question
> was a tail contained in a larger block. It assumes the block extends to
> the end of the compressed block (cblk_size - cnode_offset).
yes, I thought the same thing when I first read that code, and was about
to send a lengthy reply about how it should be changed when I saw that
it already does exactly that ;-).
Arnd <><
^ permalink raw reply
* Re: [PATCH 05/10] AXFS: axfs_profiling.c
From: Carsten Otte @ 2008-08-22 7:26 UTC (permalink / raw)
To: Jared Hulbert
Cc: Arnd Bergmann, David Woodhouse, carsteno, Linux-kernel,
linux-embedded, linux-mtd, Jörn Engel
In-Reply-To: <6934efce0808210817h489bbeafyaf27217ca68bd31e@mail.gmail.com>
Jared Hulbert wrote:
>> The profiling code has certainly been useful to you during development,
>> and you should keep that code around for your own work on it,
>> but maybe you should not push that upstream, because regular users
>> are not going to need it.
>
> Nope. Profiling is absolutely fundamental to how AXFS works. Read
> the [PATCH 00/10] thread again.
I agree, the profiling part is the sweet spot. Profiling should be in,
probably even selectable at runtime as opposed to a config-switch.
This way we could have it in enterprise distros that would'nt build
another kernel image for this.
^ permalink raw reply
* Re: Adding a new platform
From: Peter Korsgaard @ 2008-08-22 7:25 UTC (permalink / raw)
To: Phillip Lougher
Cc: Geert Uytterhoeven, Charles Manning, vb, Paul Gortmaker,
Linux Embedded Maillist, corbet
In-Reply-To: <48AE4647.5060407@lougher.demon.co.uk>
>>>>> "Phillip" == Phillip Lougher <phillip@lougher.demon.co.uk> writes:
Hi,
Phillip> It only uses a relatively small subset of the VFS, and goes
Phillip> nowhere near the MTD subsystem. Recently dusting off an MTD
Phillip> patch I wrote for Squashfs a couple of years ago, I found it
Phillip> had to be completely rewritten for modern kernels.
Can I see it? I've recently pondered patching squashfs to talk
directly to MTD instead of through mtdblock as squashfs often is the
only thing using the block layer on embedded systems.
Compiling with CONFIG_BLOCK=n seems to save around 125kb here.
Phillip> Having said that the bit of the VFS Squashfs is interested
Phillip> in has changed in each of 2.6.23, 2.6.24, 2.6.25, 2.6.26 and
Phillip> now 2.6.27, and so I wouldn't say it was immune anyway.
Yeah, but it has always been pretty easy to fixup.
--
Bye, Peter Korsgaard
^ permalink raw reply
* Re: Adding a new platform
From: Phillip Lougher @ 2008-08-22 4:53 UTC (permalink / raw)
To: Geert Uytterhoeven
Cc: Charles Manning, vb, Paul Gortmaker, Linux Embedded Maillist,
corbet
In-Reply-To: <Pine.LNX.4.64.0808211044590.20704@vixen.sonytel.be>
Geert Uytterhoeven wrote:
> On Thu, 21 Aug 2008, Charles Manning wrote:
>
>> Luckily APIs for drivers (the most common stuff that people work on) don't
>> change that much, and the interfaces are reasonably clear. If you want some
>> hell then try working on file systems :-).
>
> Really? So how come so few changes are needed to keep squashfs working?
>
It only uses a relatively small subset of the VFS, and goes nowhere near
the MTD subsystem. Recently dusting off an MTD patch I wrote for
Squashfs a couple of years ago, I found it had to be completely
rewritten for modern kernels.
Having said that the bit of the VFS Squashfs is interested in has
changed in each of 2.6.23, 2.6.24, 2.6.25, 2.6.26 and now 2.6.27, and so
I wouldn't say it was immune anyway.
Phillip
^ permalink raw reply
* Re: [PATCH 04/10] AXFS: axfs_inode.c
From: Phillip Lougher @ 2008-08-22 3:46 UTC (permalink / raw)
To: Jared Hulbert
Cc: Linux-kernel, linux-embedded, linux-mtd, Jörn Engel,
tim.bird, cotte, nickpiggin
In-Reply-To: <6934efce0808212027q412c4cbbp6ea8673a7d3bc1b9@mail.gmail.com>
Jared Hulbert wrote:
>> I assume compressed blocks can be larger than PAGE_CACHE_SIZE? This suffers
>> from the rather obvious inefficiency that you decompress a big block >
>> PAGE_CACHE_SIZE, but only copy one PAGE_CACHE_SIZE page out of it. If
>> multiple files are being read simultaneously (a common occurrence), then
>> each is going to replace your one cached uncompressed block
>> (sbi->current_cnode_index), leading to decompressing the same blocks over
>> and over again on sequential file access.
>>
>> readpage file A, index 1 -> decompress block X
>> readpage file B, index 1 -> decompress block Y (replaces X)
>> readpage file A, index 2 -> repeated decompress of block X (replaces Y)
>> readpage file B, index 2 -> repeated decompress of block Y (replaces X)
>>
>> and so on.
>
> Yep. Been thinking about optimizing it. So far it hasn't been an
> issue for my customers. Most fs traffic being on the XIP pages. Once
> I get a good automated performance test up we'll probably look into
> something to improve this.
It's relatively easy to solve. Squashfs explicitly pushes the extra
pages into the pagecache (so subsequent readpages find them there and
don't call readpage on squashfs again).
Phillip
^ permalink raw reply
* Re: [PATCH 04/10] AXFS: axfs_inode.c
From: Phillip Lougher @ 2008-08-22 3:29 UTC (permalink / raw)
To: Jared Hulbert
Cc: Arnd Bergmann, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird, cotte, nickpiggin
In-Reply-To: <6934efce0808212023x758babf0w500da6801bd66f45@mail.gmail.com>
Jared Hulbert wrote:
>
> The memcpy in question copies a c_node to the page. The len is either
> the max length of a c_node and size of the buffer I'm copying to
> (PAGE_CACHE_SIZE) or it is the difference between the beginning of the
> c_node in the c_block and the end of the c_block, whichever is
> smaller. The confusion is probably because of the fact that this
> copies extra crap to the page for tails.
Ah yes, that's where I got confused :) Glad to see AXFS uses tail packing.
Phillip
^ permalink raw reply
* Re: [PATCH 04/10] AXFS: axfs_inode.c
From: Jared Hulbert @ 2008-08-22 3:27 UTC (permalink / raw)
To: Phillip Lougher
Cc: Linux-kernel, linux-embedded, linux-mtd, Jörn Engel,
tim.bird, cotte, nickpiggin
In-Reply-To: <48AE0697.5040706@lougher.demon.co.uk>
> I assume compressed blocks can be larger than PAGE_CACHE_SIZE? This suffers
> from the rather obvious inefficiency that you decompress a big block >
> PAGE_CACHE_SIZE, but only copy one PAGE_CACHE_SIZE page out of it. If
> multiple files are being read simultaneously (a common occurrence), then
> each is going to replace your one cached uncompressed block
> (sbi->current_cnode_index), leading to decompressing the same blocks over
> and over again on sequential file access.
>
> readpage file A, index 1 -> decompress block X
> readpage file B, index 1 -> decompress block Y (replaces X)
> readpage file A, index 2 -> repeated decompress of block X (replaces Y)
> readpage file B, index 2 -> repeated decompress of block Y (replaces X)
>
> and so on.
Yep. Been thinking about optimizing it. So far it hasn't been an
issue for my customers. Most fs traffic being on the XIP pages. Once
I get a good automated performance test up we'll probably look into
something to improve this.
^ permalink raw reply
* Re: [PATCH 04/10] AXFS: axfs_inode.c
From: Jared Hulbert @ 2008-08-22 3:23 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: <48AE22F5.3000309@lougher.demon.co.uk>
> 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 AXFS code is rather obscure but it doesn't look to me that it does tail
> merging. The following code wouldn't work if the block in question was a
> tail contained in a larger block. It assumes the block extends to the end
> of the compressed block (cblk_size - cnode_offset).
A c_block is the unit that gets compressed. It can contain multiple
c_nodes. The c_block can be PAGE_SIZE to 4GB in size, in theory :)
The c_nodes can be 1B to PAGE_SIZE. in any alignment. I pack many
tails as c_nodes in a c_block.
>>> + max_len = cblk_size - cnode_offset;
>>> + len = max_len > PAGE_CACHE_SIZE ? PAGE_CACHE_SIZE :
>>> max_len;
>>> + src = (void *)((unsigned long)cblk0 + cnode_offset);
>>> + memcpy(pgdata, src, len);
>
> Perhaps the AXFS authors could clarify this?
The memcpy in question copies a c_node to the page. The len is either
the max length of a c_node and size of the buffer I'm copying to
(PAGE_CACHE_SIZE) or it is the difference between the beginning of the
c_node in the c_block and the end of the c_block, whichever is
smaller. The confusion is probably because of the fact that this
copies extra crap to the page for tails.
^ permalink raw reply
* Re: [PATCH 06/10] AXFS: axfs_super.c
From: Jared Hulbert @ 2008-08-22 3:05 UTC (permalink / raw)
To: Phillip Lougher
Cc: Linux-kernel, linux-embedded, linux-mtd, Jörn Engel,
tim.bird, cotte, nickpiggin
In-Reply-To: <48AE19AD.1020209@lougher.demon.co.uk>
> From this it would appear that if the region data can't be mapped XIP (i.e.
> it is compressed or on a block device), it is cached in its entirety in RAM?
That is correct.
> 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.
^ permalink raw reply
* Re: kernel dump solutions
From: Josh Boyer @ 2008-08-22 2:54 UTC (permalink / raw)
To: Randy MacLeod; +Cc: linux-embedded
In-Reply-To: <21f828e90808211853r6e92f6b9ta4bf9252ed63eccd@mail.gmail.com>
On Thu, 2008-08-21 at 21:53 -0400, Randy MacLeod wrote:
> On Wed, Aug 13, 2008 at 3:48 PM, Josh Boyer <jwboyer@gmail.com> wrote:
> > Hi All,
> >
> > I'm curious what people are using for a kernel dump solution on embedded
>
> Create a region of memory that pesist across resets.
> Put kernel panic info, exceptiions and scheduling events into said memory.
> Profit!
I've done that many times. It works well enough, but it's not a dump.
I've actually used some dumps to debug some rather difficult kernel
problems in the past, but there are increasingly fewer options these
days.
> If only more manufactures would support this in the bios...
> Intel and BIOS writter folks are you listening?
BIOS... yeah... I don't have a BIOS. That's the best way to deal with
that.
josh
^ permalink raw reply
* Re: [PATCH 00/10] AXFS: Advanced XIP filesystem
From: Jared Hulbert @ 2008-08-22 2:48 UTC (permalink / raw)
To: Greg Ungerer
Cc: Jamie Lokier, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird, cotte, nickpiggin
In-Reply-To: <48AE0476.80109@snapgear.com>
> That would be enough I think. If you could manually select
> which files are contiguous-and-uncompressed that would be
> useful for some too here.
So.... If you don't have an MMU when do you call ->fault? Does the
noMMU code just loop through ->fault()ing all the pages in an mmap()?
> 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 :-)
True.
^ permalink raw reply
* Re: [PATCH 00/10] AXFS: Advanced XIP filesystem
From: Nick Piggin @ 2008-08-22 2:32 UTC (permalink / raw)
To: Jared Hulbert
Cc: carsteno, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird
In-Reply-To: <6934efce0808210713m220d2a6cje06a2dc51c4a857a@mail.gmail.com>
On Friday 22 August 2008 00:13, Jared Hulbert wrote:
> > Agreed. I haven't had a good look through it yet, but at a glance it
> > looks pretty neat. The VM side of things looks pretty reasonable
> > (I fear XIP faulting might have another race or two, but that's a
> > core mm issue rather than filesystem specific).
>
> How might I design a test to flush those bugs out? We haven't seen any.
Not quite sure yet. I just fixed a couple of easy ones, but there
could be some more lurking. Don't be too worried about it yet, I
was just musing to myself there really :)
^ permalink raw reply
* Re: [PATCH 04/10] AXFS: axfs_inode.c
From: Phillip Lougher @ 2008-08-22 2:22 UTC (permalink / raw)
To: Arnd Bergmann
Cc: jaredeh, Linux-kernel, linux-embedded, linux-mtd, Jörn Engel,
tim.bird, cotte, nickpiggin
In-Reply-To: <200808211417.14425.arnd@arndb.de>
Arnd Bergmann wrote:
> On Thursday 21 August 2008, Jared Hulbert wrote:
>> + array_index = AXFS_GET_INODE_ARRAY_INDEX(sbi, ino_number);
>> + array_index += page->index;
>> +
>> + node_index = AXFS_GET_NODE_INDEX(sbi, array_index);
>> + node_type = AXFS_GET_NODE_TYPE(sbi, array_index);
>> +
>> + if (node_type == Compressed) {
>> + /* node is in compessed region */
>> + cnode_offset = AXFS_GET_CNODE_OFFSET(sbi, node_index);
>> + cnode_index = AXFS_GET_CNODE_INDEX(sbi, node_index);
>> + down_write(&sbi->lock);
>> + if (cnode_index != sbi->current_cnode_index) {
>> + /* uncompress only necessary if different cblock */
>> + ofs = AXFS_GET_CBLOCK_OFFSET(sbi, cnode_index);
>> + len = AXFS_GET_CBLOCK_OFFSET(sbi, cnode_index + 1);
>> + len -= ofs;
>> + axfs_copy_data(sb, cblk1, &(sbi->compressed), ofs, len);
>> + axfs_uncompress_block(cblk0, cblk_size, cblk1, len);
>> + sbi->current_cnode_index = cnode_index;
>> + }
>> + downgrade_write(&sbi->lock);
>> + max_len = cblk_size - cnode_offset;
>> + len = max_len > PAGE_CACHE_SIZE ? PAGE_CACHE_SIZE : max_len;
>> + src = (void *)((unsigned long)cblk0 + cnode_offset);
>> + memcpy(pgdata, src, len);
>> + up_read(&sbi->lock);
>
> 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 AXFS code is rather obscure but it doesn't look to me that it does
tail merging. The following code wouldn't work if the block in question
was a tail contained in a larger block. It assumes the block extends to
the end of the compressed block (cblk_size - cnode_offset).
>> + max_len = cblk_size - cnode_offset;
>> + len = max_len > PAGE_CACHE_SIZE ? PAGE_CACHE_SIZE :
max_len;
>> + src = (void *)((unsigned long)cblk0 + cnode_offset);
>> + memcpy(pgdata, src, len);
Perhaps the AXFS authors could clarify this?
Phillip
^ permalink raw reply
* Re: [PATCH 00/10] AXFS: Advanced XIP filesystem
From: Nick Piggin @ 2008-08-22 2:04 UTC (permalink / raw)
To: Jared Hulbert
Cc: Frans Meulenbroeks, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird, cotte
In-Reply-To: <6934efce0808211232i21fcf347vb6baa6502246adb2@mail.gmail.com>
On Friday 22 August 2008 05:32, Jared Hulbert wrote:
> > Jared, nice work!
> > - would axfs be suitable as a filesystem on a ram disk?
>
> It could be. I plan on implementing support for brd. That might work
> nicely.
I was going to take a look at this too. With any luck, it should be
little effort required as it looks like you have the block device
support in place?
This filesystem actually should in theory work fairly well with brd,
because then we wouldn't have to bring the data over into pagecache
for frequently used pages but we can retain the compressed storage
for the infrequently used stuff.
I say in theory because I don't know of any serious users (except
kernel testing) of brd :)
^ permalink raw reply
* Re: kernel dump solutions
From: Randy MacLeod @ 2008-08-22 1:53 UTC (permalink / raw)
To: Josh Boyer; +Cc: linux-embedded
In-Reply-To: <1218656903.10489.50.camel@localhost.localdomain>
On Wed, Aug 13, 2008 at 3:48 PM, Josh Boyer <jwboyer@gmail.com> wrote:
> Hi All,
>
> I'm curious what people are using for a kernel dump solution on embedded
Create a region of memory that pesist across resets.
Put kernel panic info, exceptiions and scheduling events into said memory.
Profit!
If only more manufactures would support this in the bios...
Intel and BIOS writter folks are you listening?
--
// Randy
^ permalink raw reply
* Re: [PATCH 06/10] AXFS: axfs_super.c
From: Phillip Lougher @ 2008-08-22 1:43 UTC (permalink / raw)
To: jaredeh
Cc: Linux-kernel, linux-embedded, linux-mtd, Jörn Engel,
tim.bird, cotte, nickpiggin
In-Reply-To: <48AD0101.4020505@gmail.com>
Jared Hulbert wrote:
> +static void axfs_free_region(struct axfs_super *sbi,
> + struct axfs_region_desc *region)
> +{
> + if (!region)
> + return;
> +
> + if (AXFS_IS_REGION_XIP(sbi, region))
> + return;
> +
> + if (region->virt_addr)
> + vfree(region->virt_addr);
> +}
> +
No need to do
if(xxx)
vfree(xxx)
vfree/kfree can cope with NULL pointers.
> +static void axfs_put_sbi(struct axfs_super *sbi)
> +{
> + axfs_free_region(sbi, &sbi->uids);
> + axfs_free_region(sbi, &sbi->gids);
> +
> + if (sbi->second_dev)
> + kfree(sbi->second_dev);
> +
> + if (sbi->cblock_buffer[0])
> + vfree(sbi->cblock_buffer[0]);
> + if (sbi->cblock_buffer[1])
> + vfree(sbi->cblock_buffer[1]);
> +
Again, just kfree(xxx)/vfree(xxx)
> +
> +static int axfs_copy_mem(struct super_block *sb, void *buf, u64 fsoffset,
> + u64 len)
> +{
> + struct axfs_super *sbi = AXFS_SB(sb);
> + unsigned long addr;
> +
> + addr = sbi->virt_start_addr + (unsigned long)fsoffset;
> + memcpy(buf, (void *)addr, (size_t) len);
> + return 0;
Always returns 0, consider changing to static void
> +}
> +
> +static int axfs_copy_metadata(struct super_block *sb, void *buf, u64 fsoffset,
> + u64 len)
> +{
> + struct axfs_super *sbi = AXFS_SB(sb);
> + u64 end = fsoffset + len;
> + u64 a = sbi->mmap_size - fsoffset;
> + u64 b = end - sbi->mmap_size;
> + void *bb = (void *)((unsigned long)buf + (unsigned long)a);
> + int err;
> +
> + /* Catches case where sbi is not yet fully initialized. */
> + if ((sbi->magic == 0) && (sbi->virt_start_addr != 0))
> + return axfs_copy_mem(sb, buf, fsoffset, len);
> +
> + if (fsoffset < sbi->mmap_size) {
> + if (end > sbi->mmap_size) {
> + err = axfs_copy_metadata(sb, buf, fsoffset, a);
> + if (err)
> + return err;
> + err = axfs_copy_metadata(sb, bb, sbi->mmap_size, b);
> + } else {
> + if (AXFS_IS_OFFSET_MMAPABLE(sbi, fsoffset)) {
> + err = axfs_copy_mem(sb, buf, fsoffset, len);
> + } else if (AXFS_HAS_MTD(sb)) {
> + err = axfs_copy_mtd(sb, buf, fsoffset, len);
> + } else if (AXFS_HAS_BDEV(sb)) {
> + err = axfs_copy_block(sb, buf, fsoffset, len);
> + } else {
> + err = -EINVAL;
Consider initialising err to -EINVAL at declaration time, and get rid of
this else,
> + }
> + }
> + } else {
> + if (AXFS_NODEV(sb)) {
> + err = axfs_copy_mem(sb, buf, fsoffset, len);
> + } else if (AXFS_HAS_BDEV(sb)) {
> + err = axfs_copy_block(sb, buf, fsoffset, len);
> + } else if (AXFS_HAS_MTD(sb)) {
> + err = axfs_copy_mtd(sb, buf, fsoffset, len);
> + } else {
> + err = -EINVAL;
and this one.
> + }
> + }
> + return err;
> +}
> +
> +static int axfs_fill_region_data(struct super_block *sb,
> + struct axfs_region_desc *region, int force)
> +{
> +
> + if (AXFS_IS_REGION_INCORE(region))
> + goto incore;
> +
> + if (AXFS_IS_REGION_COMPRESSED(region))
> + goto incore;
> +
> + if (AXFS_IS_REGION_XIP(sbi, region)) {
> + if ((end > sbi->mmap_size) && (force))
> + goto incore;
> + addr = sbi->virt_start_addr;
> + addr += (unsigned long)fsoffset;
> + region->virt_addr = (void *)addr;
> + return 0;
> + }
> +
> +incore:
> + region->virt_addr = vmalloc(size);
> + if (!region->virt_addr)
> + goto out;
> + vaddr = region->virt_addr;
> +
> + if (AXFS_IS_REGION_COMPRESSED(region)) {
> + buff = vmalloc(c_size);
> + if (!buff)
> + goto out;
> + axfs_copy_metadata(sb, buff, fsoffset, c_size);
> + err = axfs_uncompress_block(vaddr, size, buff, c_size);
> + if (!err)
> + goto out;
> + vfree(buff);
> + } else {
> + axfs_copy_metadata(sb, vaddr, fsoffset, size);
> + }
> +
> + return 0;
From this it would appear that if the region data can't be mapped XIP
(i.e. it is compressed or on a block device), it is cached in its
entirety in RAM?
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.
> +
> +out:
> + if (buff)
> + vfree(buff);
> + if (region->virt_addr)
> + vfree(region->virt_addr);
> + return err;
> +}
> +
Just do kfree(xxx)
> +
> +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;
> + }
> +
> + 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);
> + if (err)
> + goto out;
> +
> + err = 0;
Redundant code
> +out:
> + kfree(sbo);
> + return err;
> +}
> +
Phillip
^ permalink raw reply
* Re: [PATCH 04/10] AXFS: axfs_inode.c
From: Phillip Lougher @ 2008-08-22 0:21 UTC (permalink / raw)
To: jaredeh
Cc: cotte, linux-embedded, nickpiggin, Jörn Engel, Linux-kernel,
linux-mtd, tim.bird
In-Reply-To: <48AD00F0.5030403@gmail.com>
Jared Hulbert wrote:
> +
> +static int axfs_iget5_test(struct inode *inode, void *opaque)
> +{
> + u64 *inode_number = (u64 *) opaque;
> +
> + if (inode->i_sb == NULL) {
> + printk(KERN_ERR "axfs_iget5_test:"
> + " the super block is set to null\n");
> + }
> + if (inode->i_ino == *inode_number)
> + return 1; /* matches */
> + else
> + return 0; /* does not match */
> +}
> +
This implies inode_numbers are unique in AXFS? If so you can get rid of
the axfs_iget5_set/test logic. This is only necessary for filesystems
with non-unique inode numbers like cramfs.
> +
> +struct inode *axfs_create_vfs_inode(struct super_block *sb, int ino)
> +{
> + struct axfs_super *sbi = AXFS_SB(sb);
> + struct inode *inode;
> + u64 size;
> +
> + inode = iget5_locked(sb, ino, axfs_iget5_test, axfs_iget5_set, &ino);
If inode_numbers are unique, use iget_locked here.
> +
> + if (!(inode && (inode->i_state & I_NEW)))
> + return inode;
> +
> + inode->i_mode = AXFS_GET_MODE(sbi, ino);
> + inode->i_uid = AXFS_GET_UID(sbi, ino);
> + size = AXFS_GET_INODE_FILE_SIZE(sbi, ino);
> + inode->i_size = size;
What's the reason for splitting this into two lines, rather than
inode->i_size = AXFS_GET_INODE_FILE_SIZE(sbi, ino);
> + inode->i_blocks = AXFS_GET_INODE_NUM_ENTRIES(sbi, ino);
> + inode->i_blkbits = PAGE_CACHE_SIZE * 8;
> + inode->i_gid = AXFS_GET_GID(sbi, ino);
> +
> + inode->i_mtime = inode->i_atime = inode->i_ctime = sbi->timestamp;
No unique per inode time? Will cause problems using AXFS for archives
etc. where preserving timestamps is important.
> + inode->i_ino = ino;
> +
Unnecessary, set by iget_locked/iget_locked5
> +
> +static int axfs_readdir(struct file *filp, void *dirent, filldir_t filldir)
> +{
> + struct inode *inode = filp->f_dentry->d_inode;
> + struct super_block *sb = inode->i_sb;
> + struct axfs_super *sbi = AXFS_SB(sb);
> + u64 ino_number = inode->i_ino;
> + u64 entry;
> + loff_t dir_index;
> + char *name;
> + int namelen, mode;
> + int err = 0;
> +
> + /* Get the current index into the directory and verify it is not beyond
> + the end of the list */
> + dir_index = filp->f_pos;
> + if (dir_index >= AXFS_GET_INODE_NUM_ENTRIES(sbi, ino_number))
> + goto out;
> +
> + /* Verify the inode is for a directory */
> + if (!(S_ISDIR(inode->i_mode))) {
> + err = -EINVAL;
> + goto out;
> + }
> +
> + while (dir_index < AXFS_GET_INODE_NUM_ENTRIES(sbi, ino_number)) {
> + entry = AXFS_GET_INODE_ARRAY_INDEX(sbi, ino_number) + dir_index;
> +
> + name = (char *)AXFS_GET_INODE_NAME(sbi, entry);
One to one mapping between inode number and inode name? No hard link
support...?
> + namelen = strlen(name);
> +
> + mode = (int)AXFS_GET_MODE(sbi, entry);
> + err = filldir(dirent, name, namelen, dir_index, entry, mode);
> +
> + if (err)
> + break;
> +
> + dir_index++;
> + filp->f_pos = dir_index;
> + }
> +
> +out:
> + return 0;
> +}
Are "." and ".." stored in the directory? If not then axfs_readdir
should fabricate them to avoid confusing applications that expect
readdir(3) to return them.
> +static ssize_t axfs_file_read(struct file *filp, char __user *buf, size_t len,
> + loff_t *ppos)
> + actual_size = len > remaining ? remaining : len;
> + readlength = actual_size < PAGE_SIZE ? actual_size : PAGE_SIZE;
Use min() or min_t()
> +
> +static int axfs_readpage(struct file *file, struct page *page)
> +{
> +
> + if (node_type == Compressed) {
> + /* node is in compessed region */
> + cnode_offset = AXFS_GET_CNODE_OFFSET(sbi, node_index);
> + cnode_index = AXFS_GET_CNODE_INDEX(sbi, node_index);
> + down_write(&sbi->lock);
> + if (cnode_index != sbi->current_cnode_index) {
> + /* uncompress only necessary if different cblock */
> + ofs = AXFS_GET_CBLOCK_OFFSET(sbi, cnode_index);
> + len = AXFS_GET_CBLOCK_OFFSET(sbi, cnode_index + 1);
> + len -= ofs;
> + axfs_copy_data(sb, cblk1, &(sbi->compressed), ofs, len);
> + axfs_uncompress_block(cblk0, cblk_size, cblk1, len);
> + sbi->current_cnode_index = cnode_index;
I assume compressed blocks can be larger than PAGE_CACHE_SIZE? This
suffers from the rather obvious inefficiency that you decompress a big
block > PAGE_CACHE_SIZE, but only copy one PAGE_CACHE_SIZE page out of
it. If multiple files are being read simultaneously (a common
occurrence), then each is going to replace your one cached uncompressed
block (sbi->current_cnode_index), leading to decompressing the same
blocks over and over again on sequential file access.
readpage file A, index 1 -> decompress block X
readpage file B, index 1 -> decompress block Y (replaces X)
readpage file A, index 2 -> repeated decompress of block X (replaces Y)
readpage file B, index 2 -> repeated decompress of block Y (replaces X)
and so on.
> + }
> + downgrade_write(&sbi->lock);
> + max_len = cblk_size - cnode_offset;
> + len = max_len > PAGE_CACHE_SIZE ? PAGE_CACHE_SIZE : max_len;
Again, min() or min_t(). Lots of these.
Phillip
______________________________________________________
Linux MTD discussion mailing list
http://lists.infradead.org/mailman/listinfo/linux-mtd/
^ permalink raw reply
* Re: [PATCH 00/10] AXFS: Advanced XIP filesystem
From: Greg Ungerer @ 2008-08-22 0:12 UTC (permalink / raw)
To: Jared Hulbert
Cc: Jamie Lokier, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird, cotte, nickpiggin
In-Reply-To: <6934efce0808210711t686a88eci6eb294dbb54d68fe@mail.gmail.com>
Hi Jared,
Jared Hulbert wrote:
>> 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?
>>
>> No complaint if not, it would be a nice bonus though.
>
> Sorry. I don't believe it will work on no-MMU as is. That said you
> _could_ tweak the mkfs tool to lay mmap()'ed regions down contiguously
> but then if you mmap() an unprofiled region, well that would be bad.
> I suppose you could make axfs_mmap smart enough to handle that. I
> guess the cleanest way would be to just make files lay down
> contiguously, you lose some of the space saving but it would work.
That would be enough I think. If you could manually select
which files are contiguous-and-uncompressed that would be
useful for some too here.
> I'm not plannin to get to this anytime soon. But I'd be willing merge
> patches. Can anybody convince me offline that working on no-MMU this
> makes financial sense for my employer? This is getting to be a common
> question. How many noMMU users are out there and why are you so
> interested?
One of those unknown factors, how many are there?
Who knows, pretty much impossible to tell.
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 :-)
Regards
Greg
------------------------------------------------------------------------
Greg Ungerer -- Chief Software Dude EMAIL: gerg@snapgear.com
Secure Computing Corporation PHONE: +61 7 3435 2888
825 Stanley St, FAX: +61 7 3891 3630
Woolloongabba, QLD, 4102, Australia WEB: http://www.SnapGear.com
^ permalink raw reply
* Re: [PATCH 00/10] AXFS: Advanced XIP filesystem
From: Greg Ungerer @ 2008-08-21 23:46 UTC (permalink / raw)
To: Jamie Lokier
Cc: Jared Hulbert, Linux-kernel, linux-embedded, linux-mtd,
Jörn Engel, tim.bird, cotte, nickpiggin
In-Reply-To: <20080821110749.GA1926@shareable.org>
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?
Regards
Greg
------------------------------------------------------------------------
Greg Ungerer -- Chief Software Dude EMAIL: gerg@snapgear.com
Secure Computing Corporation PHONE: +61 7 3435 2888
825 Stanley St, FAX: +61 7 3891 3630
Woolloongabba, QLD, 4102, Australia WEB: http://www.SnapGear.com
^ permalink raw reply
* Re: [PATCH 03/10] AXFS: axfs.h
From: Jared Hulbert @ 2008-08-21 22:40 UTC (permalink / raw)
To: Arnd Bergmann
Cc: Linux-kernel, linux-embedded, linux-mtd, Jörn Engel,
tim.bird, cotte, nickpiggin
In-Reply-To: <200808211424.31966.arnd@arndb.de>
> 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 :
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.
> 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.
> 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.
^ permalink raw reply
* Re: [PATCH 03/10] AXFS: axfs.h
From: Jared Hulbert @ 2008-08-21 20:07 UTC (permalink / raw)
To: Daniel Walker
Cc: Linux-kernel, linux-embedded, linux-mtd, Jörn Engel,
tim.bird, cotte, nickpiggin
In-Reply-To: <1219324258.23311.14.camel@localhost.localdomain>
> I think it would be much cleaner to do all these similar macro's as
> static inline functions.
Yeah. Been thinking about that.
^ permalink raw reply
* Re: [PATCH 03/10] AXFS: axfs.h
From: Jared Hulbert @ 2008-08-21 20:05 UTC (permalink / raw)
To: Arnd Bergmann
Cc: Linux-kernel, linux-embedded, linux-mtd, Jörn Engel,
tim.bird, cotte, nickpiggin
In-Reply-To: <200808211331.36346.arnd@arndb.de>
>> +#define AXFS_PAGE_SIZE 4096
>
> What happens on systems where AXFS_PAGE_SIZE != PAGE_SIZE?
Right now, bad things I imagine. I meant to revisit this, there was
some reason during development for this, I don't remember. No reason
for AXFS_PAGE_SIZE I think.
^ permalink raw reply
* Re: [PATCH 00/10] AXFS: Advanced XIP filesystem
From: Jared Hulbert @ 2008-08-21 19:32 UTC (permalink / raw)
To: Frans Meulenbroeks
Cc: Linux-kernel, linux-embedded, linux-mtd, Jörn Engel,
tim.bird, cotte, nickpiggin
In-Reply-To: <ac9c93b10808202332n2654884eh877848df2da59f20@mail.gmail.com>
> Jared, nice work!
Thanks.
> A few questions:
I meant to address these before. Sorry.
> - how does this benchmark compared to cramfs and squashfs in a NAND-only system
> (or is it just not a good plan to use this with NAND-only (of course
> I won't get XIP with NAND, I understand that)
I don't know, I'm interested to find out. I just benchmarked that.
Actually it should work very well as a NAND-only fs. Also you do get
something like XIP with NAND. If you boot an XIP AXFS image on NAND
or a blkdev it will copy that XIP region into RAM and "XIP" it from
there. I think this will make it very good for LiveCD's. Though we
just (minutes ago) realized our testing of that feature was flawed, so
no guarantees.
> - would axfs be suitable as a filesystem on a ram disk?
It could be. I plan on implementing support for brd. That might work nicely.
^ permalink raw reply
* Re: [PATCH 05/10] AXFS: axfs_profiling.c
From: Arnd Bergmann @ 2008-08-21 15:50 UTC (permalink / raw)
To: Jared Hulbert
Cc: David Woodhouse, carsteno, Linux-kernel, linux-embedded,
linux-mtd, Jörn Engel
In-Reply-To: <6934efce0808210817h489bbeafyaf27217ca68bd31e@mail.gmail.com>
On Thursday 21 August 2008, Jared Hulbert wrote:
> So /sys/kernel/debug/axfs/volume0 would work?
>
> > 4) no profiling at all
> > The profiling code has certainly been useful to you during development,
> > and you should keep that code around for your own work on it,
> > but maybe you should not push that upstream, because regular users
> > are not going to need it.
>
> Nope. Profiling is absolutely fundamental to how AXFS works. Read
> the [PATCH 00/10] thread again.
Ok, understood it now. So it actually is a stable interface into
the file system, which means that debugfs might not be the best
solution.
I need to think about this some more. So far none of the options
are perfect. What I can think of so far includes:
1. An ioctl on the mount point of the fs
2. An ioctl that you need to call on each file
3. sysfs files is /sys/fs/axfs/
4. A new virtual file system to be mounted to /sys/fs/axfs/
5. A file below the device in sysfs, e.g. /sys/block/mtdblk0/axfs-profile
I've also taken a look at the format of the profiling data file.
I'm not sure that it is ideal if you want to be able to share
identical data blocks between files. Do you currently do that
in your mkfs? The fs format certainly allows it. I would expect
that if you checksum each page, you can find duplicates on a page
basis and save some space this way. However, it can make profiling
harder if you count based on blocks but report the data based on
the file name. Not sure what a better solution would look like.
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