File perforation.

File perforation.

[David Woodhouse]

I keep receiving requests from users to allow space saving by making holes 
in files. For people using JFFS2, a compressed file system designed for use 
on fairly small solid state storage devices, this is a fairly reasonable 
request, and it's also fairly simple to implement. It's only the interface 
I'm concerned about.

I've been resisting these requests because I really don't want to do it 
with an ioctl on the file. Only if we can have a generic sys_perforate() 
would I really want to do it.

Apparently it's hard to implement on block-based file systems. I don't 
really care about that though -- just falling back to writing zeroes to the 
offending range (or indeed returning -EINVAL) would be perfectly sufficient 
until/unless it gets implemented for other file systems. All I want is an 
interface that doesn't make me feel dirty :)

Comments? 

--
dwmw2

Re: File perforation.

[Eli Carter]

David Woodhouse wrote:
> I keep receiving requests from users to allow space saving by making holes 
> in files. For people using JFFS2, a compressed file system designed for use 
> on fairly small solid state storage devices, this is a fairly reasonable 
> request, and it's also fairly simple to implement. It's only the interface 
> I'm concerned about.
> 
> I've been resisting these requests because I really don't want to do it 
> with an ioctl on the file. Only if we can have a generic sys_perforate() 
> would I really want to do it.
> 
> Apparently it's hard to implement on block-based file systems. I don't 
> really care about that though -- just falling back to writing zeroes to the 
> offending range (or indeed returning -EINVAL) would be perfectly sufficient 
> until/unless it gets implemented for other file systems. All I want is an 
> interface that doesn't make me feel dirty :)
> 
> Comments? 

Could you elaborate on the difference between what you want to do and 
sparse files?

Eli
--------------------. "If it ain't broke now,
Eli Carter           \                  it will be soon." -- crypto-gram
eli.carter(a)inet.com `-------------------------------------------------

Re: File perforation.

[David Woodhouse]

eli.carter@inet.com said:
>  Could you elaborate on the difference between what you want to do and
>  sparse files?


No difference. Given a non-sparse file, I want a way to make it sparse.

Well, I _have_ a way to make it sparse; all I have to do is write out a
single log entry. What I am lacking is a way for the user to tell me to do
so :)

I'm aware that you can do this by deleting the file and writing out a new
copy. But this is flash and it has a limited number of write cycles; I don't
want to do that.

--
dwmw2

Re: File perforation.

[Eli Carter]

David Woodhouse wrote:
> eli.carter@inet.com said:
> 
>> Could you elaborate on the difference between what you want to do and
>> sparse files?
> 
> 
> 
> No difference. Given a non-sparse file, I want a way to make it sparse.
> 
> Well, I _have_ a way to make it sparse; all I have to do is write out a
> single log entry. What I am lacking is a way for the user to tell me to do
> so :)
> 
> I'm aware that you can do this by deleting the file and writing out a new
> copy. But this is flash and it has a limited number of write cycles; I don't
> want to do that.

(No answers, just questions... ;) )

On a compressed fs like jffs2, wouldn't a block of 0's compress down to 
next-to-nothing already?

Can the fs recognize a big block of 0's and make it sparse on-the-fly 
without needing the user to specify it?  (On block-based fs's, that 
might not always be desirable due to out-of-space errors on modifying a 
file, but for a compressed fs, that's not a new issue.)

(Hmm.... If I'm missing something obvious, clue-by-four me and I'll go 
away. ;) )

Eli
--------------------. "If it ain't broke now,
Eli Carter           \                  it will be soon." -- crypto-gram
eli.carter(a)inet.com `-------------------------------------------------

Re: File perforation.

[David Woodhouse]

eli.carter@inet.com said:
>  On a compressed fs like jffs2, wouldn't a block of 0's compress down
> to  next-to-nothing already? 

Well, sort of. In fact each page would get zlib-compressed down to about 
40-odd bytes of payload and a datanode header of 70-odd bytes. 

