heap memory issues

heap memory issues

[Phil Pennock]

Line numbers are based upon a clean 3.1.5.  All this is Src/mem.c.
None of it delves into the ZSH_MEM allocators -- it's all heap stuff.

The debugging array h_m is declared to be:
  static int h_m[1025];
It seems to be used for tracing the number of allocations of a given
size; however, with an H_ISIZE == sizeof(long), [assuming 4] then
scanning mem.c, it's 3/4 unused.  The first 1024/H_ISIZE entries and
1024 can be filled, the rest will never change from 0.

Also, for 64-bit platforms, might alignment constraints require H_ISIZE
to be sizeof(long long), or can all of them use 32-bit alignment?  The
halloc() and hrealloc() functions seem to rely upon H_ISIZE being a
measure of sufficient alignment for all data-types.

Take a deap breath for the logic here ...

Whilst I haven't tested this, it looks upon reading as though there are
some problems if hrealloc()ing a memory-block that is larger than
HEAP_ARENA_SIZE.  This would only manifest itself on an allocation
larger than about 8176 bytes (varying according to compiler whim).
These are probably sufficiently rare to not crop up too often.
In halloc() line 269, we have:
  n = HEAP_ARENA_SIZE > size ? HEAPSIZE : size + sizeof(*h);
Then in hrealloc() line 335:
  zfree(h, HEAPSIZE);
from a hrealloc(startofhunk, oldverybig, 0) -- the /next/ block checks
for big sizes, just too late.  Changing this to check for
(h->used > HEAP_ARENA_SIZE) first would, as it stands, work FOR THIS
case.  If a previous hrealloc() has gone from greater than
HEAP_ARENA_SIZE to less than HEAP_ARENA_SIZE then a new arena will have
been allocated (lines 338-345), so h->used can't be less than
HEAP_ARENA_SIZE for a big hunk, *BUT* there is the problem that the new
arena thus allocated will be smaller than HEAP_ARENA_SIZE and the
zfree(h, HEAPSIZE) in line 269 now frees too much memory.

Um... just re-read the code if that's confusing.

Hrm, lines 314-316 are:
    DPUTS(!h, "BUG: hrealloc() called for non-heap memory.");
    DPUTS(h->sp && arena(h) + h->sp->used > p,
          "BUG: hrealloc() wants to realloc pushed memory");
If the first DPUTS prints (ie, non-heap memory) then won't this
dereference a null-pointer?  At least dputs() fflush()s stderr, so we
see the error message before getting the core dump.  :^)

Lines 318-325 handle reallocating from the middle of an arena  --
should this do a memset() to 0xff if ZSH_MEM_DEBUG, or is that only for
memory ranges that extend to the end of an arena?  If so, how about a
memset() to 0xfe or something?

If I'm right and these are bugs, someone more comfortable with actually
altering the code might want to write the patches.  But first I want
Bart to rip holes in my logic and work out my mistakes.  :^)

HTH
-- 
--> Phil Pennock ; GAT d- s+:+ a22 C++(++++) UL++++/I+++/S+++/H+ P++@ L+++
E-@ W(+) N>++ o !K w--- O>+ M V !PS PE Y+ PGP+ t-- 5++ X+ R !tv b++>+++ DI+ D+
G+ e+ h* r y?

Re: heap memory issues

[Bart Schaefer]

On Nov 21,  9:37pm, Phil Pennock wrote:
} Subject: heap memory issues
}
} If I'm right and these are bugs, someone more comfortable with actually
} altering the code might want to write the patches.  But first I want
} Bart to rip holes in my logic and work out my mistakes.  :^)

Chuckle.  I'm not really all that well-versed in the memory code, and I
was pretty busy with other stuff the last several days, but here are some
random rips.

} The debugging array h_m is declared to be:
}   static int h_m[1025];
} It seems to be used for tracing the number of allocations of a given
} size; however, with an H_ISIZE == sizeof(long), [assuming 4] then
} scanning mem.c, it's 3/4 unused.  The first 1024/H_ISIZE entries and
} 1024 can be filled, the rest will never change from 0.

That's right.  It appears from the code in bin_mem() that halloc() should
be using
    h_m[size < (1024 * H_ISIZE) ? (size / H_ISIZE) : 1024]++;

} Also, for 64-bit platforms, might alignment constraints require H_ISIZE
} to be sizeof(long long), or can all of them use 32-bit alignment?

