Re: [Gcl-devel] Re: TMP_ALLOC in mpn_mul_n

[Camm Maguire]

Greetings, and thanks for your reply!

Kevin Ryde <address@hidden> writes:

> Camm Maguire <address@hidden> writes:
> >
> > 2) Anyway, all of that is gcl's problem and not gmp's -- but what
> >    about other systems using garbage collection?  The Boehm collector
> >    is becoming more popular these days for example, and it relies on a
> >    redirected malloc as well.
> 
> It reclaims blocks, but doesn't move anything does it?
> 

Perhaps.  Would make sense.

> >    Do you know of any areas off hand in which gmp would
> >    assign a pointer variable, do some allocation, and then access the
> >    original variable which then could be no longer valid?
> 
> That sort of thing is done almost everywhere.  GMP is typical C code,
> when it mallocs one block and then mallocs another it expects the
> first pointer to still be valid.
> 

OK, then gcl will either have to step around, *or* rely on its
traversal of the C stack to find pointers and relocate them.

> >    gmp doesn't save addresses statically anywhere, does it?
> 
> The old-style random number functions might be the only place doing
> that.  Use the new style gmp_randstate_t instead.
> 

Thanks!

> >    In any case, it is
> >    entirely possible that even if gmp does do the former, as long as the
> >    address in question is held in a local variable on the C stack,
> >    gcl's garbage collector will find and 'mark' it.
> 
> On the stack or in registers, as you'd expect from C code.  Oh, and
> mpz_powm stores pointers to malloced blocks within another malloced
> block, if that affects anything.
> 

Thanks again!  gcl appears to only use gmp in a limited number of
pathways.  I'm not yet totally familiar with all of them.

> > 4) It sounds as if you might be aware of some prior conversation with
> >    Dr. Schelter on these points.  Is such a conversation archived
> >    anywhere? 
> 
> It started on bug-gmp, block movement was the only real stumbling
> block, resulting in the patched multiply you've seen, and perhaps also
> tweaks to mpz_setbit and mpz_clrbit.
> 

OK, I see the opening messages in May 2001.  Were the remaining
followups private?  I see no evidence of mpz_{set,clr}bit changes --
can you elaborate further?

> > On Windows, we'll have to build and statically link our
> > own version for the time being.
> 
> Other perverse systems might be similarly afflicted, AIX maybe, not
> sure.


Thanks!  One other observation as I study this -- Dr. Schelter appears
to have explicitly added code ensuring that bignum pointers would be
on the C stack, and therefore relocated by the gc, in code like the
following: 

/* we have to store the body of a u in a bignum object
   so that the garbage collecter will move it and save
   it, and then we can copy it back
*/   
#define GCPROTECT(u) \
 MP_INT * __u = MP(big_gcprotect); \
 (__u)->_mp_d =   (u)->_mp_d; \
 (__u)->_mp_alloc = (u)->_mp_alloc 
#define GC_PROTECTED_SELF (__u)->_mp_d
#define END_GCPROTECT (__u)->_mp_d = 0
 


object
make_bignum(__mpz_struct *u)
{ object ans ;
 int size;
 {BEGIN_NO_INTERRUPT;
 /* make sure we follow the bignum body of u if it gets moved... */
 { GCPROTECT(u);
 ans = alloc_object(t_bignum);
 size = u->_mp_size;
 MP(ans)->_mp_d = 0;
 if (size == 0 )
   size = 1;
 else if (size < 0) size= -size;
 MP(ans)->_mp_d = (mp_ptr) gcl_gmp_alloc (size*MP_LIMB_SIZE);
 MP(ans)->_mp_alloc = size;
 MP(ans)->_mp_size = u->_mp_size;
 memcpy(MP(ans)->_mp_d,GC_PROTECTED_SELF,size*MP_LIMB_SIZE);
 END_GCPROTECT;
 }
 END_NO_INTERRUPT;
 return ans;
 }
} 

What I don't yet fully understand is why the unpatched code would not
similarly have the temporary allocated space referred to by a stack
variable (e.g. ws) already, and thereby be protected from gc:

diff -ruN ../libgmp3-4.0.1/mpn/generic/mul_n.c gmp/mpn/generic/mul_n.c
--- ../libgmp3-4.0.1/mpn/generic/mul_n.c        Thu Jun 28 19:04:08 2001
+++ gmp/mpn/generic/mul_n.c     Sun Jul 28 14:01:36 2002
@@ -1144,9 +1144,15 @@
        * multiplication will take much longer than malloc()/free().  */
       mp_limb_t wsLen, *ws;
       wsLen = MPN_TOOM3_MUL_N_TSIZE (n);
+#ifdef BAD_ALLOCA
       ws = __GMP_ALLOCATE_FUNC_LIMBS ((size_t) wsLen);
+#else
+      ws = TMP_ALLOC ((size_t) wsLen * sizeof(mp_limb_t));
+#endif
       mpn_toom3_mul_n (p, a, b, n, ws);
+#ifdef BAD_ALLOCA
       __GMP_FREE_FUNC_LIMBS (ws, (size_t) wsLen);
+#endif
     }
 #if WANT_FFT || TUNE_PROGRAM_BUILD
   else

The temporary space must have been fine, but rather some other mp
currently in use by gmp and referrred to via an inaccessible variable
got hosed, is my guess.

I'm trying to find a way to convince myself that this patch is the
only one required.

Take care,


> 
> 
> _______________________________________________
> Gcl-devel mailing list
> address@hidden
> http://mail.gnu.org/mailman/listinfo/gcl-devel
> 
> 

-- 
Camm Maguire                                            address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah