lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date:	Wed, 08 Sep 2010 19:05:47 +0800
From:	Miao Xie <miaox@...fujitsu.com>
To:	Andi Kleen <andi@...stfloor.org>
CC:	Peter Zijlstra <peterz@...radead.org>,
	Ingo Molnar <mingo@...hat.com>,
	Andrew Morton <akpm@...ux-foundation.org>,
	"Theodore Ts'o" <tytso@....edu>,
	Linux Kernel <linux-kernel@...r.kernel.org>,
	Linux Ext4 <linux-ext4@...r.kernel.org>,
	Linux Btrfs <linux-btrfs@...r.kernel.org>
Subject: Re: [PATCH V2 1/3] lib: introduce some memory copy macros and functions

Hi, Andi

On Thu, 2 Sep 2010 12:40:08 +0200, Andi Kleen wrote:
>> So I improve the generic version of memcpy and memmove, and x86_64's memmove
>> which are implemented by byte copy.
>
> One should also add that most memmove()s and memcpy()s are actually
> generated by gcc as inlines (especially if you don't use the
> "make my code slow" option aka -Os) and don't use the fallback.
> The fallback depends on the gcc version and if gcc thinks the
> data is aligned or not.
>
> Sometimes one can get better code in the caller by making sure
> gcc knows the correct alignment (e.g. with suitable
> types) and size. This might be worth looking at for btrfs
> if it's really that memmove heavy.

Right! But the src address and dest address is not fixed, so it is hard to
tell gcc that the address is alignment or not.

The problem is memmove is very inefficient in fact, and it is used at some fast path,
such as: it is used to do metadata copy for filesystem, so we must improve it.

>>> I have some systemtap scripts to measure size/alignment distributions of
>>> copies on a kernel, if you have a particular workload you're interested
>>> in those could be tried.
>>
>> Good! Could you give me these script?
>
> ftp://firstfloor.org/pub/ak/probes/csum.m4
>
> You need to run them through .m4 first.
> They don't measure memmove, but that should be easy to add.

I used your script to measure size/alignment distributions of copies on a kernel when
I ran the btrfs test, and got some data:

memmove
total 325903
length
value |-------------------------------------------------- count
     1 |                                                       0
     2 |                                                       0
     4 |                                                       3
     8 |                                                       0
    16 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@                       57062
    32 |@@                                                  5903
    64 |@@@                                                 7296
   128 |@@@@@@@@@                                          18868
   256 |@@@@@@@@@@@@@@@@@                                  33790
   512 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                   64886
  1024 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 98450
  2048 |@@@@@@@@@@@@@@@@@@@@                               39645
  4096 |                                                       0
  8192 |                                                       0

length upto 50
value |-------------------------------------------------- count
     2 |                                                        0
     3 |                                                        0
     4 |                                                        3
     5 |                                                        0
     6 |                                                        0
       ~
    21 |                                                        0
    22 |                                                        0
    23 |                                                       24
    24 |                                                        0
    25 |@@@@@@@@@@                                          57037
    26 |                                                        0
    27 |                                                        0
       ~
    29 |                                                        0
    30 |                                                        0
    31 |                                                        1
    32 |                                                        3
    33 |                                                       78
    34 |                                                      215
    35 |                                                     1865
    36 |                                                      432
    37 |                                                        0
    38 |                                                        0
    39 |                                                        0
    40 |                                                        0
    41 |                                                      130
    42 |                                                        0
    43 |                                                       80
    44 |                                                        0
    45 |                                                        0
    46 |                                                        0
    47 |                                                        0
    48 |                                                       80
    49 |                                                        0
    50 |                                                     1077
   >50 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@  264878

src unalignments
value |-------------------------------------------------- count
     0 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@       23173
     1 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                  17623
     2 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@      23760
     3 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                  17372
     4 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@               19185
     5 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@  26264
     6 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@             20288
     7 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                18474
     8 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@             20160
     9 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                  17754
    10 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@           21450
    11 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                 18127
    12 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@        23075
    13 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                18582
    14 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@          21879
    15 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                18737
    16 |                                                       0

dst unalignments
value |-------------------------------------------------- count
     0 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@  28566
     1 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                     17449
     2 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@               20980
     3 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                     17239
     4 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                     17171
     5 |@@@@@@@@@@@@@@@@@@@@@@@@@@@                        15691
     6 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                20558
     7 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                   18590
     8 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@               20644
     9 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@              21459
    10 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                20384
    11 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                 19460
    12 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@           23087
    13 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                 19656
    14 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@     26330
    15 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                   18639
    16 |                                                       0

same unalignments
value |-------------------------------------------------- count
     0 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@  5695
     1 |@@@@@@@@@@@@@@@                                    1815
     2 |@@@@@@@@@@@@@@@@@@@@@@@@@                          2850
     3 |@@@@@@@@@@@@@@@                                    1819
     4 |@@@@@@@@@@@@@@@@@@@@@@@@                           2791
     5 |@@@@@                                               573
     6 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                      3358
     7 |@@@@@@@@@@@@@@@@@@@@@                              2411
     8 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                      3340
     9 |@@@@@@@@@@@@@@@@@@@@@                              2404
    10 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                     3475
    11 |@@@@@@@@@@@@@@@@@@@@@@@@@@                         3019
    12 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@               4153
    13 |@@@@@@@@@@@@@@@@@@@@@@@@@@                         3052
    14 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@               4212
    15 |@@@@@@@@@@@@@@@@@@@@@@@@@@                         3011
    16 |                                                      0