It would probably be useful to have a configure test for the actual size
required for correct alignment on any given platform.  I may be able to
dig one up (somebody remind me later, please).

} Whilst I haven't tested this, it looks upon reading as though there are
} some problems if hrealloc()ing a memory-block that is larger than
} HEAP_ARENA_SIZE.  [...] If a previous hrealloc() has gone from greater than
} HEAP_ARENA_SIZE to less than HEAP_ARENA_SIZE then a new arena will have
} been allocated (lines 338-345), so h->used can't be less than
} HEAP_ARENA_SIZE for a big hunk, *BUT* there is the problem that the new
} arena thus allocated will be smaller than HEAP_ARENA_SIZE and the
} zfree(h, HEAPSIZE) in line 269 now frees too much memory.

I don't see any immediate flaws in this reasoning, except for one:  The
second parameter to zfree() is almost completely meaningless. :-)  This
parameter is only used when ZSH_MEM is defined, and then it's only used
to try to consolidate small blocks so a larger block can be recovered.
It's only a problem for the second parameter of zfree() to be wrong when
it's also less than (M_ISIZE * M_NSMALL).  See line 854, which gates the
zfree() code extending down to line 936.

} Hrm, lines 314-316 are:
}     DPUTS(!h, "BUG: hrealloc() called for non-heap memory.");
}     DPUTS(h->sp && arena(h) + h->sp->used > p,
}           "BUG: hrealloc() wants to realloc pushed memory");
} If the first DPUTS prints (ie, non-heap memory) then won't this
} dereference a null-pointer?

Yes, but so will other code later, so the whole point is to flush out that
error message.

} Lines 318-325 handle reallocating from the middle of an arena  --
} should this do a memset() to 0xff if ZSH_MEM_DEBUG, or is that only for
} memory ranges that extend to the end of an arena?

That one I can't (really:  don't want to stare at this long enough to :-)
answer.

-- 
Bart Schaefer                                 Brass Lantern Enterprises
http://www.well.com/user/barts              http://www.brasslantern.com

Re: heap memory issues

[Sven Wischnowsky]

Phil Pennock wrote:

> The debugging array h_m is declared to be:
>   static int h_m[1025];
> It seems to be used for tracing the number of allocations of a given
> size; however, with an H_ISIZE == sizeof(long), [assuming 4] then
> scanning mem.c, it's 3/4 unused.  The first 1024/H_ISIZE entries and
> 1024 can be filled, the rest will never change from 0.

The patch below adds the fix Bart suggested in his reply to Phil's
mail.

> 
> Also, for 64-bit platforms, might alignment constraints require H_ISIZE
> to be sizeof(long long), or can all of them use 32-bit alignment?  The
> halloc() and hrealloc() functions seem to rely upon H_ISIZE being a
> measure of sufficient alignment for all data-types.

As I've in a reply to another mail all 64-Bit machines I know about
use the LP64 convention, i.e. longs and pointers are 64 Bit wide. If
ever some demented processor manufacturer builds a 64-Bit processor
and manages to make people use a different convention in C(++) code we 
are in trouble. In this case using a configure-test for the word size
as suggested by Bart would be needed (and it might be a good thing
even now).
Btw. is the type `long long' in the ANSI-standard? I always thought it 
was some special thing offered only by gcc.

> 
> Take a deap breath for the logic here ...
> 
> Whilst I haven't tested this, it looks upon reading as though there are
> some problems if hrealloc()ing a memory-block that is larger than
> HEAP_ARENA_SIZE.  This would only manifest itself on an allocation
> larger than about 8176 bytes (varying according to compiler whim).
> These are probably sufficiently rare to not crop up too often.
> In halloc() line 269, we have:
>   n = HEAP_ARENA_SIZE > size ? HEAPSIZE : size + sizeof(*h);
> Then in hrealloc() line 335:
>   zfree(h, HEAPSIZE);
> from a hrealloc(startofhunk, oldverybig, 0) -- the /next/ block checks
> for big sizes, just too late.  Changing this to check for
> (h->used > HEAP_ARENA_SIZE) first would, as it stands, work FOR THIS
> case.  If a previous hrealloc() has gone from greater than
> HEAP_ARENA_SIZE to less than HEAP_ARENA_SIZE then a new arena will have
> been allocated (lines 338-345), so h->used can't be less than
> HEAP_ARENA_SIZE for a big hunk, *BUT* there is the problem that the new
> arena thus allocated will be smaller than HEAP_ARENA_SIZE and the
> zfree(h, HEAPSIZE) in line 269 now frees too much memory.
> 
> Um... just re-read the code if that's confusing.

Bart already described the meaning of the second argument to
zfree(). To answer the other thing: I don't see a place where a heap
can be allocated that has an arena of less than HEAD_ARENA_SIZE
bytes in which case we simply don't have the problem you
described. Could you enlighten me where this small head arena can be
allocated?

> ...
> 
> Lines 318-325 handle reallocating from the middle of an arena  --
> should this do a memset() to 0xff if ZSH_MEM_DEBUG, or is that only for
> memory ranges that extend to the end of an arena?  If so, how about a
> memset() to 0xfe or something?

Yes, this might be useful, it seems someone has overlooked the
halloc() here.

The last hunk in the patch makes gcc be quiet about yet another
`ambiguous else'.


