After finding a major mismatch between the model I outlined and how J
actually works, I have fixed all remaining bugs with the new memory
model. The only work left now is to rewrite 7!:0 when not all objects
reside on the stack. Long explanation of the changes follows. They've
been pushed to the refcount branch again.
In my original proof, I assumed that
2. When EPILOG(z) is called, z and its descendants obey the reference
count formula.
This is actually never true, except in the trivial case that z has no
descendants. Instead, the following holds:
2. After executing the funny series of operations in EPILOG that come
before derec, z and those of its descendants popped by tpop obey the
reference count formula.
Not as good. Let's look at this series of operations (best viewed in
monospace):
initial state (b is a descendent of a)
| |
a 1 -> b 1
ra(a)
| |
a 2 -> b 2
tpop(old)
a 1 -> b 1
tpush(a)
|
a 1 -> b 2
derec(a)
| |
a.1 -> b.2
The vertical bars are references from the stack to objects. The number
next to each object is its reference count (with a dot for non-recursive
counts), and arrows between them are references. The reference count
formula states that the count of each object is equal to the sum, for
each referrer that refers to it, of 1 if that referrer is the stack or a
non-recursive object, and that object's reference count if it is a
recursive object. This formula is wrong until after tpush! Before tpop,
b's reference count is too high, and after it a's count is too high.
Here's a problem that occurred in the tests various times. It happens if
b and c are created in a function with no EPILOG, and then a is created
in a function with an EPILOG.
initial (assume only a is above old on the stack)
| | |
a 1 -> b 1 -> c 1
ra(a)
| | |
a 2 -> b 2 -> c 2
tpop(old)
| |
a 1 -> b 2 -> c 2
tpush(a)
| | |
a 1 -> b 2 -> c 2
derec(a)
| | |
a.1 -> b.2 -> c.1
Our formula is wrong all the way through! Because b is never popped from
the stack, its reference count is higher than 1 when tpush is called,
and this isn't reflected in c's reference count, which should be 3. So
when derec is called, it removes excess references from c which were
never there, and c's count ends up being one too low. Once b and c are
taken off the stack (say at the end of the current sentence), b's count
goes to 1 but c's goes to 0, and c is freed leaving a dangling
reference.
The problem was that I had treated the discrepancy in reference counts
like an "implicit reference" from a to b. Thus to fix it, we should call
ra(a), making it into a real reference, and clear the stack under it.
But this ra call never happens for objects which aren't EPILOGged. Their
descendants end up with no indication of the reference. Instead, I need
a different reference count formula, which will actually hold when
EPILOG is called. This requires a new flag, although there are perhaps
other methods in which it wouldn't.
We define the flag AFCLR. The absence of this flag indicates that the
stack reference is not propagated to descendants (this only makes sense
for recursive objects. The AFCLR flag will always be on for
non-recursive objects). Initially AFCLR is off. There are two situations
in which we should turn AFCLR on for object w, and the discrepancy is
corrected in each case:
- w is popped from the stack. tpop uses fa, which non-recursively
decreases w's reference count.
- w is made non-recursive. We account for the missing reference by
decrementing the counts of w's descendants by one less than we usually
would.
Here's how that works for our problem scenario before. Objects with
AFCLR and AFREC set are marked with *.
initial
| | |
a 1 -> b 1 -> c 1
ra
| | |
a 2 -> b 2 -> c 2
tpop
| |
a*1 -> b 2 -> c 2
tpush
| | |
a*1 -> b 2 -> c 2
derec
| | |
a.1 -> b.2 -> c.2
You can verify that the modified reference count formula is true all the
way through. The reference count of each object is the sum of the counts
of its referrers, minus one for each referrer without a *. Once derec is
called, c's count of 2 matches with its two referrers.
Marshall
On Mon, May 23, 2016 at 06:29:13PM -0400, Marshall Lochbaum wrote:
> I have modified cp.c, cx.c, and vgauss.c and am back to no new test
> failures. Test failures in all three sparse tests have mysteriously
> vanished. This is not incredibly surprising because those failures could
> have been caused by omitting gc on the simpler functions, some of which
> deal with sparse arrays. However, it would be nice to get Valgrind
> working to see if there are use-after-frees which are still there but
> aren't causing any bugs in those particular tests.
>
> For cx.c and vgauss.c I just replaced gc with a version that doesn't use
> derec. This is essentially the same as the old functionality except that
> objects are not pushed to the stack recursively, so we still get some
> improvement in performance. For cp.c I actually rewrote the relevant
> operations.
>
> It turns out it's not actually safe to call derec on an object on the
> stack of unknown origin, because it may have implicit references to
> children which are on the stack. The only known safe way to
> derecursivize an object is with gc (or gc3), which is safe by
> construction. Here are the rules for performing a running update of
> object x:
>
> - Ensure that x is not recursive. Calling derec immediately after GA is
> safe, since x has no children yet.
> - After creating a value z which will be added to x, call gc(z,old).
> Stack index old should be should be set late enough so that nothing
> important is clobbered (in particular, the original copy of x).
> - Before adding z to x, call ra(z). Since ra(z) returns z, you can just
> write xv[k]=ra(z) or similar.
>
> Changes have been pushed to the refcount branch again. Remaining
> problems are that 7!:0 doesn't work and that tests g13x, g5x2, and gq
> fail.
>
> Marshall
>
> On Mon, May 23, 2016 at 04:17:52PM -0400, Marshall Lochbaum wrote:
> > w should be made non-recursive before doing anything else--otherwise we
> > would have to keep track of whether it is or not during the loop. So
> > adding it to the stack just increments the reference count, and popping
> > it decrements it again. No danger of messing with child reference counts
> > or anything.
> >
> > I made the changes to the two files I mentioned, and naturally there are
> > still test failures beyond those with no-op gc. They shouldn't take too
> > long to work out, though. I'm tired enough of actually reading code that
> > I think I'll just do a binary search on instances of gc...
> >
> > Marshall
> >
> > On Mon, May 23, 2016 at 03:59:25PM -0400, Henry Rich wrote:
> > > You are right, provided you are sure w is off the stack. If you can
> > > be sure of that, it's better to derec the child as you add it.
> > >
> > > I also answered my question about the use of jt->tbase.
> > >
> > > Henry
> > >
> > > On 5/23/2016 1:56 PM, Marshall Lochbaum wrote:
> > > >I don't see why tpopnotw would be any better than just leaving w off the
> > > >stack (or, perhaps, why leaving w off the stack is flawed). The only
> > > >reason these functions break our current system is that they add a
> > > >recursive object as a child of a non-recursive one. So calling derec on
> > > >the children solves the problem, and any other changes are for
> > > >performance. And tpopexcept is clearly going to be slower than just
> > > >tpop. So what's the benefit?
> > > >
> > > >Marshall
> > > >
> > > >On Sun, May 22, 2016 at 12:17:19PM -0400, Henry Rich wrote:
> > > >>no, tpopnotw would not leave the w dangling - it would move it (see
> > > >>my latest). It would work like this (you will have to reflect any
> > > >>changes you made to tpop/tpush):
> > > >>
> > > >>tpopexcept(old,w){
> > > >> I wfound = 0; // set if there was a free of w
> > > >> while(old<jt->tbase+jt->ttop){ // till we have freed back to 'old'
> > > >> //?? question: why is 'old <' used rather than 'old !='? Aren't
> > > >> the
> > > >> // blocks of the stack in accidental order, so that this test
> > > >>would fail
> > > >> // if the stack spans a block boundary, and the second block is
> > > >> at a
> > > >> // lower address than the first?
> > > >> if(1<jt->ttop) { // if the stack item is a pointer to a free block
> > > >> A blocktofree = jt->tstack[--jt->ttop]; // fetch address to free
> > > >> if(blocktofree==w)++wfound;else fr(blocktofree); // free it,
> > > >>unless it's w
> > > >> elsetf(); // stack item is a stack-block chain pointer - free
> > > >>the stack block
> > > >> }
> > > >> DO(wfound, tpush(w)); // restore any occurrences of w that were
> > > >>suppressed
> > > >> R old; // return free-to pointer - it may not be the top, if w was
> > > >>restored
> > > >>}
> > > >>
> > > >>I agree that if it's w being changed, nothing special is needed, but
> > > >>this would be a good idea for the other places.
> > > >>
> > > >>What testcase would you like me to look at first?
> > > >>
> > > >>Henry
> > > >>
> > > >>
> > > >>On 5/22/2016 11:52 AM, Marshall Lochbaum wrote:
> > > >>>Replying to both of your comments here.
> > > >>>
> > > >>>Almost all uses of this pattern actually replace w rather than append
> > > >>>to
> > > >>>it. I haven't tested, but I think it's fine in all of these cases to
> > > >>>use
> > > >>>gc or gc3. The exceptions which do modify w are in cp.c and vgauss.c,
> > > >>>although it's possible I missed some.
> > > >>>
> > > >>>tpopnotw isn't possible--the stack is stored in an array, so ignoring w
> > > >>>would just leave it dangling beyond the end of the stack. Your first
> > > >>>suggestion still works, except that derec, rather than ra, makes
> > > >>>objects
> > > >>>non-recursive.
> > > >>>
> > > >>>I've pushed my changes so far to the unbox branch refcount:
> > > >>>https://github.com/iocane/unbox/commits/refcount
> > > >>>
> > > >>>Failing tests are
> > > >>>
> > > >>>- Because 7!:0 is no longer accurate
> > > >>> core/g202.ijs
> > > >>> core/g202b.ijs
> > > >>> core/g7x.ijs
> > > >>> core/glocale.ijs
> > > >>>
> > > >>>- Problem with in-place sparse amends
> > > >>> sparse/gsp530i.ijs
> > > >>> sparse/gsp530l.ijs
> > > >>> sparse/gsp530n.ijs
> > > >>>
> > > >>>- Miscellaneous
> > > >>> core/g13x.ijs
> > > >>> core/g5x2.ijs
> > > >>> core/gq.ijs
> > > >>>
> > > >>>Presumably the last two groups are use-after-frees. Standard tools
> > > >>>don't
> > > >>>work to identify these because of J's pool allocation, and making J use
> > > >>>mallocs instead of pool allocations causes bugs for reasons that are
> > > >>>probably even harder to track down. I have tried to configure Valgrind
> > > >>>to recognize pool allocations (using the requests described at
> > > >>>http://www.network-theory.co.uk/docs/valgrind/valgrind_57.html), but it
> > > >>>seems to only recognize that certain reads/writes are invalid, not the
> > > >>>free that caused them to be invalid. Useless.
> > > >>>
> > > >>>Marshall
> > > >>>
> > > >>>On Sat, May 21, 2016 at 04:29:03PM -0400, Henry Rich wrote:
> > > >>>> store the current stack top in variable old.
> > > >>>> for(...) {
> > > >>>> add something to boxed array w.
> > > >>>> call gc(w,old), putting w in non-recursive form.
> > > >>>> }
> > > >>>>
> > > >>>>What I was suggesting is:
> > > >>>>
> > > >>>> store the current stack top in variable old.
> > > >>>> ra(w);
> > > >>>> for(...) {
> > > >>>> add something to boxed array w.
> > > >>>> ra(something); // putting something in non-recursive form.
> > > >>>> tpop(old);
> > > >>>> }
> > > >>>> tpush(w);
> > > >>>>
> > > >>>>Now I suggest
> > > >>>>
> > > >>>> store the current stack top in variable old.
> > > >>>> for(...) {
> > > >>>> add something to boxed array w.
> > > >>>> ra(something); // putting something in non-recursive form?
> > > >>>> tpopnotw(old,w);
> > > >>>> }
> > > >>>>
> > > >>>>Where tpopnotw is like tpop but simply ignores stack entries that
> > > >>>>match w.
> > > >>>>
> > > >>>>If this idea is sound, I think you might as well do it, because
> > > >>>>
> > > >>>>* you will have to inspect each place gc() is used anyway
> > > >>>>* assuming that the current code is there because the free was needed,
> > > >>>> this preserves that behavior. It will be hard to be confident
> > > >>>> that
> > > >>>> this is not needed (you'd have to deploy and wait for user
> > > >>>> complaints -
> > > >>>> I wouldn't want to take that chance)
> > > >>>>* No usecount will be modified or block freed that doesn't need to be
> > > >>>>* it is necessary to increment the usecount of (something)
> > > >>>>
> > > >>>>Henry
> > > >>>>
> > > >>>>
> > > >>>>
> > > >>>>
> > > >>>>
> > > >>>>
> > > >>>>
> > > >>>>
> > > >>>>
> > > >>>>
> > > >>>>
> > > >>>>
> > > >>>>On 5/20/2016 10:06 AM, Marshall Lochbaum wrote:
> > > >>>>>>>A number of spots in the J source follow this pattern, or similar:
> > > >>>>>>> store the current stack top in variable old.
> > > >>>>>>> for(...) {
> > > >>>>>>> add something to boxed array w.
> > > >>>>>>> call gc(w,old), putting w in non-recursive form.
> > > >>>>>>> }
> > > >>>>>>>
> > > >>>>>>>(A particular example is cp.c, lines 91--97, which performs (v^:l
> > > >>>>>>>x)
> > > >>>>>>>where l is an integer list).
> > > >>>>----------------------------------------------------------------------
> > > >>>>For information about J forums see http://www.jsoftware.com/forums.htm
> > > >>>----------------------------------------------------------------------
> > > >>>For information about J forums see http://www.jsoftware.com/forums.htm
> > > >>----------------------------------------------------------------------
> > > >>For information about J forums see http://www.jsoftware.com/forums.htm
> > > >----------------------------------------------------------------------
> > > >For information about J forums see http://www.jsoftware.com/forums.htm
> > >
> > > ----------------------------------------------------------------------
> > > For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
