Unity DOTS中的Entity

在DOTS中entity往往只被看作一个ID，用来查找component，但实际上Unity为了有效地管理entity，在背后还做了一些其他的工作。首先是Entity类本身的定义，它的确跟一个ID差不多，只包含了两个int类型的成员：

public struct Entity : IEquatable<Entity>, IComparable<Entity>
{
    /// <summary>
    /// The ID of an entity.
    /// </summary>
    /// <value>The index into the internal list of entities.</value>
    /// <remarks>
    /// Entity indexes are recycled when an entity is destroyed. When an entity is destroyed, the
    /// EntityManager increments the version identifier. To represent the same entity, both the Index and the
    /// Version fields of the Entity object must match. If the Index is the same, but the Version is different,
    /// then the entity has been recycled.
    /// </remarks>
    public int Index;
    /// <summary>
    /// The generational version of the entity.
    /// </summary>
    /// <remarks>The Version number can, theoretically, overflow and wrap around within the lifetime of an
    /// application. For this reason, you cannot assume that an Entity instance with a larger Version is a more
    /// recent incarnation of the entity than one with a smaller Version (and the same Index).</remarks>
    /// <value>Used to determine whether this Entity object still identifies an existing entity.</value>
    public int Version;
}

这里的Index，并非是表示entity在chunk中的存储位置，它是一个二级索引，指向管理entity的block。block才真正记录了entity位于哪个chunk，以及在chunk中的具体位置。之所以这样设计，是因为在structural change时（例如AddComponent，RemoveComponent）entity会从一个chunk移动到另一个chunk。使用二级索引，就可以保证在发生移动时，entity的index保持不变，变化的只是block中的内容。

另外，从代码中的注释可知，entity的Index是会循环利用的，当一个entity销毁时，另一个创建的entity可能会复用到之前entity的Index，所以entity还包含一个Version字段。只有当Index和Version同时相等时，两个entity才会被视为相等。Version字段的默认值为0，每当entity创建时都会+1，销毁时也会+1，这意味着只有当Version为奇数时，entity才是存在的。

管理entity的block是全局唯一的，它是一个长度为16K的64位指针数组，其中每个指针指向一个更小的data block，data block最多可记录8K数量的entity状态。所以Unity全局最多可以支持16K * 8K数量的entity。

struct DataBlock
{
    // 8k entities per DataBlock
    public fixed ulong allocated[k_EntitiesInBlock / 64];
    public fixed ulong entityInChunk[k_EntitiesInBlock];
    public fixed int versions[k_EntitiesInBlock];
#if !DOTS_DISABLE_DEBUG_NAMES
    public fixed int nameByEntityIndex[k_EntitiesInBlock];
#endif
}

const int k_EntitiesInBlock = 8192;

这里可以看到记录data block当前分配entity使用的是8192 / 64大小的unsigned long数组，这是由于unsigned long本身是64位的，每一个二进制位都可以表示是否被分配，所以数组的大小可以省下来。

来看下创建entity的具体逻辑，看上去比较复杂：

internal void AllocateEntities(Entity* entities, int totalCount, ChunkIndex chunkIndex, int firstEntityInChunkIndex)
{
    var entityInChunkIndex = firstEntityInChunkIndex;

    for (int i = 0; i < k_BlockCount; i++)
    {
        var blockCount = Interlocked.Add(ref m_EntityCount[i], 0);

        if (blockCount == k_BlockBusy || blockCount == k_EntitiesInBlock)
        {
            continue;
        }

        var blockAvailable = k_EntitiesInBlock - blockCount;
        var count = math.min(blockAvailable, totalCount);

        // Set the count to a flag indicating that this block is busy (-1)
        var before = Interlocked.CompareExchange(ref m_EntityCount[i], k_BlockBusy, blockCount);

        if (before != blockCount)
        {
            // Another thread is messing around with this block, it's either busy or was changed
            // between the time we read the count and now. In both cases, let's keep looking.
            continue;
        }

        DataBlock* block = (DataBlock*)m_DataBlocks[i];

        // Be careful that the block might exist even if the count is zero, checking the pointer
        // for null is the only valid way to tell if the block exists or not.
        if (block == null)
        {
            block = (DataBlock*)Memory.Unmanaged.Allocate(k_BlockSize, 8, Allocator.Persistent);
            UnsafeUtility.MemClear(block, k_BlockSize);
            m_DataBlocks[i] = (ulong)block;
        }

        int remainingCount = math.min(blockAvailable, count);
        var allocated = block->allocated;
        var versions = block->versions;
        var entityInChunk = block->entityInChunk;
        var baseEntityIndex = i * k_EntitiesInBlock;

        while (remainingCount > 0)
        {
            for (int maskIndex = 0; maskIndex < k_EntitiesInBlock / 64; maskIndex++)
            {
                if (allocated[maskIndex] != ~0UL)
                {
                    // There is some space in this one

                    for (int entity = 0; entity < 64; entity++)
                    {
                        var indexInBlock = maskIndex * 64 + entity;
                        var mask = 1UL << (indexInBlock % 64);

                        if ((allocated[maskIndex] & mask) == 0)
                        {
                            allocated[maskIndex] |= mask;

                            *entities = new Entity
                            {
                                Index = baseEntityIndex + indexInBlock,
                                Version = versions[indexInBlock] += 1
                            };

                            if (chunkIndex != ChunkIndex.Null)
                            {
                                ((EntityInChunk*)entityInChunk)[indexInBlock] = new EntityInChunk
                                {
                                    Chunk = chunkIndex,
                                    IndexInChunk = entityInChunkIndex,
                                };
                            }
                            else
                            {
                                entityInChunk[indexInBlock] = 0;
                            }

                            entities++;
                            entityInChunkIndex++;
                            remainingCount--;

                            if (remainingCount == 0)
                            {
                                break;
                            }
                        }
                    }

                    if (remainingCount == 0)
                    {
                        break;
                    }
                }
            }
        }

        Assert.AreEqual(0, remainingCount);

        var resultCheck = Interlocked.CompareExchange(ref m_EntityCount[i], blockCount + count, k_BlockBusy);

        Assert.AreEqual(resultCheck, k_BlockBusy);

        totalCount -= count;

        if (totalCount == 0)
        {
            return;
        }
    }

    throw new InvalidOperationException("Could not find a data block for entity allocation.");
}

