php7变量实现_array

作者: jun123123 | 来源:发表于2020-09-10 00:27 被阅读0次

PHP数组实现

key，键
value，值
bucket，桶，一个数组元素，用来保存key和value
slot，槽，一个slot可以存放多个bucket，数组可以通过key和一个哈希函数指向一个slot
哈希函数，将key指向slot
哈希冲突，不同的key经过计算后指向同一个slot。php通过链地址法来解决哈希冲突。哈希函数分为hash1和hash2，hash1将key(string)映射为h值(long)，hash2将h值映射到slot地址。对于一个数组key，就不需要使用hash1计算哈希值，而是直接将key储存在h值中。

php5的数组实现

typedef struct bucket {
    ulong h;
    uint nKeyLength;                //key的长度，当nKeyLength=0时表示key为数字。比较key值是否相等时，首先比较h值，再比较nKeyLength，最后比较key值。
    void * pData;                   //data的指针
    void * pDataPtr;                //一般pDataPtr=NULL，如果当该value值是一个指针时，将这个指针直接储存在pDataPtr中，再将pData指向pDataPtr，用于减少内存碎片
    struct bucket * pListNext;      //全局链表的前驱指针
    struct bucket * pListLast;      //全局链表的后驱指针
    struct bucket * pNext;          //局部链表的前驱指针
    struct bucket * pLast;          //局部链表的后驱指针
    const char * arkey;             //key值，有的版本为char arKey[1]柔性数组
} Bucket;

typedef struct _HashTable {
    uint nTableSize;                //arBuckets指向的slot个数，该值始终为2的n次方，且不小于8不大于2的31次方（64位系统）
    uint nTableMask;                //掩码，等于nTableSize-1，也就是2的n次方减一，hash2函数通过这个值来获取slot索引，slot=h & nTableMask。再通过arBuckets[slot]找到相应的slot首元素
    uint nNumOfElements;            //bucket元素的个数
    ulong nNextFreeElements;        //下一个可用数值索引，如$a[]=1的赋值会用到这个值
    Bucket * pInternalPointer;      //全局默认游标，用于实现数组的foreach等遍历操作，保存了正在遍历的bucket
    Bucket * pListHead;             //指向数组的首元素
    Bucket * pListTail;             //指向数组的尾元素
    Bucket ** arBuckets;            //一段连续的数组内存，每个指针指向一个slot链表的首元素
    dtor_func_t pDestructor;        //析构函数
    zend_bool prtsistent;           
    unsigned char nApplyCount;      //循环遍历保护
    zend_bool aApplyProtection;
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

bucket中的四个bucket指针，包括pListNext、pListLast、pNext、pLast，其中前两个用来保证数组的有序性。后两个用来解决哈希冲突。对于映射到相同slot的key，通过链表将他们连接起来，这个链表成为局部链表，新元素插入采用头插法。

php5中的数组存在一些问题，如bucket中的四个指针占用了32字节内存，空间效率不高，并且由于bucket内存分配的随机性，cpu的缓存命中率也不高。

php7的数组实现

typedef struct _Bucket {
    zval              val;                          //保存一个zval，val.value指向实际的数据，如value为字符串，那么val.value.str指向实际的zend_string
    zend_ulong        h;                            //保存key的哈希值，或者直接保存数字key
    zend_string      *key;                          //保存key，或者NULL（key为long型时）
} Bucket;

struct _zend_array {
    zend_refcounted_h gc;                           //php7中统一的gc计数
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    flags,                //各个bit表达不同的标志
                zend_uchar    nAppklyCount,         //遍历递归计数，该值超过一个最大值时抛出一个警告或异常    
                zend_uchar    nIteratorsCount,      //迭代计数，记录了当前正在遍历该hashtable的迭代器数量
                zend_uchar    consistency)          //用于调试
        } v;
        uint32_t flags;
    } u;
    uint32_t          nTableMask;                   //掩码
    Bucket           *arData;                       //Bucket数组
    uint32_t          nNumUsed;                     //已使用bucket数量，包括有效bucket和无效bucket
    uint32_t          nNumOfElements;               //有效bucket数量
    uint32_t          nTableSize;                   //所有bucket数量，该值始终为2的n次方，且不小于8不大于2的31次方（64位系统）
    uint32_t          nInternalPointer;             //全局默认游标，用于实现数组的foreach等遍历操作，保存了正在遍历的bucket在arData数组中的索引
    zend_long         nNextFreeElement;             //下一个可用的数值索引，如$a[]=1的赋值会用到这个值
    dtor_func_t       pDestructor;                  //析构函数
};                                              //php7中，HashTable和zend_array都是_zend_array的别名

