[gentoo-user] RFC : fast copying of a whole directory tree

[gentoo-user] RFC : fast copying of a whole directory tree

[Helmut Jarausch]

[-- Attachment #1: Type: text/plain, Size: 566 bytes --]

Hi,

when copying a whole directory tree with standard tools, e.g.
tar cf - . | ( cd $DEST && tar xf - )
or  cpio -p ...

the source disk is busy seeking. That's noisy and particularly slow.

I've written a small Python program which outputs the file names in
i-node order. If this is fed into tar or cpio nearly no seeks are 
required during copying.

I've tested it by comparing the resulting copied tree to one created by 
tar | tar.

But it's correctness for backing up data is critical.
Therefore I'd like to ask for comments.

Thanks for any comments,
Helmut.

[-- Attachment #2: TreeWalk_I_Sorted.py --]
[-- Type: text/x-python, Size: 1345 bytes --]

#!/usr/bin/python3
import os, sys, stat


def walktree(top):
    '''recursively descend the directory tree rooted at top,
       calling the callback function for each regular file'''
    for f in os.listdir(top):
        pathname = os.path.join(top, f)
        Stat= os.lstat(pathname)
        Dev = Stat.st_dev
        if  Dev != Root_Dev :
            continue
        Ino = Stat.st_ino
        mode = Stat.st_mode
        if stat.S_ISDIR(mode):
            # It's a directory, recurse into it
            FN_List.append((Ino,pathname))
            walktree(pathname)
        else :
          FN_List.append((Ino,pathname))


if len(sys.argv) != 2 :
  print('''usage:
  TreeWalk_I_Sorted <TOPDIR>  # generates a list of files in inode order
  # example with tar :
  TreeWalk_I_Sorted <TOPDIR> | tar --no-recursion -c -j -T- -f XXX.tar.bz2
  # example with cpio
  TreeWalk_I_Sorted <TOPDIR> | cpio -padmu <DESTDIR>
  ''')
  exit(1)

TOP= sys.argv[1]
Stat= os.lstat(TOP)
Root_Dev= Stat.st_dev
FN_List=[(Stat.st_ino,TOP)]

# import resource
# print("at Start in kB ",resource.getrusage(0).ru_maxrss)
# uses about 500 bytes per file

walktree(TOP)
FN_List.sort()

# print("*** starting ...",file=sys.stderr)
for I,F in FN_List :
  print(F)  #  print(I," -> " ,F)

# print("after loading",len(FN_List)," items : ",resource.getrusage(0).ru_maxrss)

Re: [gentoo-user] RFC : fast copying of a whole directory tree

[Michael Orlitzky]

On 02/13/12 05:49, Helmut Jarausch wrote:
> 
> I've written a small Python program which outputs the file names in
> i-node order. If this is fed into tar or cpio nearly no seeks are 
> required during copying.

What makes you think the inodes are sequential on-disk?


> But it's correctness for backing up data is critical.
> Therefore I'd like to ask for comments.

You're nuts =)

Seriously though, use cp, tar, or rsync. They've seen years of use by
millions of people. All of the remaining bugs are sufficiently insidious
that you'll never hit them. The same probably isn't true for your script!

[gentoo-user] Re: RFC : fast copying of a whole directory tree

[Grant Edwards]

On 2012-02-13, Michael Orlitzky <michael@orlitzky.com> wrote:
> On 02/13/12 05:49, Helmut Jarausch wrote:
>> 
>> I've written a small Python program which outputs the file names in
>> i-node order. If this is fed into tar or cpio nearly no seeks are 
>> required during copying.
>
> What makes you think the inodes are sequential on-disk?

Even if the i-nodes are sequential on-disk, there's no reason to think
that the data blocks associated with the inodes are in any particular
order with respect to the i-nodes themselves.

>> But it's correctness for backing up data is critical.
>> Therefore I'd like to ask for comments.
>
> You're nuts =)
>
> Seriously though, use cp, tar, or rsync. They've seen years of use by
> millions of people. All of the remaining bugs are sufficiently
> insidious that you'll never hit them. The same probably isn't true
> for your script!

-- 
Grant Edwards               grant.b.edwards        Yow! All this time I've
                                  at               been VIEWING a RUSSIAN
                              gmail.com            MIDGET SODOMIZE a HOUSECAT!

Re: [gentoo-user] Re: RFC : fast copying of a whole directory tree

[Joerg Schilling]

Grant Edwards <grant.b.edwards@gmail.com> wrote:

> On 2012-02-13, Michael Orlitzky <michael@orlitzky.com> wrote:
> > On 02/13/12 05:49, Helmut Jarausch wrote:
> >> 
> >> I've written a small Python program which outputs the file names in
> >> i-node order. If this is fed into tar or cpio nearly no seeks are 
> >> required during copying.
> >
> > What makes you think the inodes are sequential on-disk?
>
> Even if the i-nodes are sequential on-disk, there's no reason to think
> that the data blocks associated with the inodes are in any particular
> order with respect to the i-nodes themselves.

Correct, there is however a really fast method using "star -copy".

This works because there are two decoupled processes, shared memory between 
them and the fact that star reads names from directories in one big chunk.

Jörg

-- 
 EMail:joerg@schily.isdn.cs.tu-berlin.de (home) Jörg Schilling D-13353 Berlin
       js@cs.tu-berlin.de                (uni)  
       joerg.schilling@fokus.fraunhofer.de (work) Blog: http://schily.blogspot.com/
 URL:  http://cdrecord.berlios.de/private/ ftp://ftp.berlios.de/pub/schily

Re: [gentoo-user] Re: RFC : fast copying of a whole directory tree

[Pandu Poluan]

[-- Attachment #1: Type: text/plain, Size: 1008 bytes --]

On Feb 13, 2012 11:15 PM, "Joerg Schilling" <
Joerg.Schilling@fokus.fraunhofer.de> wrote:
>
> Grant Edwards <grant.b.edwards@gmail.com> wrote:
>
> > On 2012-02-13, Michael Orlitzky <michael@orlitzky.com> wrote:
> > > On 02/13/12 05:49, Helmut Jarausch wrote:
> > >>
> > >> I've written a small Python program which outputs the file names in
> > >> i-node order. If this is fed into tar or cpio nearly no seeks are
> > >> required during copying.
> > >
> > > What makes you think the inodes are sequential on-disk?
> >
> > Even if the i-nodes are sequential on-disk, there's no reason to think
> > that the data blocks associated with the inodes are in any particular
> > order with respect to the i-nodes themselves.
>
> Correct, there is however a really fast method using "star -copy".
>
> This works because there are two decoupled processes, shared memory
between
> them and the fact that star reads names from directories in one big chunk.
>

Honestly, that's news to me. Which package has star?

Rgds,

[-- Attachment #2: Type: text/html, Size: 1448 bytes --]

[gentoo-user] Re: RFC : fast copying of a whole directory tree

[Nikos Chantziaras]

On 13/02/12 18:29, Pandu Poluan wrote:
>
> On Feb 13, 2012 11:15 PM, "Joerg Schilling"
> <Joerg.Schilling@fokus.fraunhofer.de
> <mailto:Joerg.Schilling@fokus.fraunhofer.de>> wrote:
>  > Correct, there is however a really fast method using "star -copy".
>  >
>  > This works because there are two decoupled processes, shared memory
> between
>  > them and the fact that star reads names from directories in one big
> chunk.
>  >
>
> Honestly, that's news to me. Which package has star?

eix -e star

:-/

Re: [gentoo-user] Re: RFC : fast copying of a whole directory tree

[Pandu Poluan]

[-- Attachment #1: Type: text/plain, Size: 687 bytes --]

On Feb 13, 2012 11:41 PM, "Nikos Chantziaras" <realnc@arcor.de> wrote:
>
> On 13/02/12 18:29, Pandu Poluan wrote:
>>
>>
>> On Feb 13, 2012 11:15 PM, "Joerg Schilling"
>> <Joerg.Schilling@fokus.fraunhofer.de
>> <mailto:Joerg.Schilling@fokus.fraunhofer.de>> wrote:
>>  > Correct, there is however a really fast method using "star -copy".
>>  >
>>  > This works because there are two decoupled processes, shared memory
>> between
>>  > them and the fact that star reads names from directories in one big
>> chunk.
>>  >
>>
>> Honestly, that's news to me. Which package has star?
>
>
> eix -e star
>
> :-/
>

Hehhe... sorry, I'm on the road and don't have Gentoo on my smartphone :-P

Rgds,

[-- Attachment #2: Type: text/html, Size: 1171 bytes --]

Re: [gentoo-user] Re: RFC : fast copying of a whole directory tree

[Joerg Schilling]

Nikos Chantziaras <realnc@arcor.de> wrote:

> >  > This works because there are two decoupled processes, shared memory
> > between
> >  > them and the fact that star reads names from directories in one big
> > chunk.
> >  >
> >
> > Honestly, that's news to me. Which package has star?
>
> eix -e star

To help star to buffer, give star a large fifo size that is up to haslf of the 
RAM in your machine, e.g. fs=1000m

To make sure that star gives fast file creation (unpacking of archives) on 
filesystems that do not support fast verified transactions, you need to make 
star as "insecure" as other software to get comparable results, so add:

	-no-fsync

Jörg

-- 
 EMail:joerg@schily.isdn.cs.tu-berlin.de (home) Jörg Schilling D-13353 Berlin
       js@cs.tu-berlin.de                (uni)  
       joerg.schilling@fokus.fraunhofer.de (work) Blog: http://schily.blogspot.com/
 URL:  http://cdrecord.berlios.de/private/ ftp://ftp.berlios.de/pub/schily

Re: [gentoo-user] Re: RFC : fast copying of a whole directory tree

[Dale]

Joerg Schilling wrote:
> Nikos Chantziaras <realnc@arcor.de> wrote:
> 
>>>  > This works because there are two decoupled processes, shared memory
>>> between
>>>  > them and the fact that star reads names from directories in one big
>>> chunk.
>>>  >
>>>
>>> Honestly, that's news to me. Which package has star?
>>
>> eix -e star
> 
> To help star to buffer, give star a large fifo size that is up to haslf of the 
> RAM in your machine, e.g. fs=1000m
> 
> To make sure that star gives fast file creation (unpacking of archives) on 
> filesystems that do not support fast verified transactions, you need to make 
> star as "insecure" as other software to get comparable results, so add:
> 
> 	-no-fsync
> 
> Jörg
> 


The problem with star is that when I need to copy a large number of
files, it isn't on the DVD I boot from.  That's why most people use cp
since it is on every bootable media I have ever booted.  That includes
the Gentoo bootable media.

Since star is so good, why not get them to include it on the bootable
media?  Is it to large a package or what?

Dale

:-)  :-)

-- 
I am only responsible for what I said ... Not for what you understood or
how you interpreted my words!

Miss the compile output?  Hint:
EMERGE_DEFAULT_OPTS="--quiet-build=n"

Re: [gentoo-user] Re: RFC : fast copying of a whole directory tree

[Neil Bothwick]

[-- Attachment #1: Type: text/plain, Size: 248 bytes --]

On Tue, 14 Feb 2012 00:42:56 +0700, Pandu Poluan wrote:

> Hehhe... sorry, I'm on the road and don't have Gentoo on my
> smartphone :-P

Not even via SSH? :P


-- 
Neil Bothwick

If at first you don't succeed you'll get lots of advice.

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [gentoo-user] Re: RFC : fast copying of a whole directory tree

[Pandu Poluan]

[-- Attachment #1: Type: text/plain, Size: 331 bytes --]

On Feb 14, 2012 6:00 AM, "Neil Bothwick" <neil@digimed.co.uk> wrote:
>
> On Tue, 14 Feb 2012 00:42:56 +0700, Pandu Poluan wrote:
>
> > Hehhe... sorry, I'm on the road and don't have Gentoo on my
> > smartphone :-P
>
> Not even via SSH? :P
>

It's a new phone and I forgot the port-knocking sequence to open the ssh
port >.<

Rgds,

[-- Attachment #2: Type: text/html, Size: 496 bytes --]

Re: [gentoo-user] Re: RFC : fast copying of a whole directory tree

[Florian Philipp]

[-- Attachment #1: Type: text/plain, Size: 1188 bytes --]

Am 13.02.2012 16:31, schrieb Grant Edwards:
> On 2012-02-13, Michael Orlitzky <michael@orlitzky.com> wrote:
>> On 02/13/12 05:49, Helmut Jarausch wrote:
>>>
>>> I've written a small Python program which outputs the file names in
>>> i-node order. If this is fed into tar or cpio nearly no seeks are 
>>> required during copying.
>>
>> What makes you think the inodes are sequential on-disk?
> 
> Even if the i-nodes are sequential on-disk, there's no reason to think
> that the data blocks associated with the inodes are in any particular
> order with respect to the i-nodes themselves.

You could probably find the intended order by using debugfs (at least
for ext*). The following command should output the first physical block
of every file:
find /var/db/portage/ -type f -printf 'bmap <%i> 0\n' | sudo debugfs
/dev/mapper/vg-portage

Todo left as an exercise to the reader:
- Clean debugfs output
- Map inodes back to file names (hint: don't use debugfs's 'ncheck')
- sort | cut | xargs cp

Possible further improvement: Sort the files so that the first block of
the next file is close to the last block of the previous file.

Regards,
Florian Philipp


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 262 bytes --]

Re: [gentoo-user] Re: RFC : fast copying of a whole directory tree

[Joerg Schilling]

Florian Philipp <lists@binarywings.net> wrote:

> > Even if the i-nodes are sequential on-disk, there's no reason to think
> > that the data blocks associated with the inodes are in any particular
> > order with respect to the i-nodes themselves.
>
> You could probably find the intended order by using debugfs (at least
> for ext*). The following command should output the first physical block
> of every file:
> find /var/db/portage/ -type f -printf 'bmap <%i> 0\n' | sudo debugfs
> /dev/mapper/vg-portage

This kind of order is not important for copy speed.

Copy speed is dominated by write speed and write speed is dominated by seeks 
that are a result of keeping meta data up to date.

Jörg

-- 
 EMail:joerg@schily.isdn.cs.tu-berlin.de (home) Jörg Schilling D-13353 Berlin
       js@cs.tu-berlin.de                (uni)  
       joerg.schilling@fokus.fraunhofer.de (work) Blog: http://schily.blogspot.com/
 URL:  http://cdrecord.berlios.de/private/ ftp://ftp.berlios.de/pub/schily

Re: [gentoo-user] Re: RFC : fast copying of a whole directory tree

[Mick]

On 13 February 2012 22:11, Dale <rdalek1967@gmail.com> wrote:
> Joerg Schilling wrote:
>> Nikos Chantziaras <realnc@arcor.de> wrote:
>>
>>>>  > This works because there are two decoupled processes, shared memory
>>>> between
>>>>  > them and the fact that star reads names from directories in one big
>>>> chunk.
>>>>  >
>>>>
>>>> Honestly, that's news to me. Which package has star?
>>>
>>> eix -e star
>>
>> To help star to buffer, give star a large fifo size that is up to haslf of the
>> RAM in your machine, e.g. fs=1000m
>>
>> To make sure that star gives fast file creation (unpacking of archives) on
>> filesystems that do not support fast verified transactions, you need to make
>> star as "insecure" as other software to get comparable results, so add:
>>
>>       -no-fsync
>>
>> Jörg
>>
>
>
> The problem with star is that when I need to copy a large number of
> files, it isn't on the DVD I boot from.  That's why most people use cp
> since it is on every bootable media I have ever booted.  That includes
> the Gentoo bootable media.
>
> Since star is so good, why not get them to include it on the bootable
> media?  Is it to large a package or what?

It used to be in the Knoppix package list, but alas it is no more.  :-(

I still keep my old copy somewhere just for this reason.
-- 
Regards,
Mick

Re: [gentoo-user] Re: RFC : fast copying of a whole directory tree

[Florian Philipp]

[-- Attachment #1: Type: text/plain, Size: 2667 bytes --]

Am 14.02.2012 10:57, schrieb Joerg Schilling:
> Florian Philipp <lists@binarywings.net> wrote:
> 
>>> Even if the i-nodes are sequential on-disk, there's no reason to think
>>> that the data blocks associated with the inodes are in any particular
>>> order with respect to the i-nodes themselves.
>>
>> You could probably find the intended order by using debugfs (at least
>> for ext*). The following command should output the first physical block
>> of every file:
>> find /var/db/portage/ -type f -printf 'bmap <%i> 0\n' | sudo debugfs
>> /dev/mapper/vg-portage
> 
> This kind of order is not important for copy speed.
> 
> Copy speed is dominated by write speed and write speed is dominated by seeks 
> that are a result of keeping meta data up to date.
> 
> Jörg
> 

I cannot verify that hypothesis.

Test setup:
1x 7200rpm 2,5" HDD
/var/db/portage is my portage tree, ext4
/dev/mapper/vg-portage is its block device
/tmp is ext4

First test --- copy whole tree just with `cpio` (performance tested and
similar to `cp -a`):
$ echo 1 >/proc/sys/vm/drop_caches
$ time find /var/db/portage/ -type f -print0 |
$ cpio -p0 --make-directories /tmp/portage/

real    11m52.657s
user    0m1.848s
sys     0m19.802s

Second test --- Sort by starting physical block number:
$ echo 1 >/proc/sys/vm/drop_caches
$ FIFO=/tmp/$(uuidgen).fifo
$ mkfifo "$FIFO"
$ time find /var/db/portage/ -type f \
$	-fprintf "$FIFO" 'bmap <%i> 0\n' -print0 |
$ tr '\n\0' '\0\n' | paste <(
$	debugfs -f "$FIFO" /dev/mapper/vg-portage |
$	grep -E '^[[:digit:]]+') - |
$ sort -k 1,1n | cut -f 2- | tr '\n\0' '\0\n' |
$ cpio -p0 --make-directories /tmp/portage/
$ unlink "$FIFO"

real    2m8.400s
user    0m1.888s
sys     0m15.417s

Using `xargs -0 cat >/dev/null` instead of `cpio` yields 9m27.745s and
1m11.087s, respectively.

Some comments to the sorting script:
- Using a fifo instead of a pipe for issuing commands to debugfs is faster.
- If it is not obvious, the two `tr` commands are there because `paste`
and `cut` cannot handle zero-terminated lines but file names might
contain line breaks.
- `grep` is there because `debugfs` echoes all commands. Filtering every
odd numbered line should also work.
- A production-ready script should probably use `join` instead of
`paste` to deal with read errors of `debugfs` (for example if files are
removed between `find` and `debugfs`). Currently, this leads to
misaligned output.

BTW: I wanted to test it with `star -copy` but this resulted in buffer
overflows similar to these:
http://permalink.gmane.org/gmane.comp.archivers.star.user/752

Regards,
Florian Philipp


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 262 bytes --]