php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Bug #39534 Error in maths to calculate of ZEND_MM_ALIGNED_MIN_HEADER_SIZE
Submitted: 2006-11-16 15:15 UTC Modified: 2006-11-23 09:34 UTC
From: wharmby at uk dot ibm dot com Assigned: dmitry
Status: Closed Package: Scripting Engine problem
PHP Version: 5CVS-2006-11-16 (snap) OS: Windows XP
Private report: No CVE-ID:
 [2006-11-16 15:15 UTC] wharmby at uk dot ibm dot com
Description:
------------
Error in maths spotted whilst reviewing the Memory Manager
code in zend_alloc.c in order to get a general understanding
of the allocation algorithm. I believe the maths involved in
calculating the size of ZEND_MM_ALIGNED_MIN_HEADER_SIZE is
incorrect as it stands although the problem reported only 
shows up in the DEBUG build currently. 

Enabling the debug printf at the start of zend_mm_startup_ex() helps to demonstrate the problem: 

Output with Retail build
------------------------

  0 :  16 1  1
  1 :  16 1  1
  2 :  16 1  1
  3 :  16 1  1
  4 :  16 1  1
  5 :  16 1  1
  6 :  16 1  1
  7 :  16 1  1
  8*:  16 1  1
  9 :  24 1  2
 10 :  24 1  2
 11 :  24 1  2
  ..... etc

This shows that in the retail build we can see that a
request for zero bytes requires a "true size" of 16 bytes
and such blocks are added to/found in free_bucket[1]. 
Requests for 1-8 bytes also map to free_bucket[1], requests 
for 9-16 map to free_bucket[2] etc all as expected.

However, in the DEBUG build we do not get the correct mapping between request size and free_bucket[]'s.

Output from Debug build
-----------------------

  0 :  48 1  2
  1 :  48 1  2
  2 :  48 1  2
  3 :  48 1  2
  4 :  48 1  2
  5 :  56 1  3
  6 :  56 1  3
  7 :  56 1  3
  8 :  56 1  3
  9 :  56 1  3
 10 :  56 1  3
 11 :  56 1  3
 12 :  56 1  3

 .....etc

This shows that for a request size of zero bytes we require
a "true size" of 48 bytes and such blocks are found in free_bucket[2], i.e free_bucket[1] is not used at all.
 
Only a minor issue in the DEBUG version of the code I know
but wrong all the same and in worse case it could mean that 
a problem that recreates with retail build is more difficult
to recreate with debug build. The retail and debug algorithms should wherever possible cause the same results. 
The reason for this mis-mapping of blocks to free buckets is
because ZEND_MM_ALIGNED_MIN_HEADER_SIZE currently equates
to 40 rather than the correct value of 48 bytes.

From my reading of the code ZEND_MM_ALIGNED_MIN_HEADER_SIZE
rather than the minimum size of a block header is more 
correctly the size of the smallest block which the Memory 
Manager will allocate and/or add to its free lists and is 
the greater of:
	(1) the size of a free block header itself, and 
	(2) the size of block required in order to satisfy 
            an allocate of the smallest permissible size 
            which as the code stands is for zero bytes.

In the retail build it will indeed be equal to the size of 
the larger of the zend_mm_block and zend_mm_free_block 
headers rounded to the next 8 byte multiple. However in the 
DEBUG build the magic slot which immediately follows the 
data portion of a block, i.e not part of header, needs to be
correctly taken account of. The data portion of a block 
(even if its of zero length) must start on an 8 byte aligned
boundary with the magic slot immediately after it.

The code to calculate ZEND_MM_ALIGNED_MIN_HEADER_SIZE in
zend_alloc.c is currently as follows:

#define ZEND_MM_ALIGNED_MIN_HEADER_SIZE	
    (sizeof(zend_mm_block)+END_MAGIC_SIZE>sizeof(zend_mm_free_block) ? ZEND_ALIGNED_SIZE(sizeof(zend_mm_block)+END_MAGIC_SIZE):
  ZEND_MM_ALIGNED_SIZE(sizeof(zend_mm_free_block)))