bucket分类

未使用bucket，最初所有bucket都是未使用状态
有效bucket：储存有效数据的bucket，插入一个数据时，会选择一个未使用bucket，这样这个未使用bucket就成为了一个有效bucket

，更新操做只能发生在有效bucket上
无效bucket：有效bucket上的数据被删除时，有效bucket成为无效bucket，如unset操作。对有效bucket进行unset操作时并没有删除该bucket而是修改bucket.val.u1.v.type=IS_UNDF，标记为未定义，但对数据并不会进行修改，在对数组进行rehash时才会删除无效bucket。

一般在内存上有效bucket和无效bucket会交替分布，但都在未使用bucket的前面。当bucket数组中无效bucket很多有效bucket很少时，php会对整个数组进行rehash操作，释放无效bucket并使有效bucket连续紧密。

部分zend_array属性

u.v.flags

#define HASH_FLAG_PERSISTENT    (1<<0)      //是否使用持久化内存（不使用内存池）
#define HASH_APPLY_PROTECTION   (1<<1)      //是否开启递归遍历保护
#define HASH_FLAG_PACKED        (1<<2)      //是否是packed array
#define HASH_FLAG_INITIALIZED   (1<<3)      //是否已经初始化
#define HASH_FLAG_STATIC_KEYS   (1<<4)      //标记HashTable的key是否为静态值，即long和内部字符串
#define HASH_FLAG_HAS_EMPTY_IND (1<<5)      //是否存在空的间接zval

nTableMask

掩码，php7的掩码始终为负数，一般为-nTableSize，通过掩码和h值来确定slot索引。php7的slot保存在arData前的一块内存中，可以通过负向索引来访问。php7分配数组内存时会在bucket也申请一块内存，用做索引数组，这个数组内的每个元素都是一个slot，其中存放了这个slot链表的首bucket在arData数组中的索引。如果这个slot中还没有bucket，那么该索引值为-1。由于索引数组个arData数组是连续的内存，可以直接使用负数下标来访问索引数组。比如arData[1]是一个bucket，((uint32_t *)arData(-1))就是索引数组中的元素，保存的是这个slot链表首bucket在arData数组中的索引。

例如nTableSize=8，那么nTableMask=-8，即nTableMask=11111111111111111111111111111000，php7中的hash2函数：slot = h | nTableMask，通过这个slot就能在arData中找到slot。

php7和php5一样都是使用链地址法来解决哈希冲突，但是php7中的bucket结构体并没有保存局部链表的信息，那么怎么遍历局部链表。这里的局部链表信息实际上是保存在zval中的

struct _zval_struct {
     union {
          zend_long         lval;            
          double            dval;            
          zend_refcounted  *counted;
          zend_string      *str;
          zend_array       *arr;
          zend_object      *obj;
          zend_resource    *res;
          zend_reference   *ref;            
          zend_ast_ref     *ast;            
          zval             *zv;
          void             *ptr;
          zend_class_entry *ce;
          zend_function    *func;
          struct {
               uint32_t w1;
               uint32_t w2;
          } ww;
     } value;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    type,         
                zend_uchar    type_flags,   
                zend_uchar    const_flags,  
                zend_uchar    reserved     
        } v;
        uint32_t type_info;
    } u1;
    union {
        uint32_t     var_flags;
        uint32_t     next;                 
        uint32_t     cache_slot;           
        uint32_t     lineno;               
        uint32_t     num_args;             
        uint32_t     fe_pos;               
        uint32_t     fe_iter_idx;          
    } u2;
};

在zval.u2中有一个next字段，这个字段就是用来保存局部链表中下一个元素在arData数组中的索引。

数组初始化

对于一个空数组或数组的元素都是常量表达式，那么数据的初始化发生在编译阶段。否则发送在执行阶段。数据的初始化分为两步

分配HashTable结构体内存并初始化字段
分配bucket数组内存，修改部分HashTable部分字段值

对于bucket数组内存分配并不是每次都会进行，比如一个空数组的初始化就不会分配bucket数组内存，只有当需要使用bucket数组时才会分配内存。

php7中可以使用zval.value.arr来指向一个数组，也可以直接使用HashTable，他们对应的宏分别是ZVAL_NEW_ARR和ALLOC_HASHTABLE。

