Re: Heap memory leak in Pari/GP 2.1.4 during vector operations.

[Karim Belabas <kb@math.u-psud.fr>]

[Alexander Shumakovitch:]
> After some tries, I've managed to trace down the problem to initializations
> of vectors (or matrices) whose entries are going to be vectors as well. I
> used to do it in one operator. But in this case assignment of arbitrary
> values to elements of those vectors grabs some blocks on heap, which are
> not freed even after doing kill().
>
> Here is how to trigger the bug:
>   (20:35) gp > v=vector(2,i,vector(i));v[2][1]=5;getheap
>   time = 0 ms.
>   %2 = [34, 225]
>   (20:35) gp > v=vector(2,i,vector(i));v[2][1]=5;getheap
>   time = 0 ms.
>   %3 = [35, 232]

Please, try the following patch  [or, better, upgrade from CVS stable branch].

I wrote the original code about 8 years ago now [to implement linear time
assignment to GP arrays, former was quadratic in the most favourable
case...], and it should have been junked long ago.

Basic assumption was that 1 level of recursion from the toplevel structure
was enough. The new code is simpler, more robust [and correctly documented],
but possibly a bit slower when huge multidimensional arrays are involved. I
don't see any way around this without implementing a full-fledged garbage
collector [which would probably end up being slower for ordinary scripts...]

Index: init.c
===================================================================
RCS file: /home/megrez/cvsroot/pari/src/language/init.c,v
retrieving revision 1.158
retrieving revision 1.159
diff -c -r1.158 -r1.159
*** src/language/init.c	2002/08/25 22:21:41	1.158
--- src/language/init.c	2002/08/27 12:12:10	1.159
***************
*** 658,669 ****
    return cur_bloc = x;
  }

! void
! killbloc0(GEN x, int inspect)
  {
!   long tx,lx,l,i,j;
!   GEN p1;

    if (!x || isonstack(x)) return;
    if (bl_next(x)) bl_prev(bl_next(x)) = bl_prev(x);
    else
--- 658,689 ----
    return cur_bloc = x;
  }

! /* recursively look for clones in the container and kill them */
! static void
! inspect(GEN x)
  {
!   long i, lx;
!   switch(typ(x)) /* HACK: if x is not a GEN, we have typ(x)=0 */
!   {
!     case t_VEC: case t_COL: case t_MAT:
!       lx = lg(x);
!       for (i=1;i<lx;i++) inspect((GEN)x[i]);
!       break;
!     case t_LIST:
!       lx = lgef(x);
!       for (i=2;i<lx;i++) inspect((GEN)x[i]);
!       break;
!   }
!   if (isclone(x)) gunclone(x); /* Don't inspect here! components are dead */
! }

+ /* If insp is set, recursively inspect x, killing all clones found. The GP
+  * expression x[i] = y is implemented as x[i] := gclone(y) and we need to
+  * reclaim the memory. Useless to inspect when x does not correspond to a GP
+  * variable [not dangerous, though] */
+ void
+ killbloc0(GEN x, int insp)
+ {
    if (!x || isonstack(x)) return;
    if (bl_next(x)) bl_prev(bl_next(x)) = bl_prev(x);
    else
***************
*** 674,718 ****
    if (bl_prev(x)) bl_next(bl_prev(x)) = bl_next(x);
    if (DEBUGMEM > 2)
      fprintferr("killing bloc (no %ld): %08lx\n", bl_num(x), x);
!   if (inspect)
!   {
!     /* FIXME: SIGINT should be blocked at this point */
!     tx=typ(x); /* if x is not a GEN, we will have tx=0 */
!     if (is_vec_t(tx))
!     {
!       lx = lg(x);
!       for (i=1;i<lx;i++)
!       {
!         p1=(GEN)x[i];
!         if (isclone(p1)) killbloc(p1);
!       }
!     }
!     else if (tx==t_MAT)
!     {
!       lx = lg(x);
!       if (lx>1)
!       {
!         l=lg(x[1]);
!         if (l>1)
!           for (i=1;i<lx;i++)
!             for (j=1;j<l;j++)
!             {
!               p1=gmael(x,i,j);
!               if (isclone(p1)) killbloc(p1);
!             }
!       }
!     }
!     else if (tx==t_LIST)
!     {
!       lx = lgef(x);
!       for (i=2;i<lx;i++)
!       {
!         p1=(GEN)x[i];
!         if (isclone(p1)) killbloc(p1);
!       }
!     }
!     unsetisclone(x);
!     /* FIXME: SIGINT should be released here */
    }
    free((void *)bl_base(x));
  }
--- 694,703 ----
    if (bl_prev(x)) bl_next(bl_prev(x)) = bl_next(x);
    if (DEBUGMEM > 2)
      fprintferr("killing bloc (no %ld): %08lx\n", bl_num(x), x);
!   if (insp)
!   { /* FIXME: SIGINT should be blocked until inspect() returns */
!     unsetisclone(x); /* important: oo recursion otherwise */
!     inspect(x);
    }
    free((void *)bl_base(x));
  }

--
Karim Belabas                    Tel: (+33) (0)1 69 15 57 48
Dép. de Mathematiques, Bat. 425  Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud             Email: Karim.Belabas@math.u-psud.fr
F-91405 Orsay (France)           http://www.math.u-psud.fr/~belabas/
--
PARI/GP Home Page: http://www.parigp-home.de/