ID: 39534
Updated by: [EMAIL PROTECTED]
Reported By: wharmby at uk dot ibm dot com
-Status: Assigned
+Status: Closed
Bug Type: Scripting Engine problem
Operating System: Windows XP
PHP Version: 5CVS-2006-11-16 (snap)
Assigned To: dmitry
New Comment:
The patch committed into CVS HEAD and PHP_5_2.
Thank you for catching the bug.
Previous Comments:
------------------------------------------------------------------------
[2006-11-16 15:15:34] 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
------------------------------------------------------------------------
--
Edit this bug report at http://bugs.php.net/?id=39534&edit=1