#define ZVAL_NEW_ARR(z) do {        \
    zval * __z = (z);   \
    zend_array * _arr = \
    (zend_array *) emalloc(sizeof(zend_array));\
    Z_ARR_P(__z) = _arr; \
    Z_TYPE_INFO_P(__z) = IS_ARRAY_EX; \
} while(0)

#define ALLOC_HASHTABLE(ht) \
    (ht) = (HashTable *) emalloc(sizeof(HashTable))

为HashTable分配内存

为Hashtable分配内存后会对其各个字段进行初始化

static zend_always_inline void _zend_hash_init_int(HashTable *ht, uint32_t nSize, dtor_func_t pDestructor, zend_bool persistent)
{
    GC_SET_REFCOUNT(ht, 1);
    GC_TYPE_INFO(ht) = IS_ARRAY | (persistent ? (GC_PERSISTENT << GC_FLAGS_SHIFT) : (GC_COLLECTABLE << GC_FLAGS_SHIFT));
    HT_FLAGS(ht) = HASH_FLAG_UNINITIALIZED;
    ht->nTableMask = HT_MIN_MASK;               //HT_MIN_MASK=-2
    HT_SET_DATA_ADDR(ht, &uninitialized_bucket);    //将arData指向uninitialized_bucket的尾部
    ht->nNumUsed = 0;
    ht->nNumOfElements = 0;
    ht->nInternalPointer = 0;
    ht->nNextFreeElement = 0;
    ht->pDestructor = pDestructor;
    ht->nTableSize = zend_hash_check_size(nSize);
}

ZEND_API void ZEND_FASTCALL _zend_hash_init(HashTable *ht, uint32_t nSize, dtor_func_t pDestructor, zend_bool persistent)
{
    _zend_hash_init_int(ht, nSize, pDestructor, persistent);
}

static const uint32_t unintialized_bucket[-HT_MIN_MASK] = {HT_INVALID,HT_INVALID};//HT_INVALID=-1，这个数组大小为2，并且元素都为-1，arData指向这个数组的尾部也就是将这个数组作为arData的索引数组，因此nTableMask=-2。

为arData数组分配内存

hash array和packed array

php中的一种常用数组是以递增整型值为索引的数组，这种数组类似c语言的数组，不需要进行索引，这种数组称为packed array。packed array的nTableMask=-2，因为在上面初始化HashTable字段时给nTableMask赋的值。

ZEND_API void ZEND_FASTCALL zend_hash_real_init(HashTable *ht, zend_bool packed)
{
    IS_CONSISTENT(ht);

    HT_ASSERT_RC1(ht);
    zend_hash_real_init_ex(ht, packed);
}

static zend_always_inline void zend_hash_real_init_ex(HashTable *ht, int packed)
{
    HT_ASSERT_RC1(ht);
    ZEND_ASSERT(HT_FLAGS(ht) & HASH_FLAG_UNINITIALIZED);
    if (packed) {
        zend_hash_real_init_packed_ex(ht);
    } else {
        zend_hash_real_init_mixed_ex(ht);
    }
}

static zend_always_inline void zend_hash_real_init_packed_ex(HashTable *ht)
{
    void *data;

    if (UNEXPECTED(GC_FLAGS(ht) & IS_ARRAY_PERSISTENT)) {
        data = pemalloc(HT_SIZE_EX(ht->nTableSize, HT_MIN_MASK), 1);
    } else if (EXPECTED(ht->nTableSize == HT_MIN_SIZE)) {
        data = emalloc(HT_SIZE_EX(HT_MIN_SIZE, HT_MIN_MASK));
    } else {
        data = emalloc(HT_SIZE_EX(ht->nTableSize, HT_MIN_MASK));
    }
    HT_SET_DATA_ADDR(ht, data);
    /* Don't overwrite iterator count. */
    ht->u.v.flags = HASH_FLAG_PACKED | HASH_FLAG_STATIC_KEYS;
    HT_HASH_RESET_PACKED(ht);
}