> Can the fs recognize a big block of 0's and make it sparse on-the-fly
> without needing the user to specify it?  (On block-based fs's, that
> might not always be desirable due to out-of-space errors on modifying
> a  file, but for a compressed fs, that's not a new issue.) 

Yeah -- JFFS2 has a special compression type for a datanode payload which 
is all zeroes, but doesn't currently _detect_ that in a write, it only gets 
used for holes. I was dubious about adding a check for all zeroes before 
falling back to zlib, since it'll slow down the common case where we write 
non-zero data. I suppose we could always compare _after_ zlib compression 
though :)

The other thing about hole nodes (i.e. nodes with this special compression
type and hence no actual compressed data payload on the medium) is that
they're an exception to the rule that data nodes may not cross a page
boundary. So when we write zeroes to a file, even if we fix the compression
to notice and use JFFS2_COMPR_ZERO instead of zlib hence have no data
payload on the nodes, we still get a 70-odd-byte node header for every
(typ.) 4KiB, whereas with a 'proper' hole we'd write out a single node to
cover the whole range.

I suppose we could also munge the garbage collection to notice adjacent hole
nodes and merge them... on the whole, I think I prefer sys_perforate()
though.

--
dwmw2

Re: File perforation.

[Andrew Morton]

David Woodhouse wrote:
> 
> I was dubious about adding a check for all zeroes before
> falling back to zlib, since it'll slow down the common case where we write
> non-zero data.

I suggest you bench this first.  As a prototype, just add some code to
touch the data and see how much difference it makes.  Quite possibly
not much - view it as a fancy cache preload.   Plus for real data,
it'll bale out after the first byte...

A full holepunch()/perforate() thing is, as Dave points out, a trickier
version of truncate.  It's quite a hassle for not a lot of gain on
the block filesystems.

Re: File perforation.

[Andreas Dilger]

On Jan 08, 2003  17:22 -0800, Andrew Morton wrote:
> A full holepunch()/perforate() thing is, as Dave points out, a trickier
> version of truncate.  It's quite a hassle for not a lot of gain on
> the block filesystems.

Peter actually had a working version of this, what we called "punch", for
ext2 and I did the ext3 port in the 2.2 and early 2.3 days.  The original
motivator was HSM, because some applications (Windows mainly) checked
both the beginning and end of a file for data (icons I think) when you
opened a folder (unlike "file" magic which is just the first 64kB at most),
so it was critical for the HSM system to be able to do hole punching in
the middle of the file.

Similarly, InterMezzo would like to be able to do partial cacheing of
giant files by essentially having a block LRU of a file and punching
out the unused blocks of a file without disturbing the other content.
InterMezzo also has a use for this to have an always-growing modification
log, and the server can punch out the blocks of data at the beginning of
the log when all clients have pulled those updates and/or those updates
have been superceded by later changes.

I think there is pent up demand for this, and applications would take
advantage of this if it where available.  A simple syscall like

	sys_punch(file, start, end)

(or start, count) is the natural thing to have.  If end > file_size
it becomes equal to truncate.

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/

Re: File perforation.

[Steven Whitehouse]

Hi,

I would have thought it was the kind of thing that HSM people might be
interested in, perhaps they have some ideas for interfaces ? 
Also I thought of an interface like madvise() but for
files: fadvise() and then discovered that it already exists :-)

http://www.opengroup.org/onlinepubs/007904975/functions/posix_fadvise.html

So presumably a suitable advice value FADV_CLEAR (for example) could be 
used as an addition to the POSIX values ? unless there is a reason not to
overload it ? I guess preallocation could be done through the same
mechanism too if it was required.

Also I found a thread about fadvise here:

http://www.cs.helsinki.fi/linux/linux-kernel/2002-11/0031.html

Steve.

Re: File perforation.

[David Woodhouse]

steve@gw.chygwyn.com said:
> So presumably a suitable advice value FADV_CLEAR (for example) could
> be  used as an addition to the POSIX values ? 

Nothing else that fadvise() offers actually changes the file. They're all 
optional -- if the kernel ignores your fadvise() call you can't even prove 
that it's done so. I'm not sure it's a good fit.

--
dwmw2