虽然有一定代码量，但是要做的事情其实是很直观的。具体来说可以分为以下几个步骤：

• 找到第一个可用的data block，如果某个block分配已满（entity数量为8K），或者被其他线程所占用（entity数量被置为busy），则说明不可用；
• 对可用的data block尝试加锁（即将其entity数量置为busy），如果加锁失败，说明被其他线程抢先一步占用，直接放弃尝试下一个data block；
• 加锁成功，查看data block当前的分配状态，如果分配状态为空，创建一个新的内存块并指向它；
• 在分配状态中寻找空闲的二进制位，根据它的位置计算出entity的Index，也就是指向block的二级索引，同时entity的Version自增，表示新建；
• 把entity在chunk中的实际位置信息（位于哪个chunk，以及在chunk中的位置）记录到block中；
• 释放之前加的锁，恢复data block的entity数量为正确的值。

当有了一个entity之后，又如何判断它是否还真实存在呢？这时候Version就派上用场了，data block里存着的永远是最新的Version，直接对比一下就好：

internal bool Exists(Entity entity)
{
    var blockIndex = entity.Index / k_EntitiesInBlock;
    var indexInBlock = entity.Index % k_EntitiesInBlock;

    var block = (DataBlock*)m_DataBlocks[blockIndex];
    if (block == null) return false;

    if (((uint)entity.Version & 1) == 0 || block->versions[indexInBlock] != entity.Version) return false;
    return true;
}

销毁entity的逻辑也是类似的，只不过销毁只处理data block分配状态的二进制位，将其置回为0，Version字段继续自增，表示已销毁。另外，就算block的分配状态为全空，也不会将block的内存回收掉。

for (int j = startIndex, indexInEntitiesArray = rangeStart; j < endIndex; j++, indexInEntitiesArray++)
{
    var indexInBlock = j % k_EntitiesInBlock;

    if (versions[indexInBlock] == entities[indexInEntitiesArray].Version)
    {
        // Matching versions confirm that we are deallocating the intended entity

        var mask = 1UL << (indexInBlock % 64);

        versions[indexInBlock]++;
        allocated[indexInBlock / 64] &= ~0UL ^ mask;

#if !DOTS_DISABLE_DEBUG_NAMES
        block->nameByEntityIndex[indexInBlock] = default;
#endif

        blockCount--;
    }
}

// Do not deallocate the block even if it's empty. Versions should be preserved.

{
    var resultCheck = Interlocked.CompareExchange(ref m_EntityCount[blockIndex], blockCount, k_BlockBusy);
    Assert.AreEqual(resultCheck, k_BlockBusy);
}

最后我们来看一下chunk的创建与销毁。当出现无处安放的entity时，就需要创建新的chunk。在前一篇文章中我们提到过，chunk不是单独分配的，而是按照64 * 16K大小进行分配的，这块内存成为mega chunk。Unity最多可以创建16384个mega chunk。 那么，Unity最多需要管理16384*64个chunk，为了提高效率，Unity使用了两个查找表，方便快速定位到空闲的chunk。

Ulong16384 m_chunkInUse;
Ulong256   m_megachunkIsFull;