static zend_always_inline void zend_hash_real_init_mixed_ex(HashTable *ht)
{
    void *data;
    uint32_t nSize = ht->nTableSize;

    if (UNEXPECTED(GC_FLAGS(ht) & IS_ARRAY_PERSISTENT)) {
        data = pemalloc(HT_SIZE_EX(nSize, HT_SIZE_TO_MASK(nSize)), 1);
    } else if (EXPECTED(nSize == HT_MIN_SIZE)) {
        data = emalloc(HT_SIZE_EX(HT_MIN_SIZE, HT_SIZE_TO_MASK(HT_MIN_SIZE)));
        ht->nTableMask = HT_SIZE_TO_MASK(HT_MIN_SIZE);
        HT_SET_DATA_ADDR(ht, data);
        /* Don't overwrite iterator count. */
        ht->u.v.flags = HASH_FLAG_STATIC_KEYS;
#ifdef __SSE2__
        do {
            __m128i xmm0 = _mm_setzero_si128();
            xmm0 = _mm_cmpeq_epi8(xmm0, xmm0);
            _mm_storeu_si128((__m128i*)&HT_HASH_EX(data,  0), xmm0);
            _mm_storeu_si128((__m128i*)&HT_HASH_EX(data,  4), xmm0);
            _mm_storeu_si128((__m128i*)&HT_HASH_EX(data,  8), xmm0);
            _mm_storeu_si128((__m128i*)&HT_HASH_EX(data, 12), xmm0);
        } while (0);
#elif defined(__aarch64__)
        do {
            int32x4_t t = vdupq_n_s32(-1);
            vst1q_s32((int32_t*)&HT_HASH_EX(data,  0), t);
            vst1q_s32((int32_t*)&HT_HASH_EX(data,  4), t);
            vst1q_s32((int32_t*)&HT_HASH_EX(data,  8), t);
            vst1q_s32((int32_t*)&HT_HASH_EX(data, 12), t);
        } while (0);
#else
        HT_HASH_EX(data,  0) = -1;
        HT_HASH_EX(data,  1) = -1;
        HT_HASH_EX(data,  2) = -1;
        HT_HASH_EX(data,  3) = -1;
        HT_HASH_EX(data,  4) = -1;
        HT_HASH_EX(data,  5) = -1;
        HT_HASH_EX(data,  6) = -1;
        HT_HASH_EX(data,  7) = -1;
        HT_HASH_EX(data,  8) = -1;
        HT_HASH_EX(data,  9) = -1;
        HT_HASH_EX(data, 10) = -1;
        HT_HASH_EX(data, 11) = -1;
        HT_HASH_EX(data, 12) = -1;
        HT_HASH_EX(data, 13) = -1;
        HT_HASH_EX(data, 14) = -1;
        HT_HASH_EX(data, 15) = -1;
#endif
        return;
    } else {
        data = emalloc(HT_SIZE_EX(nSize, HT_SIZE_TO_MASK(nSize)));
    }
    ht->nTableMask = HT_SIZE_TO_MASK(nSize);
    HT_SET_DATA_ADDR(ht, data);
    HT_FLAGS(ht) = HASH_FLAG_STATIC_KEYS;
    HT_HASH_RESET(ht);
}

HT_SIZE宏用来计算索引数组和bucket数组的总内存大小，HT_SET_DATA_ADDR宏用来设置arData指针指向这段内存中bucket数组开始的地址。也就是将这段地址的基地址+(-nTableMask)*sizeof(uint32_t)赋给arData。

申请arData数组内存

如果ht->u.flags的HASH_FLAG_PERSISTENT位有效。就通过malloc函数直接申请内存，否则通过pemalloc函数在内存池中分配内存。申请内存大小为(-nTableMask)*sizeof(uint32_t)+nTableSize*sizeof(Bucket)。
设置ht->arData指针
修改ht->u.flags

如果是packed array，那么ht->u.flags | = HASH_FLAG_INITIALIZED | HASH_FLAG_PACKED

如果是hash array，那么ht->u.flags | = HASH_FLAG_INITIALIZED
初始化索引数组

如果是packed array，使用用HT_HASH_RESET_PACKED设置索引数组，设置索引值均为-1

如果是hash array，且nTableSize为最小值8，那么直接初始化索引数组全为-1，否则使用HT_HASH_RESER宏初始化索引数组，注意在最初的php7版本中，hash array的nTableMask=-nTableSize，即|nTableSize/nTableMask|=1，在较新的版本中，hash array的nTableMask=-2nTableSize，即|nTableSize/nTableMask|=0.5。这个值称为负载因子。所以在上面的代码中当nTableSize=8时初始化了16个索引数组位，在《PHP7底层设计与源码实现》一书给出的代码中写的是8位。
负载因子（Load Factor）

负载因子会影响 hash 碰撞的概率从而影响到耗时，也会影响 Hash 区的大小来影响内存消耗。

在 PHP 中，用 nTableMask 和 nTableSize 的关系来体现：
```
负载因子 = |nTableMask / nTableSize|
```
- 负载因子为 1 的时候（PHP 5），nTableMask == - (nTableSize) 。
- 负载因子为 0.5 的时候（PHP 7）， nTableMask == - (nTableSize + nTableSize) 。
上一次修改负载因子的提交是：
https://github.com/php/php-src/commit/34ed8e53fea63903f85326ea1d5bd91ece86b7ae