different unalignments
value |-------------------------------------------------- count
     0 |                                                       0
     1 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                      41652
     2 |@@@@@@@@@@@@@@@@@@                                 25447
     3 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@  69946
     4 |@                                                   1800
     5 |@                                                   1701
     6 |@                                                   1573
     7 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@       62478
     8 |                                                     810
     9 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                49180
    10 |                                                     684
    11 |                                                     148
    12 |                                                    1148
    13 |@@@@@@@@@@                                         15298
    14 |@@                                                  3459
    15 |@                                                   2601
    16 |                                                       0

According to the data, the length of the most copies is >=128.

Besides that I did some tests for various condition on my x86_64 box.
The test is doing 500 bytes memory copy for 50000 times.

The test result is following:

dest < src || dest >= src + len:
Length	Src Unalign	Dest Unalign	Without Patch	Patch applied
------	-----------	------------	-------------	-------------
8	0		0		0s 223086us	0s 230612us
8	0		3		0s 133857us	0s 138364us
8	0		6		0s 133852us	0s 138364us
8	3		0		0s 133845us	0s 138365us
8	3		3		0s 133845us	0s 138364us
8	3		6		0s 133841us	0s 138363us
8	6		0		0s 133848us	0s 138364us
8	6		3		0s 133842us	0s 138363us
8	6		6		0s 133840us	0s 138360us
16	0		0		0s 133847us	0s 138364us
16	0		3		0s 133851us	0s 138362us
16	0		6		0s 133842us	0s 138368us
16	3		0		0s 133849us	0s 138360us
16	3		3		0s 133844us	0s 138362us
16	3		6		0s 133839us	0s 138365us
16	6		0		0s 133845us	0s 138359us
16	6		3		0s 133841us	0s 138368us
16	6		6		0s 133841us	0s 138363us
32	0		0		0s 160914us	0s 165435us
32	0		3		0s 160925us	0s 165427us
32	0		6		0s 160898us	0s 165443us
32	3		0		0s 160930us	0s 165432us
32	3		3		0s 160898us	0s 165434us
32	3		6		0s 160919us	0s 165433us
32	6		0		0s 160909us	0s 165436us
32	6		3		0s 160914us	0s 165425us
32	6		6		0s 160910us	0s 165439us
256	0		0		0s 294756us	0s 299280us
256	0		3		0s 500777us	0s 505367us
256	0		6		0s 655671us	0s 660232us
256	3		0		0s 497769us	0s 503386us
256	3		3		0s 497790us	0s 502358us
256	3		6		0s 500793us	0s 505253us
256	6		0		0s 497751us	0s 503097us
256	6		3		0s 497773us	0s 502242us
256	6		6		0s 497769us	0s 502192us
1024	0		0		0s 457170us	0s 461843us
1024	0		3		1s 655705us	1s 660707us
1024	0		6		2s 388031us	2s 391429us
1024	3		0		1s 652717us	1s 660362us
1024	3		3		2s 755214us	1s 657005us
1024	3		6		1s 655735us	1s 660939us
1024	6		0		1s 669425us	1s 662643us
1024	6		3		1s 653472us	1s 659986us
1024	6		6		1s 653559us	1s 662163us

dest > src && dest < src + len:
Length	Src Unalign	Dest Unalign	Without Patch	Patch applied
------	-----------	------------	-------------	-------------
8	0		3		0s 45029us	0s 45775us
8	0		6		0s 43634us	0s 48014us
8	3		0		0s 43625us	0s 43993us
8	3		6		0s 44324us	0s 45081us
8	6		0		0s 43613us	0s 44014us
8	6		3		0s 43620us	0s 44011us
16	0		0		0s 67680us	0s 49631us
16	0		3		0s 67677us	0s 77417us
16	0		6		0s 67671us	0s 81879us
16	3		0		0s 67676us	0s 52492us
16	3		3		0s 67675us	0s 75199us
16	3		6		0s 67677us	0s 81215us
16	6		0		0s 67673us	0s 52490us
16	6		3		0s 67676us	0s 77304us
16	6		6		0s 67676us	0s 79712us
32	0		0		0s 115800us	0s 49632us
32	0		3		0s 115812us	0s 81214us
32	0		6		0s 115792us	0s 85728us
32	3		0		0s 116488us	0s 60198us
32	3		3		0s 115803us	0s 79709us
32	3		6		0s 115798us	0s 85726us
32	6		0		0s 115844us	0s 60202us
32	6		3		0s 115805us	0s 81212us
32	6		6		0s 115802us	0s 84228us
256	0		0		0s 815079us	0s 91737us
256	0		3		0s 815075us	0s 194652us
256	0		6		0s 815079us	0s 198521us
256	3		0		0s 815074us	0s 171470us
256	3		3		0s 817181us	0s 114299us
256	3		6		0s 816478us	0s 198524us
256	6		0		0s 815822us	0s 173566us
256	6		3		0s 814936us	0s 196515us
256	6		6		0s 815152us	0s 118811us
1024	0		0		3s 125598us	0s 244644us
1024	0		3		3s 132574us	0s 590261us
1024	0		6		3s 125613us	0s 595143us
1024	3		0		3s 128452us	0s 568743us
1024	3		3		3s 124862us	0s 263189us
1024	3		6		3s 127440us	0s 595515us
1024	6		0		3s 122370us	0s 569479us
1024	6		3		3s 127429us	0s 590554us
1024	6		6		3s 126732us	0s 269415us

Though there is little regression when the length is <=16, theperformance
is quite well when the length is >=32.

Thanks!
Miao
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Powered by blists - more mailing lists