45s login delay

[Magnus Nilsson]

Hi all,

@ Matt: Your patch improved it by just a second or two on my rig, so 
that isn't the bottleneck in my case.

@ Peter: I have trouble compiling your code:
In file included from fp_mul_comba.c:365:
fp_mul_comba_small_set.i: In function `fp_mul_comba_small':
fp_mul_comba_small_set.i:1225: internal error--unrecognizable insn:
(insn 91872 37787 37788 (set (mem:SI (plus:SI (plus:SI (reg:SI 11 fp)
                     (const_int -4096 [0xfffff000]))
                 (const_int -740 [0xfffffd1c])) 0)
         (reg:SI 7 r7)) -1 (nil)
     (nil))
make[1]: *** [fp_mul_comba.o] Error 1
It's likely due to my configuration, but could also be a compatibility 
issue in your code. Just thought you might want to know.

Unfortunately I'm pressed for time and must go with openssl for the time 
being. It's a monster size-wise, but at 10s it's usable (just).
If space becomes an even more of a factor, be assured however that I 
will revisit dropbear.

Thank you all for your input and efforts to help.

Kind regards/Magnus

On 2011-03-17 16:23, Matt Johnston wrote:
> On Wed, Mar 16, 2011 at 07:16:34PM -0500, Rob Landley wrote:
>> On 03/16/2011 02:25 AM, Peter Turczak wrote:
>>> Hi Magnus, hi Rob,
>>>
>>> a while ago I made the same observations you did. On an m68k-nommu
>>> with 166 MHz the RSA exchange took quite forever. After some
>>> profiling I found out the comba multiply routine in libtommath was
>>> eating most of the time. It seems gcc produces quite inefficient code
>>> there. Libtommath resizes its large integers while calculating
>>> leading to more work for user memory management.
>> User mememory management?  It's got a malloc/free in an inner loop?  BARF!
>>
>> (Yeah, that'll blow your L1 cache wide open and slow stuff down by at
>> least an order of magnitude.  Allocation functions are some of the most
>> cache unfriendly things you can do, pretty much by definition.  Unused
>> memory is not cache hot, pretty much by definition.  That's sort of the
>> point.  Copying the data sucks too, but it's doing the copying on all
>> platforms I'd guess...)
> I guess it's possible. Logging in to a server with 1024 bit
> RSA and RSA authorized_key I get ~229 reallocs in mp_grow(),
> not a massive number if spread over 45 seconds. The patch
> below drops it to ~30 reallcs.
>
> Magnus: It might be worth seeing if it changes your
> timing. I haven't looked whether it increases memory usage.
>
> Matt
>
> --- libtommath/bn_mp_exptmod_fast.c	5a692f134deeab0992612206c16f8bf970b5088c
> +++ libtommath/bn_mp_exptmod_fast.c	5391873ccf8a11171774425c69f584195b4fdba4
> @@ -67,13 +67,13 @@ int mp_exptmod_fast (mp_int * G, mp_int
>
>     /* init M array */
>     /* init first cell */
> -  if ((err = mp_init(&M[1])) != MP_OKAY) {
> +  if ((err = mp_init_size(&M[1], P->used)) != MP_OKAY) {
>        return err;
>     }
>
>     /* now init the second half of the array */
>     for (x = 1<<(winsize-1); x<  (1<<  winsize); x++) {
> -    if ((err = mp_init(&M[x])) != MP_OKAY) {
> +    if ((err = mp_init_size(&M[x], P->alloc+1)) != MP_OKAY) {
>         for (y = 1<<(winsize-1); y<  x; y++) {
>           mp_clear (&M[y]);
>         }
> @@ -96,7 +96,7 @@ int mp_exptmod_fast (mp_int * G, mp_int
>
>        /* automatically pick the comba one if available (saves quite a few calls/ifs) */
>   #ifdef BN_FAST_MP_MONTGOMERY_REDUCE_C
> -     if (((P->used * 2 + 1)<  MP_WARRAY)&&
> +     if (((P->alloc * 2 + 1)<  MP_WARRAY)&&
>             P->used<  (1<<  ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
>           redux = fast_mp_montgomery_reduce;
>        } else
> @@ -133,7 +133,7 @@ int mp_exptmod_fast (mp_int * G, mp_int
>     }
>
>     /* setup result */
> -  if ((err = mp_init (&res)) != MP_OKAY) {
> +  if ((err = mp_init_size (&res, P->used)) != MP_OKAY) {
>       goto LBL_M;
>     }
>
> ============================================================
> --- libtommath/bn_mp_init_copy.c	fd7c20c0ee3473615de23c59074cf5c6757a20ca
> +++ libtommath/bn_mp_init_copy.c	841949a75e387e818f2f4d9adedff0ba9c9374c0
> @@ -20,7 +20,7 @@ int mp_init_copy (mp_int * a, mp_int * b
>   {
>     int     res;
>
> -  if ((res = mp_init (a)) != MP_OKAY) {
> +  if ((res = mp_init_size (a, b->used)) != MP_OKAY) {
>       return res;
>     }
>     return mp_copy (b, a);
> ============================================================
> --- libtommath/bn_mp_mod.c	3bed12926c4d019853f2b4dac814a7505580380e
> +++ libtommath/bn_mp_mod.c	9265cd0294d2c86f1c3c73eaa5bf19c30403e13b
> @@ -22,7 +22,7 @@ mp_mod (mp_int * a, mp_int * b, mp_int *
>     mp_int  t;
>     int     res;
>
> -  if ((res = mp_init (&t)) != MP_OKAY) {
> +  if ((res = mp_init_size (&t, b->used)) != MP_OKAY) {
>       return res;
>     }
>
> ============================================================
> --- libtommath/bn_mp_mulmod.c	935d0f5903589ddf62f42fc691cb2f83aa2832c4
> +++ libtommath/bn_mp_mulmod.c	ef9063432e3a0c62b7118dfc3d01d04cd4dc8bb9
> @@ -21,7 +21,7 @@ int mp_mulmod (mp_int * a, mp_int * b, m
>     int     res;
>     mp_int  t;
>
> -  if ((res = mp_init (&t)) != MP_OKAY) {
> +  if ((res = mp_init_size (&t, c->used)) != MP_OKAY) {
>       return res;
>     }
>
>