为什么负载因子会影响时间消耗和内存消耗？

负载因子越大， nTableMask 绝对值就越小（nTableMask 本身受到 nTableSize 的影响），从而导致 Hash 区变小。

Hash 区一旦变小，更容易产生碰撞。也就使得冲突链更长，执行的操作会在冲突链的时间消耗变得更长。

负载因子越小，Hash 区变大，使得内存消耗更多，但冲突链变短，操作耗时变小。

负载因子时间消耗内存消耗

大小大

小大小

所以要根据对内存和时间的要求来做调整。

PHP 的负载因子从 1 （PHP5）降到 0.5 （PHP7），使得速度变快了，但同时内存消耗变大。

负载因子	时间消耗	内存消耗
大	小	大
小	大	小

如果一个数组是packed array 那么它的索引一定是递增整型（不一定是整型，下面会说明）。但是如果一个数组的索引是递增整型，它却不一定是packed array。因为packed array是直接以数组的整型索引作为bucket数组的索引的，但是不能保证用户会建立一个什么样的数组，如果一个数组$a[0]=1;$a[10]=1;，如果采用packed array的机制那么从0到9的bucket数组位都会被浪费，造成很大的内存开销，对于这种情况php还是会使用hash array。如何进行这种选择。采用packed array是为了减少索引数组的内均开销和hash2函数的时间开销，一个uint32_t的slot一般是4字节，一个bucket是32字节，也就是一个bucket相当于8个slot的空间开销。如果一个数组因为采用packed机制而造成的额外的无用的bucket>nTableSize/2，那么从空间上看就更偏向于使用hash array。

key 可以是 integer 或者 string。value 可以是任意类型。

此外 key 会有如下的强制转换：

包含有合法整型值的字符串会被转换为整型。例如键名 "8" 实际会被储存为 8。但是 "08" 则不会强制转换，因为其不是一个合法的十进制数值。

浮点数也会被转换为整型，意味着其小数部分会被舍去。例如键名 8.7 实际会被储存为 8。

布尔值也会被转换成整型。即键名 true 实际会被储存为 1 而键名 false 会被储存为 0。

Null 会被转换为空字符串，即键名 null 实际会被储存为 ""。

数组和对象不能被用为键名。坚持这么做会导致警告：Illegal offset type。

如果在数组定义中多个单元都使用了同一个键名，则只使用了最后一个，之前的都被覆盖了。

对于hash array，早期版本的php7，nTableMask始终等于-nTableSize，对于新版本的php7，nTableMask=-2nTableSize。在数组插入时，新插入的bucket在arData数组中的索引index=ht->nNumUsed++;，对于nNextFreeElement，要注意这个指的是下一个可用的数值索引，如$a[3]=1;$a['a']=1;那么此时nNextFreeElement=4，nNextFreeElement并不是指bucket数组中下一个可用的bucket的索引，这个值是由nNumUsed保存的。整个索引过程3步，第一步获取h值，对于字符串key，通过hash1函数计算呢得到或者直接取出缓存的h值，对于数值key直接取出保存在h中的key。第二步通过h值，计算nIndex= nTableMask | h得到nIndex，这是一个负数，在arData数组中通过这个索引找到slot，这里要注意的是索引数组是uint32_t类型的而bucket数组是bucket类型的，取值时要对数组进行类型转换，是对数组进行类型转换而不是数组中的元素，在下面gdb调试的时候会说明。第三步通过nIndex找到slot后通过slot中的index在bucket数组中找到相应bucket，还要判断h值是否相同，如果h值相同再比较长度，如果长度相同再直接比较字符串，如果都相同说明已经成功索引，如果有一步不匹配则在当前bucket的zval中u2的next字段取出局部链表中下一个bucket在bucket数组中的索引，继续比较key。当插入操作时发现buckets数组容量不足时会判断当前无效bucket占比是否超过一个阈值，如果超过就进行rehash，否则进行扩容，rehash会释放无效bucket使之成为未使用bucket，并使有效bucket连续。array rehash时不会额外申请内存。如果进行扩容，扩容后bucket容量为原容量的2倍，扩容首先申请一块内存，将原内存内存拷贝过去再释放原内存，这个过程会导致较大的时间开销。例如我们构造$a[0]=1;$a[8]=1;$a[16]=1;$a[32]=1等，这样每次执行都需要进行扩容，会极大的影响性能，我们也可以通过一些方式，将数组所有的元素都索引到同一个slot上去，让数组退化为链表，每次索引都需要遍历链表。通过这些方式可以产生拒绝服务工具。