Re: File perforation.

[Steven Whitehouse]

Hi,

> 
> 
> steve@gw.chygwyn.com said:
> > So presumably a suitable advice value FADV_CLEAR (for example) could
> > be  used as an addition to the POSIX values ? 
> 
> Nothing else that fadvise() offers actually changes the file. They're all 
> optional -- if the kernel ignores your fadvise() call you can't even prove 
> that it's done so. I'm not sure it's a good fit.
>
Yes, I share your misgivings there. Perhaps keeping the interface idea but
giving it a different name. iadvise (for inode-advise) maybe ?

Steve.

Re: File perforation.

[David Woodhouse]

steve@gw.chygwyn.com said:
>  Yes, I share your misgivings there. Perhaps keeping the interface
> idea but giving it a different name. iadvise (for inode-advise) maybe
> ?

Given that madvise and fadvise are both advisory, I'd not be a lot happier 
with iadvise, to be honest.

--
dwmw2

Re: File perforation.

[Bryan Henderson]

>Nothing else that fadvise() offers actually changes the file. They're all 

>optional -- if the kernel ignores your fadvise()

Not only that, it's optional from the user's side too.  You can can ignore 
your own advice and do something else instead, and the kernel has to 
produce the same result as if you hadn't advised at all.

Re: File perforation.

[Dave Kleikamp]

On Wednesday 08 January 2003 16:06, David Woodhouse wrote:
> I've been resisting these requests because I really don't want to do
> it with an ioctl on the file. Only if we can have a generic
> sys_perforate() would I really want to do it.

I have heard requests for the same thing.  I would not be opposed to the 
new system call.

> Apparently it's hard to implement on block-based file systems. I
> don't really care about that though -- just falling back to writing
> zeroes to the offending range (or indeed returning -EINVAL) would be
> perfectly sufficient until/unless it gets implemented for other file
> systems. All I want is an interface that doesn't make me feel dirty
> :)

I don't think that it would be terribly hard to implement for 
block-based fs's.  It's basically a more general form of truncate.  Of 
course, I'm not saying it would be trivial.  Experience says that 
anything dealing with truncate is full of gotchas and corner cases.

> Comments?

-- 
David Kleikamp
IBM Linux Technology Center

Re: File perforation.

[Matthew Wilcox]

On Wed, Jan 08, 2003 at 10:06:00PM +0000, David Woodhouse wrote:
> I've been resisting these requests because I really don't want to do it 
> with an ioctl on the file. Only if we can have a generic sys_perforate() 
> would I really want to do it.

SGI have an fcntl to do this:

http://techpubs.sgi.com/library/tpl/cgi-bin/getdoc.cgi?coll=0650&db=man&fname=/usr/share/catman/p_man/cat2/standard/fcntl.z

F_FREESP

However, I think this is probably the ugliest method available to perform
this function.

-- 
"It's not Hollywood.  War is real, war is primarily not about defeat or
victory, it is about death.  I've seen thousands and thousands of dead bodies.
Do you think I want to have an academic debate on this subject?" -- Robert Fisk

Re: File perforation.

[David Woodhouse]

willy@debian.org said:
>  However, I think this is probably the ugliest method available to
> perform this function. 

Indeed. That's probably even worse than sendfile() from /dev/zero :)

--
dwmw2

Re: File perforation.

[Christoph Hellwig]

On Wed, Jan 08, 2003 at 10:55:51PM +0000, Matthew Wilcox wrote:
> On Wed, Jan 08, 2003 at 10:06:00PM +0000, David Woodhouse wrote:
> > I've been resisting these requests because I really don't want to do it 
> > with an ioctl on the file. Only if we can have a generic sys_perforate() 
> > would I really want to do it.
> 
> SGI have an fcntl to do this:
> 
> http://techpubs.sgi.com/library/tpl/cgi-bin/getdoc.cgi?coll=0650&db=man&fname=/usr/share/catman/p_man/cat2/standard/fcntl.z
> 
> F_FREESP

Or the XFS_IOC_FREESP ioctl on XFS/Linux..