m_megachunkIsFull把所有mega chunk分为256组，每组64个，那么每个mega chunk刚好可以用一个unsigned long表示；同样地，m_chunkInUse可表示16384个mega chunk，而每一个unsigned long，刚好可以表示每一个chunk的状态。

public int AllocateContiguousChunks(out ChunkIndex value, int requestedCount, out int actualCount)
{
    int gigachunkIndex = 0;
    for(; gigachunkIndex < m_megachunkIsFull.Length; ++gigachunkIndex)
        if(m_megachunkIsFull.ElementAt(gigachunkIndex) != ~0L)
            break;
    int firstMegachunk = gigachunkIndex << 6;
    actualCount = math.min(chunksPerMegachunk, requestedCount); // literally can't service requests for more
    value = ChunkIndex.Null;
    while(actualCount > 0)
    {
        for(int offset = 0; offset < megachunksInUniverse; ++offset)
        {
            int megachunkIndex = (firstMegachunk + offset) & (megachunksInUniverse-1); // index of current megachunk
            long maskAfterAllocation, oldMask, newMask, readMask = m_chunkInUse.ElementAt(megachunkIndex); // read the mask of which chunks are allocated
            int chunkInMegachunk; // index of first chunk allocated in current megachunk
            do {
                oldMask = readMask;
                if(oldMask == ~0L)
                    goto NEXT_MEGACHUNK; // can't find any bits, try the next megachunk
                if(!ConcurrentMask.foundAtLeastThisManyConsecutiveZeroes(oldMask, actualCount, out chunkInMegachunk, out int _)) // find consecutive 0 bits to allocate into
                    goto NEXT_MEGACHUNK; // can't find enough bits, try the next megachunk
                newMask = maskAfterAllocation = oldMask | ConcurrentMask.MakeMask(chunkInMegachunk, actualCount); // mask in the freshly allocated bits
                if(oldMask == 0L) // if we're the first to allocate from this megachunk,
                    newMask = ~0L; // mark the whole megachunk as full (busy) until we're done allocating memory
                readMask = Interlocked.CompareExchange(ref m_chunkInUse.ElementAt(megachunkIndex), newMask, oldMask);
            } while(readMask != oldMask);
            int firstChunkIndex = (megachunkIndex << log2ChunksPerMegachunk) + chunkInMegachunk;
            if(oldMask == 0L) // if we are the first allocation in this chunk...
            {
                long allocated = (long)Memory.Unmanaged.Allocate(MegachunkSizeInBytes, CollectionHelper.CacheLineSize, Allocator.Persistent); // allocate memory
                if (allocated == 0L) // if the allocation failed...
                    return AllocationFailed(firstChunkIndex, actualCount);
                Interlocked.Exchange(ref m_megachunk.ElementAt(megachunkIndex), allocated); // store the pointer to the freshly allocated memory
                Interlocked.Exchange(ref m_chunkInUse.ElementAt(megachunkIndex), maskAfterAllocation); // change the mask from ~0L to the true mask after our allocation (which may be ~0L)
            }
            if(maskAfterAllocation == ~0L)
                ConcurrentMask.AtomicOr(ref m_megachunkIsFull.ElementAt(megachunkIndex>>6), 1L << (megachunkIndex & 63));
            value = new ChunkIndex(firstChunkIndex);
            return kErrorNone;
            NEXT_MEGACHUNK:;
        }
        actualCount >>= 1;
    }
    return kErrorNoChunksAvailable;
}

这里分配chunk的代码也是比较直观的，从流程上可以分为以下步骤：

• 首先通过m_megachunkIsFull，找到空闲的mega chunk组gigachunkIndex；
• 通过gigachunkIndex，得到第一个空闲的mega chunk的index，再查找m_chunkInUse，得到此时该mega chunk中64个chunk的空闲情况；
• 如果chunk都已分配完毕，或者此时正被其他线程所占用，那么放弃该mega chunk，尝试下一个可用的mega chunk；
• 如果找到空闲的chunk，那么尝试加锁，如果加锁失败则一直等待，除非发生上一步的情况，才会放弃该mega chunk；
• 加锁成功，如果整个mega chunk都是空闲的，说明这个mega chunk压根还没实际分配内存，需要分配完内存后保存地址指针；
• 如果mega chunk不再有空闲的chunk，则需要记录回m_megachunkIsFull中；
• 返回可用的chunk。

销毁chunk的逻辑也是类似的，当chunk中entity数量为0时就会触发。由于chunk是以mega chunk为单位进行分配的，所以只有当整个mega chunk都是空闲时，才会真正地释放整个mega chunk的内存。

Reference

[1] Entity concepts

[2] Unity DOTS中的Archetype与Chunk

[3] Interlocked.CompareExchange Method