594533 - kContainsPointers allocs w/o kZero are bugs waiting to happen

Status: RESOLVED FIXED

(Tamarin Graveyard :: Garbage Collection (mmGC), defect, P3)

Description

[Tommy Reilly]

valgrind informs me that MarkItem is scanning uninitialized data at the end of MethodInfo's array in the space beyond the end of the amount of space asked for but before the end of the block.   

One could argue that the GC shouldn't scan this area but that would require tracking the asked size which we don't do, also since the list classes and others call Size to find out the true capacity we'd have to modify the asked size and make it the true size if they called size.

That aside the GC may be scanning parts of this array before they get written to b/c the abc parser makes other allocations before fully initializing the array.   And what if we had a concurrent scanner it could scan this memory right after the alloc even if no other allocations came before initialization.

The only sane thing to do is require kZero on kContainsPointers allocs and assert otherwise

Comment 1

[Edwin Smith]

(In reply to comment #0)

> One could argue that the GC shouldn't scan this area but that would require
> tracking the asked size which we don't do, also since the list classes and
> others call Size to find out the true capacity we'd have to modify the asked
> size and make it the true size if they called size.

Teasing out an implication of what Tom said:

  MyObject** p = gc->Alloc(7*sizeof(void*), kContainsPointers); // not kZero
  for (i=0; i < 7; i++)
     p[i] = /* some pointer */
  p[7] = 0;  // error, writing past end of allocated size
  int size = gc->Size(p);
  if (size == 32)
     p[7] = /* some pointer */;  // ok, since i called size() first.

I contend that whether the second assignment to p[7] is legal or illegal
should not depend on whether I called Size().

Whether you agree or not is one thing, but the API contract of the GC needs
to lay down the law, one way or the other; for one, it affects valgrind's treatment
of p[7] (initialized or not).

> That aside the GC may be scanning parts of this array before they get written
> to b/c the abc parser makes other allocations before fully initializing the
> array.   And what if we had a concurrent scanner it could scan this memory
> right after the alloc even if no other allocations came before initialization.

There's also this case:

  MyObect** p = gc->Alloc(3 * sizeof(void*), kContainsPointers); // not kZero
  p[0] = /* valid ptr */
  p[2] = /* valid ptr */

If the mutator never reads or writes p[1], no error, right?  well, the GC scans it,
whether or not the GC remembers the original allocation size.  Since the GC scans
it, and its not initialized, it will cause false retention.  A rule for safely using the
gc could state:

   if you allocate kContainsPointer memory, you must initialize it before it
   gets scanned.  (which is the next allocation point, currently, but that could change).

Furthermore, it happens that small blocks are zerod whether you requested it nor not (Tommy tells me), but large blocks arent.  So, the rule could be ammended:

   if you allocate less than THRESHOLD bytes of kContainsPointer memory, you must
   initialize it before it gets scanned.  (which is the next allocation point, currently,
   but that could change).

This seems untenable.  And, combined with the issue of extra room for pointers past
the end of the allocation, the rule would have to be:

   if you allocate less than THRESHOLD bytes of kContainsPointer memory, you must
   initialize it before it gets scanned.  You also must call Size(), and must initialize any
   extra memory the GC gives you, all before the next scan.

Rediculous! hence: what Tommy wrote.

> The only sane thing to do is require kZero on kContainsPointers allocs and
> assert otherwise

Comment 2

[Edwin Smith]

The assert would have to state that you violated a GC API constraint, that all pointer-containing memory must be initialized at allocation time.  on one axis, thats a rule worth debating.

on the other axis, mmgc is a conservative scanner, and you can copy uninitialized values anywhere you want to; whether the scanner sees an uninitialized value on the stack or in the heap is kind of irrelevant (since copies aren't bugs).  So, I think MarkItem needs to mark scanned memory as defined, no matter what kind of block it is.  

We could imagine a different strategy for valgrind annotations specifically for the purposes of debugging an exact scanner, to make sure it doesnt scan uninitialized pointers.  but that's a different set of requirements, i think.

Comment 3

[Lars T Hansen]

I've no opinion about valgrind, but as we're moving toward exact GC this issue is going to come up again and again.  I think required initialization is a no-brainer: anything else will be an invitation to extremely obscure bugs.  If we lose some performance on that then let's try to get it back some other way.

However, /zero/-initialization is only half the battle, and not always the right answer:

(a) An exact scanner does not use the object's size for anything, but rather knowledge about the object's semantics.  And those can be subtle - frequently the object is consistent upon return from some construction function but not always consistent while that function is executing, even for fairly weak notions of consistency.  Consider the following:

In the case of MethodInfo I had to modify the allocation code so that it would be sure to initialize _param_count and  _optional_count /before/ writing into the SlotInfo array beyond element 0 and beyond element _param_count+1 respectively, otherwise the exact scanner (which knows about the length of the array as _param_count+_optional_count+1) would not scan all slots.  A particularly tricky issue here is that while _param_count is known when the object is allocated, _optional_count is not.

Admittedly this kind of problem most often occurs when an array is allocated attached to some object, and with complicated computations for its length brought on by the need for space conservation, as for MethodInfo.  Many array objects are separately allocated and can be allocated with an attached length field that's set at construction time.

(b) While initialization is important, zero-initialization is not always correct for the GC.  The obvious example is atom arrays, where tag zero is "unused", but in this case it's fairly benign even if we treat that value as a conservative pointer (it would be NULL).  Ideally an atom array would be initialized not to zero, but to all 'undefined'.

----

Eventually the clever omission of write barriers here and there will also be a problem, but not yet.

Comment 4

[Tommy Reilly]

Attachment: fix the actual problem, asserts/docs patch forthcoming

Comment 5

[Edwin Smith]

After more thinking, I think the valgrind aspect of this is a red herring, although it's cool that we're having this thread because of what we found with valgrind.   If we're using valgrind to find mutator bugs, and we have a conservative gc, then I think MarkItem needs to mark *all* words defined before computing with them, not just words from stack blocks.  Undefined values can be legally copied into heap blocks, for example.  If the mutator only copies an undefined value and never computes with it, and the only agent doing computations on it is the conservative scanner, then it's not a bug, just one of many possible ways to have false retention.

if we instead were using valgrind to find false retention bugs due to uninitialized memory, *then* we might be interested errors from within MarkItem.  (especially for debugging an exact marker).  So whether we change the initialization rules, I think markitem should just unconditionally mark words as defined.

For initialization, should we be considering requiring both a mark method and an initializer method?

Comment 6

[Lars T Hansen]

I have no idea what you mean by "MarkItem should just unconditionally mark words as defined".

Comment 7

[Edwin Smith]

I'm talking about valgrind annotations in MarkItem, which is what led to finding this bug.  currently the logic is something like:

   ptr = *p++
   if (work item is on the stack)
      VALGRIND_MARK_MEM_DEFINED(&ptr, sizeof(ptr)) // suppress uninitialized read
   // compute stuff with ptr

Tom found a bug when MarkItem scanned uninitialized data in a heap block, which led to the whole discussion about initialization.  (is the bug due to scanning past the end of the allocation, or because the mutator didn't initialize?  begging the question, what are the initialization rules?)

Thats a good discussion, but for the sake of finding mutator bugs, i still think the conservative gc should be invisible, and that the IF guard is probably a bug.  It all comes down to whether you want to know about markitem scanning uninitialized, pointer-containing, heap memory.

Comment 8

[Tommy Reilly]

My experience has been that marking uninitialized memory can lead to catastrophic retention and we want to catch it and make it impossible.   We have had two examples where GCRoot's bypassed the GCRoot:new operator and supplied a custom new which left off the kZero.    What happens it the uninitialized values can contain pointers to the object who's dtor is supposed to delete the root.   Infinite leak results.   I know we're talking about GC memory and not GCRoot's here but in both cases scanning uninitialized data is dangerous bad and we'd be blind folding ourselves to obvious bugs to not have valgrind tell us about it.

Comment 9

[Edwin Smith]

consider it a scope creep warning.

i'm just saying false retention due to uninitialized heap (or root, or stack) memory is not a bug unless you have a concrete GC rule that says it is a bug.  No such rule exists yet.  It makes me very nervous if you start changing the programmer's rules in the middle of developing the valgrind hooks, because it conflates two separate problems into one, and likely will lead to more scope creep.

like i said -- if you're serious about using valgrind to find false retention bugs, then perhaps we leave it as is.  but until yesterday afternoon, that was not the goal for valgrind.

Comment 10

[Tommy Reilly]

duly noted, although I think it should be a rule that you can't have uninitialized data in a heap allocated object scanned by the GC, at least as long as we have a conservative scanner.

Comment 11

[Edwin Smith]

cool.  btw, roots lie inbetween - do we suppress VG errors in MarkItem when marking roots and stack, or just stack?

Comment 12

[Tommy Reilly]

just stack

Comment 13

[Steven Johnson]

So: if we see kContainsPointers without kZero, we assert (but also presumably assume kZero, in case the assertion isn't seen)?

Comment 14

[Lars T Hansen]

(In reply to comment #13)
> So: if we see kContainsPointers without kZero, we assert (but also presumably
> assume kZero, in case the assertion isn't seen)?

The obvious thing would be to say that kContainsPointers implies kZero everywhere, and just leave it at that - no assertion needed.  There's not much sense in forcing programmers to state things that are mandatory anyway.

Comment 15

[Tommy Reilly]

Edwin initially balked when I suggested kContainsPointers automatically imply kZero.   I thought it was a nice way to ensure the right thing was happening w/o auditing all GC::Alloc call sites.   Edwin?

Comment 16

[Edwin Smith]

I probably balked because it felt sloppy (kContainsPointers implies kZero, but only for large allocations), coming on the heels of a discussion about how the GC already zeros small  blocks (whether you ask it to or not), but not large blocks.  If kContainsPointers implies kZero on all allocations, that source of sloppyness goes away.  We'll still have call sites passing in redundant flags, but we can audit & clean up over time.

As long as the API is clearly defined, having kContainsPointers imply kZero is probably less churn.  I dont feel strongly about it, and Postal's Law sides with Tommy & Lars.

Comment 17

[Tommy Reilly]

http://hg.mozilla.org/tamarin-redux/rev/97f101007fbd

removing valgrind block but leaving open for GC fixes

Comment 18

[Tommy Reilly]

Attachment: Turn on zeroing for contains pointers allocations

Comment 19

[Tommy Reilly]

http://hg.mozilla.org/tamarin-redux/rev/fc140e6699a4