Re: File perforation.

[Bryan Henderson]

On AIX, that's the clear() system call.  It's defined to be identical to 
write() except that it always writes zeroes.  It is up to the individual 
filesystem driver whether it implements it by punching holes in files or 
not.

I've implemented this on a block filesystem type, and the only hairy part 
about it is taking care of the sub-block fringes of the range being 
written -- complicated by the fact that the write may go past end of file.

In practice, this system call gets used only when the caller knows that it 
creates a hole and knows the block size and thus does a clear only of 
whole blocks.  Basically, we're talking database managers.
--
Bryan Henderson                         IBM Research
San Jose CA                             Filesystems

File perforation.

[Steven French]

Steven Whitehouse said
>Also I thought of an interface like madvise() but for
>files: fadvise() and then discovered that it already exists :-)

The fadvise concept sounds somewhat promising.   In the particular case of
the cifs filesystem, as long as the posix_fadvise like info were available
before the open (perhaps in the file struct) then it is trivial to pass
equivalents to most of them to the server in the network file open (in the
NTCreateX SMB PDU) information that would presumbably be ignored by many
filesystems unfortunately since the posix specs fadvise to take an open
file descriptor it makes it trickier for my particular case.

The sparse concept is interesting for my particular vfs as well - Windows
has an attribute flag presumably to allow an application to supply a hint
to the filesystem (when creating a file) that a particular inode is going
to be written sparsely.   Not sure that such a concept matters at all for
my Linux vfs given that the open/create system call is so much simpler.
I now have something fun to do over the weekend - trying to figure out what
the flag really does   :)

Steve French
Senior Software Engineer
Linux Technology Center - IBM Austin
phone: 512-838-2294
email: sfrench@us.ibm.com

Re: File perforation.

[Bryan Henderson]

>The sparse concept is interesting for my particular vfs as well - Windows
>has an attribute flag presumably to allow an application to supply a hint
>to the filesystem (when creating a file) that a particular inode is going
>to be written sparsely.

How sure are you that that's a hint about future access?  My understanding
(based on very little authority) is that it is actually a _request_ to
allocate the file sparsely.  I.e. if you don't turn on that flag and then
write a byte at 0 and a byte at Block 99, Windows allocates 100 blocks of
disk space.  If you do turn it on, Windows allocates two blocks.

The reason you'd want the 100 block case is to be sure that when you later
go to fill in the middle, you don't get told there's no space.  And it is
default for backward compatibility because the ancestral filesystem type
wasn't sophisticated enough to do sparse.

--
Bryan Henderson                         IBM Research
San Jose CA                             Filesystems

Re: File perforation.

[Steven French]

I am not at all sure that it is a hint your theory is just as plausible.
Sounds like it is time for me to do some experimentation to prove if your
theory is correct.

Steve French
Senior Software Engineer
Linux Technology Center - IBM Austin
phone: 512-838-2294
email: sfrench@us.ibm.com


From:  Bryan Henderson on 01/10/2003 07:46 PM

To:    Steven French/Austin/IBM@IBMUS
cc:    linux-fsdevel@vger.kernel.org
From:  Bryan Henderson/San Jose/IBM@IBMUS
Subject:    Re: File perforation.  (Document link: Steven French)

>The sparse concept is interesting for my particular vfs as well - Windows
>has an attribute flag presumably to allow an application to supply a hint
>to the filesystem (when creating a file) that a particular inode is going
>to be written sparsely.

How sure are you that that's a hint about future access?  My understanding
(based on very little authority) is that it is actually a _request_ to
allocate the file sparsely.  I.e. if you don't turn on that flag and then
write a byte at 0 and a byte at Block 99, Windows allocates 100 blocks of
disk space.  If you do turn it on, Windows allocates two blocks.

The reason you'd want the 100 block case is to be sure that when you later
go to fill in the middle, you don't get told there's no space.  And it is
default for backward compatibility because the ancestral filesystem type
wasn't sophisticated enough to do sparse.

--
Bryan Henderson                         IBM Research
San Jose CA                             Filesystems