Bye
 Sven

*** os/mem.c	Thu Dec  3 09:10:44 1998
--- Src/mem.c	Fri Dec  4 10:39:09 1998
***************
*** 244,250 ****
      size = (size + H_ISIZE - 1) & ~(H_ISIZE - 1);
  
  #if defined(ZSH_MEM) && defined(ZSH_MEM_DEBUG)
!     h_m[size < 1024 ? (size / H_ISIZE) : 1024]++;
  #endif
  
      /* find a heap with enough free space */
--- 244,250 ----
      size = (size + H_ISIZE - 1) & ~(H_ISIZE - 1);
  
  #if defined(ZSH_MEM) && defined(ZSH_MEM_DEBUG)
!     h_m[size < (1024 * H_ISIZE) ? (size / H_ISIZE) : 1024]++;
  #endif
  
      /* find a heap with enough free space */
***************
*** 319,324 ****
--- 319,327 ----
  	if (new > old) {
  	    char *ptr = (char *) halloc(new);
  	    memcpy(ptr, p, old);
+ #ifdef ZSH_MEM_DEBUG
+ 	    memset(p, 0xff, old);
+ #endif
  	    return ptr;
  	} else
  	    return new ? p : NULL;
***************
*** 1004,1011 ****
  	long n = (m_lfree->len - M_MIN) & ~(m_pgsz - 1);
  
  	m_lfree->len -= n;
! 	if (brk(m_high -= n) == -1)
  	    DPUTS(1, "MEM: allocation error at brk.");
  
  #ifdef ZSH_MEM_DEBUG
  	m_b += n;
--- 1007,1015 ----
  	long n = (m_lfree->len - M_MIN) & ~(m_pgsz - 1);
  
  	m_lfree->len -= n;
! 	if (brk(m_high -= n) == -1) {
  	    DPUTS(1, "MEM: allocation error at brk.");
+ 	}
  
  #ifdef ZSH_MEM_DEBUG
  	m_b += n;

--
Sven Wischnowsky                         wischnow@informatik.hu-berlin.de

Re: heap memory issues

[Phil Pennock]

Typing away merrily, Sven Wischnowsky produced the immortal words:
> Btw. is the type `long long' in the ANSI-standard? I always thought it 
> was some special thing offered only by gcc.

I've not read the C9X draft.  It's big; thinking about it, now is the
time to do so.  I emailed zefram in January with the URLs:
 <http://www.dkuug.dk/JTC1/SC22/WG14/>
 <http://osiris.dkuug.dk/JTC1/SC22/open/n2620/n2620.txt>
Also in postscript and PDF (according to what I wrote when I mailed
him, anyway.  Too long ago for me to actually remember).

Reading through subsequent email with zef, C9X apparently adopts
'long long' rather than specifiable integer sizes.

> Bart already described the meaning of the second argument to
> zfree(). To answer the other thing: I don't see a place where a heap
> can be allocated that has an arena of less than HEAD_ARENA_SIZE
> bytes in which case we simply don't have the problem you
> described. Could you enlighten me where this small head arena can be
> allocated?

If an big hunk was allocated, such that an overly large arena was
created for it, then reallocating to a size less than the maximum looked
to me as if it would allocate a small arena.

I think.  I want to leave it a few years before looking at that code
again.  ;^)
-- 
--> Phil Pennock ; GAT d- s+:+ a22 C++(++++) UL++++/I+++/S+++/H+ P++@ L+++
E-@ W(+) N>++ o !K w--- O>+ M V !PS PE Y+ PGP+ t-- 5++ X+ R !tv b++>+++ DI+ D+
G+ e+ h* r y?