我在上一篇文章中介绍过, 经过特殊构造的键值, 使得PHP每一次插入都会造成Hash冲突, 从而使得PHP中array的底层Hash表退化成链表:

Hash collision
这样在每次插入的时候PHP都需要遍历一遍这个链表, 大家可以想象, 第一次插入, 需要遍历0个元素, 第二次是1个, 第三次是3个, 第65536个是65535个, 那么总共就需要65534*65535/2=2147385345次遍历....
那么, 这个键值是怎么构造的呢?
在PHP中,如果键值是数字, 那么Hash的时候就是数字本身, 一般的时候都是, index & tableMask. 而tableMask是用来保证数字索引不会超出数组可容纳的元素个数值, 也就是数组个数-1.
PHP的Hashtable的大小都是2的指数, 比如如果你存入10个元素的数组, 那么数组实际大小是16, 如果存入20个, 则实际大小为32, 而63个话, 实际大小为64. 当你的存入的元素个数大于了数组目前的最多元素个数的时候, PHP会对这个数组进行扩容, 并且从新Hash.
现在, 我们假设要存入64个元素(中间可能会经过扩容, 但是我们只需要知道, 最后的数组大小是64, 并且对应的tableMask为63:0111111), 那么如果第一次我们存入的元素的键值为0, 则hash后的值为0, 第二次我们存入64, hash(1000000 & 0111111)的值也为0, 第三次我们用128, 第四次用192... 就可以使得底层的PHP数组把所有的元素都Hash到0号bucket上, 从而使得Hash表退化成链表了.
当然, 如果键值是字符串的话, 就稍微比较麻烦一些了, 但是PHP的Hash算法是开源的, 已知的, 所以有心人也可以做到...

通过php的这种数组扩容方式也会造成一些问题

在实现zend_array替换HashTable中我们遇到了很多的问题，绝大部份它们都被解决了，但遗留了一个问题，因为现在arData是连续分配的，那么当数组增长大小到需要扩容到时候，我们只能重新realloc内存，但系统并不保证你realloc以后，地址不会发生变化，那么就有可能：
<?php
    $array = range(0, 7);
    set_error_handler(function($err, $msg) {    
        global $array;    $array[] = 1; //force resize;
    }); 
    function crash() {    
        global $array;    
        $array[0] += $var; //undefined notice
    } 
    crash();
比如上面的例子，首先是一个全局数组，然后在函数crash中，在+= opcode handler中，zend vm会首先获取array[0]的内容，然后+$var, 但var是undefined variable，所以此时会触发一个未定义变量的notice，而同时我们设置了error_handler, 在其中我们给这个数组增加了一个元素，因为PHP中的数组按照2^n的空间预先申请，此时数组满了，需要resize，于是发生了realloc，从error_handler返回以后，array[0]指向的内存就可能发生了变化，此时会出现内存读写错误，甚至segfault，有兴趣的同学，可以尝试用valgrind跑这个例子看看。

但这个问题的触发条件比较多，修复需要额外对数据结构，或者需要拆分add_assign对性能会有影响，另外绝大部分情况下因为数组的预先分配策略存在，以及其他大部分多opcode handler读写操作基本都很临近，这个问题其实很难被实际代码触发，所以这个问题一直悬停着。

对于packed array，因为其key都为整型数值，直接储存在h中，因此在其bucket中的key字段均赋为NULL。

在《PHP7底层设计与源码实现》P124-P130给出了一个示例代码及其执过程

$arr[] = 'foo';     //packed array，等价于$a[0]='foo';
arr['a'] = 'bar';   //packed_to_hash
$arr[2] = 'abc';
$arr[] = 'xyz';     //等价于$a[3]='xyz';
$arr['a'] = 'foo';
//后面还有两条输出语句省略了

[图片上传失败...(image-c61bae-1599668825984)]

上面是书上给出的上面代码执行完后的HashTable逻辑结构。

