Editing-in-place of a large file
I would like to take an extremely large file (multi-gigabyte) and edit it by removing a chunk out of the middle. This is easy enough by reading in the entire file and spitting it back out again, but it's hardly efficent to read in an 8GB file just to remove a 100MB segment.
Is there another way to do this?
Is it possible to modify the inode structure of the underlying filesystem to free blocks in the middle? (What to do with the half-full blocks that are left?) Has anyone written a tool to do something like this?
Is there a way to do this in a filesystem-independent manner?
Thanks,
-- Bob
Bob McElrath ([email protected]) Univ. of Wisconsin at Madison, Department of Physics
COW fs (Re: Editing-in-place of a large file)
Sunday, September 02, 2001, 11:21:37 PM, Bob McElrath wrote:
BM> I would like to take an extremely large file (multi-gigabyte) and edit BM> it by removing a chunk out of the middle. This is easy enough by BM> reading in the entire file and spitting it back out again, but it's BM> hardly efficent to read in an 8GB file just to remove a 100MB segment.
BM> Is there another way to do this?
BM> Is it possible to modify the inode structure of the underlying BM> filesystem to free blocks in the middle? (What to do with the half-full BM> blocks that are left?) Has anyone written a tool to do something like BM> this?
BM> Is there a way to do this in a filesystem-independent manner?
A COW fs is a far more useful and cool. A fs where a copy of a file does not duplicate all blocks. Blocks get copied-on-write only when copy of a file is written to. There could be even a fs compressor which looks for and merges blocks with exactly same contents from different files.
Maybe ext2/3 folks will play with this idea after ext3?
I'm planning to write a test program which will scan my ext2 fs and report how many duplicate blocks with the same contents it sees (i.e how many would I save with a COW fs)
Signature · 4 lines
Best regards, VDA mailto:[email protected] http://port.imtp.ilyichevsk.odessa.ua/vda/
Quoted 6 lines · Bob McElrath
I would like to take an extremely large file (multi-gigabyte) and edit it by removing a chunk out of the middle. This is easy enough by reading in the entire file and spitting it back out again, but it's hardly efficent to read in an 8GB file just to remove a 100MB segment.
Is there another way to do this?
It's basically changing ownership (in terms of "which inode owns which blocks") of blocks.
There is just no POSIX-API to do this, that's why there is no simple way to do this.
Applications handling such large files usally implement a chunk management, which can mark chunks as "unused" and skip them while processing the file.
What's needed is a generalisation of sparse files and truncate(). They both handle similar problems.
For now I would seriously consider editing the ext2-structures for this, because that's the only way you can do this right now.
Regards
Ingo Oeser
Signature · 2 lines
In der Wunschphantasie vieler Mann-Typen [ist die Frau] unsigned und operatorvertraeglich. --- Dietz Proepper in dasr
Quoted 2 lines
What's needed is a generalisation of sparse files and
truncate(). They both handle similar problems.
how about
fzero(int fd, off_t off, size_t len)
which zeros the blocks and if it can creates a holey file?
However, that's not what Bob wants, he wants to remove commercials from recorded TV. So what he wants is
fdelete(int fd, off_t off, size_t len)
which has the semantics of shifting the rest of the file backwards to "off".
The main problem with this is if the off/len are not block aligned. If they are, then this is just block twiddling, if they aren't, then this is a file rewrite anyway.
Signature · 2 lines
--- Larry McVoy lm at bitmover.com http://www.bitmover.com/lm
Quoted 6 lines · Larry McVoy
Quoted 2 lines
What's needed is a generalisation of sparse files and
truncate(). They both handle similar problems.how about
fzero(int fd, off_t off, size_t len)
sys_clear :-)
Quoted 5 lines
which zeros the blocks and if it can creates a holey file?
However, that's not what Bob wants, he wants to remove commercials from recorded TV. So what he wants is
Quoted 7 lines
fdelete(int fd, off_t off, size_t len)which has the semantics of shifting the rest of the file backwards to "off".
The main problem with this is if the off/len are not block aligned. If they are, then this is just block twiddling, if they aren't, then this is a file rewrite anyway.
He could insert blank video frames to pad to the edges of blocks. Very theoretical since we are ages away from having fzero/sys_clear. Ask Al Viro if you want to hear the whole ugly story. (Executive summary: it's hard enough handling remove/create races with just one boundary per file, now try it with an unbounded number.)
--
Daniel
Quoted 7 lines · Larry McVoy
Quoted 2 lines
What's needed is a generalisation of sparse files and
truncate(). They both handle similar problems.how about
fzero(int fd, off_t off, size_t len)
fdelete(int fd, off_t off, size_t len)
and
finsert(int fd, off_t off, size_t len, void *buf, size_t buflen)
Quoted 3 lines
The main problem with this is if the off/len are not block aligned. If they are, then this is just block twiddling, if they aren't, then this is a file rewrite anyway.
Yes, that's why I solved this in user space by implementing a C++ stream consisting of multiple mmaps() of files and anonymous memory. I needed this for someone editing audio streams.
It's basically creating a binary diff ;-)
Another solution for the original problem is to rewrite the file in-place by coping from the end of the gap to the beginning of the gap until the gap is shifted to the end of the file and thus can be left to ftruncate().
This will at least not require more space on disk, but will take quite a while and risk data corruption for this file in case of abortion.
But fzero, fdelete and finsert might be worth considering, since some file systems, which pack tails could also pack these kind of partial used blocks and handle them properly.
We already handle partial pages, so why not handle them with offset/size pairs and enable this mechanisms? Multi media streams would love these kind of APIs ;-)
Regards
Ingo Oeser
Quoted 4 lines
Another solution for the original problem is to rewrite the file in-place by coping from the end of the gap to the beginning of the gap until the gap is shifted to the end of the file and thus can be left to
ftruncate().
Another approach would be to keep your own index of blocks and use that for the data reads. Since fdelete and fzero wont actually relayout the files in order to make the data linear (even if such calls existed) there isnt much point performancewise doing it in kernel space - its a very specialised application
Quoted 2 lines · Alan Cox
Another approach would be to keep your own index of blocks and use that for the data reads.
That is reimplementing file system functionality in user space. I'm in doubts that this is considered good design...
But I've done a similar thing anyway (using a ordered list of continous mmap()ed chunks) some years ago (see my other posting in this thread mentioning C++) ;-)
Quoted 3 lines
Since fdelete and fzero wont actually relayout the files in order to make the data linear (even if such calls existed) there isnt much point performancewise doing it in kernel space
That's the problem of the file system to be used. And the data doesn't need to be linear. Current file systems on Linux only avoid fragmentation, but they don't actively fight it by moving things around, so this doesn't matter anyway.
Quoted 1 line
- its a very specialised application
Editing video and audio streams is more common then you think and letting the user wait, while we copy 4GB around is not what I consider user friendly, even for the selective user friendlyness of a Unix ;-)
Regards
Ingo Oeser
Quoted 2 lines
That is reimplementing file system functionality in user space. I'm in doubts that this is considered good design...
Keeping things out of the kernel is good design. Your block indirections are no different to other database formats. Perhaps you think we should have fsql_operation() and libdb in kernel 8)
Quoted 6 lines · Alan Cox
Quoted 2 lines
That is reimplementing file system functionality in user space. I'm in doubts that this is considered good design...
Keeping things out of the kernel is good design. Your block indirections are no different to other database formats. Perhaps you think we should have
fsql_operation()and libdb in kernel 8)
For that matter, he could use a database file. I don't know if Postgres (for example) supports streaming read/write from a database record, but if it doesn't it could be made to.
Or if he doesn't want to hack Postgres today, he can put his "metadata" in a database file and the video data in a separate file.
--
Daniel
Quoted 7 lines · Alan Cox
Quoted 2 lines
That is reimplementing file system functionality in user space. I'm in doubts that this is considered good design...
Keeping things out of the kernel is good design. Your block indirections are no different to other database formats. Perhaps you think we should have
fsql_operation()and libdb in kernel 8)
From what I've read, that is where windows is going!
-b
Signature · 5 lines
Number of restrictions placed on "Alice in Wonderland" (public domain) eBook: 5 Maximum penalty for reading "Alice in Wonderland" aloud (possible DMCA violation): 5 years jail Average sentence for commiting Rape: 5 years
Quoted 6 lines · Alan Cox [[email protected]] wrote:
Quoted 2 lines
That is reimplementing file system functionality in user space. I'm in doubts that this is considered good design...
Keeping things out of the kernel is good design. Your block indirections are no different to other database formats. Perhaps you think we should have
fsql_operation()and libdb in kernel 8)
Well, a filesystem that is:
1) synchronous
2) bypasses linux's buffer cache
3) insert() and delete() to insert and delete from the middle of a file.
4) Has large block sizes
Sounds like a possibility for the kernel to me. As with most things, you could do raw disk I/O from userspace, but it seems reasonable to put it in the kernel. Call it "mediafs" or something.
I agree that "normal" filesystems like ext2 should not do the insert() and delete() that were mentioned. It'd be a lot of work and could easily get someone in to trouble (imagine doing it on small files!)
It appears that SGI's XFS does some of this in IRIX. They play some tricks to keep from copying the streaming data. (i.e. same buffer gets passed around as a target for the video device, a source for a userspace program, and a source for DMA to disk) They also have some special flags:
fcentl(fd, F_SETFL, FDIRECT); /* enables direct disk access */
open(filename, O_DIRECT); /* likewise */
See this page for details:
http://reality.sgi.com/cpirazzi_engr/lg/uv/disk.html
Can linux disable its buffer cache for a particular filesystem (something like a 'nocache' mount option?)
Cheers,
-- Bob
Bob McElrath ([email protected]) Univ. of Wisconsin at Madison, Department of Physics
Quoted 1 line
Sounds like a possibility for the kernel to me. As with most things,
But you have it backwards - things are not "could go in the kernel" things are "could avoid being in kernel"
Quoted 7 lines
passed around as a target for the video device, a source for a userspace program, and a source for DMA to disk) They also have some special flags:
fcentl(fd, F_SETFL, FDIRECT); /* enables direct disk access */
open(filename, O_DIRECT); /* likewise */
See this page for details:
http://reality.sgi.com/cpirazzi_engr/lg/uv/disk.html
Andrea has this working on 2.4 + patches
Quoted 3 lines · Alan Cox
Quoted 1 line
open(filename, O_DIRECT); /* likewise */Andrea has this working on 2.4 + patches
Is O_DIRECT slated to go into mainstream 2.4? Or is it a 2.5 thing? Or neither?
-Doug
Signature · 4 lines
Free Dmitry Sklyarov! http://www.freesklyarov.org/ We will return to our regularly scheduled signature shortly.
Quoted 8 lines · Bob McElrath
Quoted 6 lines · Alan Cox [[email protected]] wrote:
Quoted 2 lines
That is reimplementing file system functionality in user space. I'm in doubts that this is considered good design...
Keeping things out of the kernel is good design. Your block indirections are no different to other database formats. Perhaps you think we should have
fsql_operation()and libdb in kernel 8)
Quoted 5 lines
Well, a filesystem that is:
1) synchronous
2) bypasses linux's buffer cache
3)insert()anddelete()to insert and delete from the middle of a file.
4) Has large block sizes
Well, just make it possible to tell something more about the operation you want to do to the kernel/VFS. Copy/Insert/Delete is in fact some sort of sendfile operation. For GLAME I did a "simple" (well, it turned out to be not that simple...) user level filesystem that supports those kind of operations. The interface I chose was
sendfile(dest_fd, source_fd, count, mode)
where mode can be composed out of nothing (overwrite, leave source intact), INSERT and CUT.
As it is a userspace implementation byte granularity is supported, but for a kernel level support I suppose block granularity would suffice and could be optimized for in the lower level filesystems code. I'd prefer such a generic interface over fcntls which would certainly be possible at least for a "split this file into two ones" operation.
Oh yes - it would help to have this in the kernel, at least if you want to support sane mmap behaviour (for block aligned modifications, of course - byte level is impossible due to aliasing issues, I believe).
Richard.
--
Richard Guenther <[email protected]>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/
The GLAME Project: http://www.glame.de/
Quoted 4 lines · Ingo Oeser [[email protected]] wrote:
Quoted 3 lines · Larry McVoy
Quoted 2 lines
What's needed is a generalisation of sparse files and
truncate(). They both handle similar problems.
Quoted 12 lines
Quoted 4 lines
how about
fzero(int fd, off_t off, size_t len)
fdelete(int fd, off_t off, size_t len)and
finsert(int fd, off_t off, size_t len, void *buf, size_t buflen)Quoted 3 lines
The main problem with this is if the off/len are not block aligned. If they are, then this is just block twiddling, if they aren't, then this is a file rewrite anyway.
*exactly* I don't know enough about ext2fs to know if this is possible (i.e. a partially filled block in the middle of a file) so that's why I asked.
Quoted 4 lines
Another solution for the original problem is to rewrite the file in-place by coping from the end of the gap to the beginning of the gap until the gap is shifted to the end of the file and thus can be left to
ftruncate().
For editing commercials, you'd still have to copy 90% of the data. In the US, there's roughly 5 minutes of commercials for every 15 of the show, so that would only save copying the first 15 minutes...
Quoted 3 lines
This will at least not require more space on disk, but will take quite a while and risk data corruption for this file in case of abortion.
Yep. I should mention that the Linux/mjpeg tools
(http://mjpeg.sourceforge.net) already have an elegant way of "marking" a portion of a video and skipping it when playing it, through the use of "edit lists". (use xlav/glav to mark it, and then you can lavplay the edit list, which just contains the start/end of skipped sections) They also have a program to apply the edit list and create a new video (lavtrans). But this requires copying the desired sections of video to a new file, which requires 75% more disk space than the original file, and takes a looong time.
The idea behind my first message should be obvious here...an almost atomic operation modifying at most 2 blocks (and marking a bunch as free) wouldn't require nearly as much disk-thrashing, and would be nearly instantaneous from the user's perspective.
Disk fragmentation is unimportant when the contiguous chunks are 300MB long.
Quoted 3 lines
But fzero, fdelete and finsert might be worth considering, since some file systems, which pack tails could also pack these kind of partial used blocks and handle them properly.
Do the journaling filesystems use blocks in a similar manner to ext2fs? Anyone know if any of them can handle partially filled blocks in the middle of a file?
Are there any media-filesystems out there that have these kinds of extensions? I'm not sure these extensions would be useful for anything but editing media...
Quoted 3 lines
We already handle partial pages, so why not handle them with offset/size pairs and enable this mechanisms? Multi media streams would love these kind of APIs ;-)
Yep yep yep. What do multimedia people use? Custom multi-thousand dollar programs with their own filesystem layer? What about TiVo? Didn't they contribute some fs-layer modifications a while back?
Cheers,
-- Bob
Bob McElrath ([email protected]) Univ. of Wisconsin at Madison, Department of Physics
Re: COW fs (Re: Editing-in-place of a large file)
In reply to Bob McElrathQuoted 22 lines · VDA
Sunday, September 02, 2001, 11:21:37 PM, Bob McElrath wrote:
BM> I would like to take an extremely large file (multi-gigabyte) and edit BM> it by removing a chunk out of the middle. This is easy enough by BM> reading in the entire file and spitting it back out again, but it's BM> hardly efficent to read in an 8GB file just to remove a 100MB segment.BM> Is there another way to do this?
BM> Is it possible to modify the inode structure of the underlying BM> filesystem to free blocks in the middle? (What to do with the half-full BM> blocks that are left?) Has anyone written a tool to do something like BM> this?
BM> Is there a way to do this in a filesystem-independent manner?
A COW fs is a far more useful and cool. A fs where a copy of a file does not duplicate all blocks. Blocks get copied-on-write only when copy of a file is written to. There could be even a fs compressor which looks for and merges blocks with exactly same contents from different files.
Quoted 5 lines
Maybe ext2/3 folks will play with this idea after ext3?
I'm planning to write a test program which will scan my ext2 fs and report how many duplicate blocks with the same contents it sees (i.e how many would I save with a COW fs)
I've tried this idea. I did an MD5 of every block (4KB) in a partition and counted the number of blocks with the same hash. Only about 5-10% of blocks on several filesystem were actually duplicates. This might be better if you reduced the block size to 512 bytes, but there's a question of how much extra space filesystem structures would then take up.
Basically, it didn't look like compressing duplicate blocks would actually be worth the extra structures or CPU.
On the other hand, a COW fs would be excellent for making file copying much quicker. You can do things like copying the linux kernel tree using 'cp -lR', but the files do not act as if they are unique copies - and I've been bitten many times when I forgot this. If you had COW, you could just copy the entire tree and forget about the fact they're linked.
The problem is this needs a bit of userland support, which could only be done automatically if you did this:
- Keep a hash of the contents of blocks in the buffer-cache.
- The kernel compares the hash of each block write to all blocks already in the buffer-cache.
- If a duplicate is found, the kernel generates a COW link instead of writing the block to disk.
Obviously this would involve large amounts of CPU. I think a simple userland call for 'COW this file to this new file' wouldn't be too hideous a solution.
Signature · 1 line
John Ripley
Re: COW fs (Re: Editing-in-place of a large file)
JR> I've tried this idea. I did an MD5 of every block (4KB) in a partition JR> and counted the number of blocks with the same hash. Only about 5-10% of JR> blocks on several filesystem were actually duplicates. This might be JR> better if you reduced the block size to 512 bytes, but there's a JR> question of how much extra space filesystem structures would then take JR> up.
JR> Basically, it didn't look like compressing duplicate blocks would JR> actually be worth the extra structures or CPU.
JR> On the other hand, a COW fs would be excellent for making file copying JR> much quicker. You can do things like copying the linux kernel tree using JR> 'cp -lR', but the files do not act as if they are unique copies - and JR> I've been bitten many times when I forgot this. If you had COW, you JR> could just copy the entire tree and forget about the fact they're JR> linked.
Yeah, I'm mostly thinking about this kind of COW fs usage. You may copy gigabytes in the instant and don't bother about tracking duplicate files ("zero blocks left??? where's the hell I copied that .mpg's???").
Now, sometimes we use hardlinks as "poor man's COW fs", but I bet it's error prone. Every now and then you forget it's a hardlinked kernel tree and start happily hacking in it... :-(
A "compressor" which hunts and merges duplicate blocks is a bonus, not a primary tool.
Signature · 4 lines
Best regards, VDA mailto:[email protected] http://port.imtp.ilyichevsk.odessa.ua/vda/
Re: COW fs (Re: Editing-in-place of a large file)
In reply to Bob McElrathQuoted 30 lines · John Ripley
Quoted 22 lines · VDA
Sunday, September 02, 2001, 11:21:37 PM, Bob McElrath wrote:
BM> I would like to take an extremely large file (multi-gigabyte) and edit BM> it by removing a chunk out of the middle. This is easy enough by BM> reading in the entire file and spitting it back out again, but it's BM> hardly efficent to read in an 8GB file just to remove a 100MB segment.BM> Is there another way to do this?
BM> Is it possible to modify the inode structure of the underlying BM> filesystem to free blocks in the middle? (What to do with the half-full BM> blocks that are left?) Has anyone written a tool to do something like BM> this?
BM> Is there a way to do this in a filesystem-independent manner?
A COW fs is a far more useful and cool. A fs where a copy of a file does not duplicate all blocks. Blocks get copied-on-write only when copy of a file is written to. There could be even a fs compressor which looks for and merges blocks with exactly same contents from different files.
Quoted 5 lines
Maybe ext2/3 folks will play with this idea after ext3?
I'm planning to write a test program which will scan my ext2 fs and report how many duplicate blocks with the same contents it sees (i.e how many would I save with a COW fs)
Quoted 6 lines
I've tried this idea. I did an MD5 of every block (4KB) in a partition and counted the number of blocks with the same hash. Only about 5-10% of blocks on several filesystem were actually duplicates. This might be better if you reduced the block size to 512 bytes, but there's a question of how much extra space filesystem structures would then take up.
Thought I'd reply to myself with some more details :)
Scanning for duplicates gave the following results:
512 byte blocks
----------------
/dev/sda5 - swap - 32122 blocks, 11488 duplicates, 35.76% /dev/sdb3 - swap - 25297 blocks, 2302 duplicates, 9.09% /dev/sdc5 - swap - 34122 blocks, 10239 duplicates, 30.00%
/dev/sda6 - /tmp - 210845 blocks, 17697 duplicates, 8.39%
/dev/sda7 - /var - 32122 blocks, 5327 duplicates, 16.58% /dev/sdb5 - /home - 220885 blocks, 24541 duplicates, 11.11%
/dev/sdc7 - /usr - 1084379 blocks, 122370 duplicates, 11.28%
4096 byte blocks
----------------
/dev/sda5 - swap - 32122 blocks, 9799 duplicates, 30.50% /dev/sdb3 - swap - 26105 blocks, 0 duplicates, 0.00% /dev/sdc5 - swap - 34122 blocks, 10539 duplicates, 30.88%
/dev/sda6 - /tmp - 210845 blocks, 17880 duplicates, 8.48% /dev/sda7 - /var - 32122 blocks, 2816 duplicates, 8.76% /dev/sdb5 - /home - 220885 blocks, 8908 duplicates, 4.03%
/dev/sdc7 - /usr - 1084379 blocks, 71778 duplicates, 6.61%
Interesting results for the swap partitions. Probably full of zeros. The time between runs probably explains the difference in /tmp.
You can grab the program I used from
http://www.pslam.demon.co.uk/md5-stuff.tar.gz
Run with ./md5device </dev/blah
Signature · 1 line
John Ripley
Re: COW fs (Re: Editing-in-place of a large file)
le dim 09-09-2001 at 18:30 John Ripley a _rit :
Quoted 4 lines
/dev/sda6- /tmp - 210845 blocks, 17697 duplicates, 8.39%/dev/sda7 - /var - 32122 blocks, 5327 duplicates, 16.58% /dev/sdb5 - /home - 220885 blocks, 24541 duplicates, 11.11%
/dev/sdc7- /usr - 1084379 blocks, 122370 duplicates, 11.28%
How many of these blocks actually belong to file data ?
Xav
Re: COW fs (Re: Editing-in-place of a large file)
In reply to Bob McElrathQuoted 9 lines · Xavier Bestel
le dim 09-09-2001 at 18:30 John Ripley a
_rit:Quoted 4 lines
/dev/sda6 - /tmp - 210845 blocks, 17697 duplicates, 8.39% /dev/sda7 - /var - 32122 blocks, 5327 duplicates, 16.58% /dev/sdb5 - /home - 220885 blocks, 24541 duplicates, 11.11% /dev/sdc7 - /usr - 1084379 blocks, 122370 duplicates, 11.28%How many of these blocks actually belong to file data ?
Hmm, good point:
Filesystem 1024-blocks Used Available Capacity Mounted on
/dev/sda6 841616 4508 837108 1% /tmp /dev/sda7 124407 63774 54209 54% /var /dev/sdb5 855138 677328 177810 79% /home /dev/sdc7 4191237 3946214 245023 94% /usr
My thinking was that I've managed to run out of space on all of the partitions in the past and had to prune a lot of stuff... so nearly all the blocks should contain at least some "likely" data. Still, I guess I need to verify that this isn't distorting the results. The program needs to recurse over all files on the filesystem rather than all blocks on a partition.
Signature · 1 line
John Ripley
Re: COW fs (Re: Editing-in-place of a large file)
In reply to Bob McElrathQuoted 1 line · John Ripley
Interesting results for the swap partitions. Probably full of zeros.
It doesn't make a lot of sense to spend 30-35% of your swap bandwidth swapping zeros in and out, does it?
--
Daniel
Re: COW fs (Re: Editing-in-place of a large file)
if sectors full of zeros are really that common then they should never be swapped out, just a new page allocated and zeroed when it would be swapped back in. Even better then combining all of them into one block on disk.
David Lang
Quoted 20 lines · Daniel Phillips
Date: Mon, 10 Sep 2001 04:43:53 +0200
From: Daniel Phillips <[email protected]>
To: John Ripley <[email protected]>, [email protected]
Cc: VDA <[email protected]>
Subject: Re: COW fs (Re: Editing-in-place of a large file)Quoted 1 line · John Ripley
Interesting results for the swap partitions. Probably full of zeros.
It doesn't make a lot of sense to spend 30-35% of your swap bandwidth swapping zeros in and out, does it?
--
Daniel
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: COW fs (Re: Editing-in-place of a large file)
In reply to Bob McElrathQuoted 6 lines · John Ripley
My thinking was that I've managed to run out of space on all of the partitions in the past and had to prune a lot of stuff... so nearly all the blocks should contain at least some "likely" data. Still, I guess I need to verify that this isn't distorting the results. The program needs to recurse over all files on the filesystem rather than all blocks on a partition.
You can find a program that does that at:
http://www.stud.ntnu.no/~ragnarkj/download/duplicates.tgz
And results from running on a few different filesystem-types (webpages, users home directories, softwareand so on) were posted to reiserfs-list long time ago - look in the archives if you're curious.
Signature · 2 lines
Ragnar Kjørstad Big Storage
Re: COW fs (Re: Editing-in-place of a large file)
In reply to Bob McElrathOn Mon, Sep 10, 2001 at 12:28:51PM +0300, VDA mentioned:
Quoted 3 lines
Now, sometimes we use hardlinks as "poor man's COW fs", but I bet it's error prone. Every now and then you forget it's a hardlinked kernel tree and start happily hacking in it... :-(
And of course hardlinks don't work on directories...
Quoted 2 lines
A "compressor" which hunts and merges duplicate blocks is a bonus, not a primary tool.
Checkout http://freshmeat.net/projects/fslint/ - it's an excellent tool
for hunting down duplicate files, dangling links etc.
Kate
Signature · 4 lines
_______________________________________ John Looney Chief Scientist a n t e f a c t o t: +353 1 8586004 www.antefacto.com f: +353 1 8586014
Re: COW fs (Re: Editing-in-place of a large file)
In reply to Bob McElrathIs there any FS that have dynamic allocation?
On one partition can reside a number of FSs and using only needed space? this
would be really cute - HD behaves just like RAM.
Some FSs on partition just like number files on FS. In other words "File Systems' System".
google and altavista both show nothing...
PS Interesting like academic task. Hm. Will invistigate.
Quoted 10 lines · Xavier Bestel
le dim 09-09-2001 at 18:30 John Ripley a
_rit:Quoted 4 lines
/dev/sda6 - /tmp - 210845 blocks, 17697 duplicates, 8.39% /dev/sda7 - /var - 32122 blocks, 5327 duplicates, 16.58% /dev/sdb5 - /home - 220885 blocks, 24541 duplicates, 11.11% /dev/sdc7 - /usr - 1084379 blocks, 122370 duplicates, 11.28%How many of these blocks actually belong to file data ?
begin:vcard
n:Filiapau;Ihar
tel;pager:+375 (0) 17 2850000#6683 tel;fax:+375 (0) 17 2841537
tel;home:+375 (0) 17 2118441
tel;work:+375 (0) 17 2841371 x-mozilla-html:TRUE
url:www.iph.to
org:Enformatica Ltd.;Linux Developement Department adr:;;Kalinine str. 19-18;Minsk;BY;220012;Belarus version:2.1
email;internet:[email protected] title:Software Developer
note:(none)
x-mozilla-cpt:;18368
fn:Philips
end:vcard
Re: COW fs (Re: Editing-in-place of a large file)
[ Charset KOI8-R unsupported, converting... ]
Quoted 6 lines
Is there any FS that have dynamic allocation?
On one partition can reside a number of FSs and using only needed space? this
would be really cute - HD behaves just like RAM.
Quoted 6 lines
Some FSs on partition just like number files on FS. In other words "File Systems' System".
google and altavista both show nothing...
PS Interesting like academic task. Hm. Will invistigate.
Are you thinking something similar than AdvFS of Tru 64 ?
( storage or partition is called as 'volume'
and filesystems which share volume are called as 'filesets' )
Signature · 4 lines
/"\ | Kari
\ / ASCII Ribbon Campaign | Hurtta
X Against HTML Mail |
/ \ |Re: COW fs (Re: Editing-in-place of a large file)
In reply to Bob McElrathHi!
Quoted 17 lines
Quoted 8 lines
le dim 09-09-2001 at 18:30 John Ripley a
_rit:Quoted 4 lines
/dev/sda6 - /tmp - 210845 blocks, 17697 duplicates, 8.39% /dev/sda7 - /var - 32122 blocks, 5327 duplicates, 16.58% /dev/sdb5 - /home - 220885 blocks, 24541 duplicates, 11.11% /dev/sdc7 - /usr - 1084379 blocks, 122370 duplicates, 11.28%How many of these blocks actually belong to file data ?
Hmm, good point:
Filesystem 1024-blocks Used Available Capacity Mounted on
/dev/sda6 841616 4508 837108 1% /tmp /dev/sda7 124407 63774 54209 54% /var /dev/sdb5 855138 677328 177810 79% /home /dev/sdc7 4191237 3946214 245023 94% /usr
Quoted 6 lines
My thinking was that I've managed to run out of space on all of the partitions in the past and had to prune a lot of stuff... so nearly all the blocks should contain at least some "likely" data. Still, I guess I need to verify that this isn't distorting the results. The program needs to recurse over all files on the filesystem rather than all blocks on a partition.
just cat /dev/urandom > file to fill it with garbage
Signature · 2 lines
Philips Velo 1: 1"x4"x8", 300gram, 60, 12MB, 40bogomips, linux, mutt, details at http://atrey.karlin.mff.cuni.cz/~pavel/velo/index.html.
Re: COW fs (Re: Editing-in-place of a large file)
In reply to Bob McElrathHi!
Quoted 7 lines
- Keep a hash of the contents of blocks in the buffer-cache.
- The kernel compares the hash of each block write to all blocks already in the buffer-cache.
- If a duplicate is found, the kernel generates a COW link instead of writing the block to disk.Obviously this would involve large amounts of CPU. I think a simple
Why? If you hashed the hashes, you could do it very fast.
Pavel
Signature · 2 lines
Philips Velo 1: 1"x4"x8", 300gram, 60, 12MB, 40bogomips, linux, mutt, details at http://atrey.karlin.mff.cuni.cz/~pavel/velo/index.html.