So in the DEBUG build ZEND_MM_ALIGNED_MIN_HEADER_SIZE equates to 40 rather than  the correct value of 48. The mistake is to add "sizeof(zend_mm_block)" and "END_MAGIC_SIZE" together before aligning. The code should read something more like:

#define ZEND_MM_MIN_ALLOC_BLOCK_SIZE
  ZEND_MM_ALIGNED_SIZE(ZEND_MM_ALIGNED_HEADER_SIZE + 
  END_MAGIC_SIZE)
#define ZEND_MM_ALIGNED_MIN_HEADER_SIZE
   (ZEND_MM_MIN_ALLOC_BLOCK_SIZE >   
    ZEND_MM_ALIGNED_FREE_HEADER_SIZE ?
    ZEND_MM_MIN_ALLOC_BLOCK_SIZE : 
    ZEND_MM_ALIGNED_FREE_HEADER_SIZE)

Which results in correct value for ZEND_MM_ALIGNED_MIN_HEADER_SIZE of 48. 

The incorrect value for ZEND_MM_ALIGNED_MIN_HEADER_SIZE has 
2 additional side affects:

(1) As ZEND_MM_ALIGNED_MIN_HEADER_SIZE is incorrectly
calculated in the DEBUG build as 40 bytes any "remainder"
of 40 bytes when allocating a block will get added to
cache/free_bucket[1] but will never be used as its too
small a block to satisfy any allocation request given that
the minimum value for "true size" in the DEBUG build is 48
bytes.

(2) ZEND_MM_MIN_SIZE currently equates to -4 in the DEBUG
build which is a little strange although does not appear to
cause any problems given its current usage. This value
should be the maximum size of allocate request which
can be satisfied by a block of ZEND_MM_ALIGNED_MIN_HEADER_SIZE whilst still satisfying all
the alignment requirements for an allocated block. So
should be equal to 4 for DEBUG build.
 
In addition renaming ZEND_MM_ALIGNED_MIN_HEADER_SIZE
to something more meaningful such as ZEND_MM_ALIGNED_MIN_FREE_SIZE would improve code readability
given that its main use in the code is in deciding if the
"remainder" of a free block is big enough to add to the free
lists.

The patch also corrects the calculation of the value of
ZEND_MM_MAX_SMALL_SIZE, i.e the largest size considered
"small" which is currently equal to 8 more than the size of the largest block the code considers small.  

I supply a patch based on the latest available 5.2 snapshot
build for Windows Nov 16, 2006 09:30 GMT) to implement all my suggested changes at: 
 
             http://pastebin.ca/250027

Even though the problems identified in this defect do not
currently result in noticeable run-time issues in the retail
builds fixing the code along the lines suggested will not
only mean the algorithms are correct going forward, it also
makes the code easier to understand for someone coming to it
for the first time.

Reproduce code:
---------------
N/A - Needs instrumentation in engine code (zend_alloc.c)
to demonstrate the bad  behaviour. Enabling the printf at
the start of zend_mm_startup_ex is sufficient to highlight
the main issue raised.


Expected result:
----------------
Debug build with supplied fix
  0 :  48 1  1
  1 :  48 1  1
  2 :  48 1  1
  3 :  48 1  1
  4*:  48 1  1
  5 :  56 1  2
  6 :  56 1  2
  7 :  56 1  2
  8 :  56 1  2
  9 :  56 1  2
 10 :  56 1  2
 11 :  56 1  2
 12 :  56 1  2
 13 :  64 1  3
...etc

Actual result:
--------------
Debug build without fix:  
  0 :  48 1  2
  1 :  48 1  2
  2 :  48 1  2
  3 :  48 1  2
  4 :  48 1  2
  5 :  56 1  3
  6 :  56 1  3
  7 :  56 1  3
  8 :  56 1  3
  9 :  56 1  3
 10 :  56 1  3
 11 :  56 1  3
 12 :  56 1  3
...etc

Patches

Add a Patch

Pull Requests

Add a Pull Request

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2006-11-23 09:34 UTC] dmitry@php.net
The patch committed into CVS HEAD and PHP_5_2. 

Thank you for catching the bug.
 
PHP Copyright © 2001-2014 The PHP Group
All rights reserved.
Last updated: Sat Apr 19 22:02:16 2014 UTC