在上面的代码中，只有$a['a']是字符串key，其他的都是整型key。在这个图中只有字符串key通过索引数组进行索引，但是整型数值key并没有经过索引数组而是直接索引到了bucket数组，可以看到图中索引数组中只有-2的位置为1，其他都为-1。这样做有几个问题，第一个就是不能保证插入顺序与bucket数组中的保存顺序一致，如果先存$a[2]=1，再存$a[1]=2，那保存时会把 $a[1]放在数组中第一个位置，\$ a[2]放在数组中第二个位置，这样数组的有序性就被破坏了。第二个是对于hashtable来说并不关心数组的key类型，因为即使是字符串key，bucket数组的主键也是h值（不考虑hash冲突），一般情况所有的查询操作都是对h值进行操作，php数组可以不关心key的类型，但是如果按照图示的逻辑，那还需要判断key的类型并进行不同的处理，显然是多此一举。

whye@ubuntu:~/Desktop/php/php_compile/bin$ sudo vim array.php
whye@ubuntu:~/Desktop/php/php_compile/bin$ cat array.php
<?php
    $arr[] = 'foo';
    $arr['a'] = 'bar';
    $arr[2] = 'abc';
    $arr[] = 'xyz';
    $arr['a'] = 'foo';
    echo 'a';   
whye@ubuntu:~/Desktop/php/php_compile/bin$ gdb php
GNU gdb (Ubuntu 9.1-0ubuntu1) 9.1
Copyright (C) 2020 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from php...
(gdb) b ZEND_ECHO_SPEC_CONST_HANDLER
Breakpoint 1 at 0x4428e0: file /home/whye/Desktop/php/php-7.4.7/Zend/zend_vm_execute.h, line 3305.
(gdb) run array.php
Starting program: /home/whye/Desktop/php/php_compile/bin/php array.php

Breakpoint 1, ZEND_ECHO_SPEC_CONST_HANDLER () at /home/whye/Desktop/php/php-7.4.7/Zend/zend_vm_execute.h:3305
3305    {
(gdb) p executor_globals.symbol_table
$1 = {gc = {refcount = 1, u = {type_info = 23}}, u = {v = {flags = 16 '\020', _unused = 0 '\000', nIteratorsCount = 0 '\000', _unused2 = 0 '\000'}, flags = 16}, nTableMask = 4294967168, 
  arData = 0x7ffff7a56200, nNumUsed = 8, nNumOfElements = 8, nTableSize = 64, nInternalPointer = 0, nNextFreeElement = 0, pDestructor = 0x5555559512b0 <zval_ptr_dtor>}
(gdb) p executor_globals.symbol_table.arData[7].val.value.zv.value.arr
$2 = (zend_array *) 0x7ffff7a022a0
(gdb) p* executor_globals.symbol_table.arData[7].val.value.zv.value.arr
$3 = {gc = {refcount = 1, u = {type_info = 23}}, u = {v = {flags = 16 '\020', _unused = 0 '\000', nIteratorsCount = 0 '\000', _unused2 = 0 '\000'}, flags = 16}, nTableMask = 4294967280, 
  arData = 0x7ffff7a5b680, nNumUsed = 4, nNumOfElements = 4, nTableSize = 8, nInternalPointer = 0, nNextFreeElement = 4, pDestructor = 0x5555559512b0 <zval_ptr_dtor>}
(gdb) p executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[0]
$4 = {val = {value = {lval = 140737348285984, dval = 6.9533488874899137e-310, counted = 0x7ffff7a6b620, str = 0x7ffff7a6b620, arr = 0x7ffff7a6b620, obj = 0x7ffff7a6b620, res = 0x7ffff7a6b620, 
      ref = 0x7ffff7a6b620, ast = 0x7ffff7a6b620, zv = 0x7ffff7a6b620, ptr = 0x7ffff7a6b620, ce = 0x7ffff7a6b620, func = 0x7ffff7a6b620, ww = {w1 = 4154897952, w2 = 32767}}, u1 = {v = {type = 6 '\006', 
        type_flags = 0 '\000', u = {extra = 0}}, type_info = 6}, u2 = {next = 4294967295, cache_slot = 4294967295, opline_num = 4294967295, lineno = 4294967295, num_args = 4294967295, fe_pos = 4294967295, 
      fe_iter_idx = 4294967295, access_flags = 4294967295, property_guard = 4294967295, constant_flags = 4294967295, extra = 4294967295}}, h = 0, key = 0x0}
(gdb) p executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[0].val.value.str.val
$5 = "f"
(gdb) p (char(*)[3])(&executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[0].val.value.str.val)
$6 = (char (*)[3]) 0x7ffff7a6b638
(gdb) p (char (*) [3])(&executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[0].val.value.str.val)
$7 = (char (*)[3]) 0x7ffff7a6b638
(gdb) p *(char (*) [3])(&executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[0].val.value.str.val)
$8 = "foo"
(gdb) p *(char (*) [3])(&executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[1].val.value.str.val)
$9 = "foo"
(gdb) p *(char (*) [3])(&executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[2].val.value.str.val)
$10 = "abc"
(gdb) p *(char (*) [3])(&executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[3].val.value.str.val)
$11 = "xyz"
(gdb) p *(char (*) [3])(&executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[3].val.value.str.val)
$12 = "xyz"
(gdb) p executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[0].h
$13 = 0
(gdb) p executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[1].h
$14 = 9223372036854953478                                                   #key='a',h=9223372036854953478
(gdb) p executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[2].h
$15 = 2
(gdb) p executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[3].h
$16 = 3
(gdb) p executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[0].h
$17 = 0
(gdb) p (char (*) [3])(&executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[0].val.value.str.val)
$18 = (char (*)[3]) 0x7ffff7a6b638
(gdb) p *(char (*) [3])(&executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[0].val.value.str.val)
$19 = "foo"
(gdb) p executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[1].h
$20 = 9223372036854953478
(gdb) p *(char (*) [3])(&executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[1].val.value.str.val)
$21 = "foo"
(gdb) p executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[2].h
$22 = 2
(gdb) p *(char (*) [3])(&executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[2].val.value.str.val)
$23 = "abc"
(gdb) p executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[3].h
$24 = 3
(gdb) p *(char (*) [3])(&executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[3].val.value.str.val)
$25 = "xyz"
(gdb) p ((uint32_t)(executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData))[-1]
cannot subscript something of type `unsigned int'
(gdb) p ((uint32_t *)(executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData))[-1] #这里是对数组进行类型转换，这样寻址时就是arData+index*sizeof(uint32_t)，如果写成(uint32_t)executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData[-1]那么还是按sizeof(bucket)进行寻址的
$26 = 4294967295
(gdb) p ((uint32_t *)(executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData))[-2]
$27 = 4294967295
(gdb) p ((uint32_t *)(executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData))[-3]
$28 = 4294967295
(gdb) p ((uint32_t *)(executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData))[-4]
$29 = 4294967295
(gdb) p ((uint32_t *)(executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData))[-5]
$30 = 4294967295
(gdb) p ((uint32_t *)(executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData))[-6]
$31 = 4294967295
(gdb) p ((uint32_t *)(executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData))[-7]
$32 = 4294967295
(gdb) p ((uint32_t *)(executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData))[-8]
$33 = 4294967295
(gdb) p ((uint32_t *)(executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData))[-9]
$34 = 4294967295
(gdb) p ((uint32_t *)(executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData))[-10]
$35 = 1
(gdb) p ((uint32_t *)(executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData))[-11]
$36 = 4294967295
(gdb) p ((uint32_t *)(executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData))[-12]
$37 = 4294967295
(gdb) p ((uint32_t *)(executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData))[-13]
$38 = 3
(gdb) p ((uint32_t *)(executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData))[-14]
$39 = 2
(gdb) p ((uint32_t *)(executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData))[-15]
$40 = 4294967295
(gdb) p ((uint32_t *)(executor_globals.symbol_table.arData[7].val.value.zv.value.arr.arData))[-16]
$41 = 0

在$3中可以看到nTableMask = 4294967280，也就是-16，因为负载因子为0.5，最小nTableSize=8。再看索引数组的值，其中arData[-10]=1，arData[-13]=3，arData[-14]=2，arData[-16]=0。可以计算一下

>>> -16 | 0                     #nTableMask=-16，与上0等于-16，所以arData[-16]保存的是key=0的bucket在bucket数组中的索引
-16
>>> -16 | 1 
-15
>>> -16 | 2                     #nTableMask=-16，与上2等于-14，所以arData[-14]保存的是key=2的bucket在bucket数组中的索引
-14
>>> -16 | 3                     #nTableMask=-16，与上3等于-13，所以arData[-13]保存的是key=3的bucket在bucket数组中的索引
-13
>>> -16 | 9223372036854953478     ##nTableMask=-16，与上key='a'的h值等于-10，所以arData[-10]保存的是key='a'的bucket在bucket数组中的索引
-10

因此书上的索引数组应该不对。

php7变量实现_array

PHP数组实现

php5的数组实现

php7的数组实现

bucket分类

部分zend_array属性

数组初始化

为HashTable分配内存

为arData数组分配内存

hash array和packed array

负载因子（Load Factor）

参考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读