TlsfAllocator.java

com.mojang.blaze3d.vertex.TlsfAllocator

信息

• 全限定名：com.mojang.blaze3d.vertex.TlsfAllocator
• 类型：public class
• 包：com.mojang.blaze3d.vertex
• 源码路径：src/main/java/com/mojang/blaze3d/vertex/TlsfAllocator.java
• 起始行号：L12
• 职责：

  TODO

字段/常量

• SECOND_LEVEL_BIN_LOG2

  • 类型: int
  • 修饰符: private static final
  • 源码定位: L13
  • 说明:

    TODO

• SECOND_LEVEL_BIN_COUNT

  • 类型: int
  • 修饰符: private static final
  • 源码定位: L14
  • 说明:

    TODO

• FIRST_LEVEL_INDEX_SHIFT

  • 类型: int
  • 修饰符: private static final
  • 源码定位: L15
  • 说明:

    TODO

• FIRST_LEVEL_BIN_COUNT

  • 类型: int
  • 修饰符: private static final
  • 源码定位: L16
  • 说明:

    TODO

• SMALL_BLOCK_SIZE

  • 类型: int
  • 修饰符: private static final
  • 源码定位: L17
  • 说明:

    TODO

• MAX_ALLOCATION_SIZE

  • 类型: long
  • 修饰符: private static final
  • 源码定位: L18
  • 说明:

    TODO

• ALIGN_SIZE

  • 类型: int
  • 修饰符: private static final
  • 源码定位: L19
  • 说明:

    TODO

• firstLevelBitmap

  • 类型: int
  • 修饰符: private
  • 源码定位: L20
  • 说明:

    TODO

• secondLevelBitmap

  • 类型: int[]
  • 修饰符: private final
  • 源码定位: L21
  • 说明:

    TODO

• freeLists

  • 类型: TlsfAllocator.Block[]
  • 修饰符: private final
  • 源码定位: L22
  • 说明:

    TODO

• totalMemorySize

  • 类型: long
  • 修饰符: private final
  • 源码定位: L23
  • 说明:

    TODO

• LOGGER

  • 类型: Logger
  • 修饰符: private static final
  • 源码定位: L24
  • 说明:

    TODO

内部类/嵌套类型

• com.mojang.blaze3d.vertex.TlsfAllocator.Allocation

  • 类型: class
  • 修饰符: public static
  • 源码定位: L283
  • 说明:

    TODO

• com.mojang.blaze3d.vertex.TlsfAllocator.Block

  • 类型: class
  • 修饰符: private static
  • 源码定位: L311
  • 说明:

    TODO

• com.mojang.blaze3d.vertex.TlsfAllocator.Heap

  • 类型: class
  • 修饰符: public static
  • 源码定位: L362
  • 说明:

    TODO

• com.mojang.blaze3d.vertex.TlsfAllocator.IndexPair

  • 类型: record
  • 修饰符: private
  • 源码定位: L371
  • 说明:

    TODO

构造器

public TlsfAllocator(TlsfAllocator.Heap heap) @ L26

• 构造器名：TlsfAllocator
• 源码定位：L26
• 修饰符：public

参数:

• heap: TlsfAllocator.Heap

说明:

TODO

方法

下面的方法块按源码顺序生成。

private TlsfAllocator.Block getBlockFromFreeList(int firstLevelIndex, int secondLevelIndex) @ L38

• 方法名：getBlockFromFreeList
• 源码定位：L38
• 返回类型：TlsfAllocator.Block
• 修饰符：private

参数:

• firstLevelIndex: int
• secondLevelIndex: int

说明:

TODO

private void setBlockFreeList(int firstLevelIndex, int secondLevelIndex, TlsfAllocator.Block block) @ L42

• 方法名：setBlockFreeList
• 源码定位：L42
• 返回类型：void
• 修饰符：private

参数:

• firstLevelIndex: int
• secondLevelIndex: int
• block: TlsfAllocator.Block

说明:

TODO

private static long alignUp(long x, long align) @ L46

• 方法名：alignUp
• 源码定位：L46
• 返回类型：long
• 修饰符：private static

参数:

• x: long
• align: long

说明:

TODO

private static long alignDown(long x, long align) @ L50

• 方法名：alignDown
• 源码定位：L50
• 返回类型：long
• 修饰符：private static

参数:

• x: long
• align: long

说明:

TODO

private static int findLastSignificantBit(long x) @ L54

• 方法名：findLastSignificantBit
• 源码定位：L54
• 返回类型：int
• 修饰符：private static

参数:

• x: long

说明:

TODO

private static int findFirstSignificantBit(int x) @ L58

• 方法名：findFirstSignificantBit
• 源码定位：L58
• 返回类型：int
• 修饰符：private static

参数:

• x: int

说明:

TODO

private TlsfAllocator.IndexPair getLevelIndex(long size) @ L62

• 方法名：getLevelIndex
• 源码定位：L62
• 返回类型：TlsfAllocator.IndexPair
• 修饰符：private

参数:

• size: long

说明:

TODO

private TlsfAllocator.IndexPair mappingSearch(long size) @ L75

• 方法名：mappingSearch
• 源码定位：L75
• 返回类型：TlsfAllocator.IndexPair
• 修饰符：private

参数:

• size: long

说明:

TODO

private void insertFreeBlock(TlsfAllocator.Block block) @ L85

• 方法名：insertFreeBlock
• 源码定位：L85
• 返回类型：void
• 修饰符：private

参数:

• block: TlsfAllocator.Block

说明:

TODO

private void removeFreeBlock(TlsfAllocator.Block block, int firstLevel, int secondLevel) @ L98

• 方法名：removeFreeBlock
• 源码定位：L98
• 返回类型：void
• 修饰符：private

参数:

• block: TlsfAllocator.Block
• firstLevel: int
• secondLevel: int

说明:

TODO

private void trimBlock(TlsfAllocator.Block block, long size) @ L120

• 方法名：trimBlock
• 源码定位：L120
• 返回类型：void
• 修饰符：private

参数:

• block: TlsfAllocator.Block
• size: long

说明:

TODO

public TlsfAllocator.Allocation allocate(long size, int align) @ L141

• 方法名：allocate
• 源码定位：L141
• 返回类型：TlsfAllocator.Allocation
• 修饰符：public

参数:

• size: long
• align: int

说明:

TODO

private void mergeBlockWithPrevious(TlsfAllocator.Block block) @ L183

• 方法名：mergeBlockWithPrevious
• 源码定位：L183
• 返回类型：void
• 修饰符：private

参数:

• block: TlsfAllocator.Block

说明:

TODO

private void mergeBlockWithNext(TlsfAllocator.Block block) @ L209

• 方法名：mergeBlockWithNext
• 源码定位：L209
• 返回类型：void
• 修饰符：private

参数:

• block: TlsfAllocator.Block

说明:

TODO

public void free(TlsfAllocator.Allocation allocation) @ L234

• 方法名：free
• 源码定位：L234
• 返回类型：void
• 修饰符：public

参数:

• allocation: TlsfAllocator.Allocation

说明:

TODO

public boolean isCompletelyFree() @ L245

• 方法名：isCompletelyFree
• 源码定位：L245
• 返回类型：boolean
• 修饰符：public

参数:

• 无

说明:

TODO

public void printAllocatorStatistics(String name) @ L259

• 方法名：printAllocatorStatistics
• 源码定位：L259
• 返回类型：void
• 修饰符：public

参数:

• name: String

说明:

TODO

代码

@OnlyIn(Dist.CLIENT)
public class TlsfAllocator {
    private static final int SECOND_LEVEL_BIN_LOG2 = 3;
    private static final int SECOND_LEVEL_BIN_COUNT = 8;
    private static final int FIRST_LEVEL_INDEX_SHIFT = 8;
    private static final int FIRST_LEVEL_BIN_COUNT = 32;
    private static final int SMALL_BLOCK_SIZE = 256;
    private static final long MAX_ALLOCATION_SIZE = 549755813888L;
    private static final int ALIGN_SIZE = 32;
    private int firstLevelBitmap = 0;
    private final int[] secondLevelBitmap = new int[32];
    private final TlsfAllocator.@Nullable Block[] freeLists = new TlsfAllocator.Block[256];
    private final long totalMemorySize;
    private static final Logger LOGGER = LogUtils.getLogger();
 
    public TlsfAllocator(TlsfAllocator.Heap heap) {
        long alignedHeapSize = alignDown(heap.size, 32L);
        TlsfAllocator.Block freeBlock = new TlsfAllocator.Block(alignedHeapSize, heap, 0L, null, null, null, null);
        freeBlock.setFree();
        this.insertFreeBlock(freeBlock);
        long remainingHeapSize = heap.size - alignedHeapSize;
        TlsfAllocator.Block sentinelBlock = new TlsfAllocator.Block(remainingHeapSize, heap, alignedHeapSize, null, null, null, freeBlock);
        sentinelBlock.setUsed();
        freeBlock.nextPhysicalBlock = sentinelBlock;
        this.totalMemorySize = alignedHeapSize;
    }
 
    private TlsfAllocator.@Nullable Block getBlockFromFreeList(int firstLevelIndex, int secondLevelIndex) {
        return this.freeLists[firstLevelIndex * 8 + secondLevelIndex];
    }
 
    private void setBlockFreeList(int firstLevelIndex, int secondLevelIndex, TlsfAllocator.@Nullable Block block) {
        this.freeLists[firstLevelIndex * 8 + secondLevelIndex] = block;
    }
 
    private static long alignUp(long x, long align) {
        return x + (align - 1L) & ~(align - 1L);
    }
 
    private static long alignDown(long x, long align) {
        return x - (x & align - 1L);
    }
 
    private static int findLastSignificantBit(long x) {
        return 63 - Long.numberOfLeadingZeros(x);
    }
 
    private static int findFirstSignificantBit(int x) {
        return Integer.numberOfTrailingZeros(x);
    }
 
    private TlsfAllocator.IndexPair getLevelIndex(long size) {
        if (Long.compareUnsigned(size, 256L) < 0) {
            int firstLevelIndex = 0;
            int secondLevelIndex = (int)Long.divideUnsigned(size, 32L);
            return new TlsfAllocator.IndexPair(0, secondLevelIndex);
        } else {
            int firstLevelIndex = findLastSignificantBit(size);
            int secondLevelIndex = (int)(size >>> firstLevelIndex - 3) ^ 8;
            firstLevelIndex -= 7;
            return new TlsfAllocator.IndexPair(firstLevelIndex, secondLevelIndex);
        }
    }
 
    private TlsfAllocator.IndexPair mappingSearch(long size) {
        long roundedSize = size;
        if (Long.compareUnsigned(size, 256L) >= 0) {
            long round = (1L << findLastSignificantBit(size) - 3) - 1L;
            roundedSize = size + round;
        }
 
        return this.getLevelIndex(roundedSize);
    }
 
    private void insertFreeBlock(TlsfAllocator.Block block) {
        TlsfAllocator.IndexPair levelIndex = this.getLevelIndex(block.getSize());
        TlsfAllocator.Block currentBlock = this.getBlockFromFreeList(levelIndex.firstLevelIndex, levelIndex.secondLevelIndex);
        if (currentBlock != null) {
            currentBlock.previousFreeBlock = block;
        }
 
        block.nextFreeBlock = currentBlock;
        this.firstLevelBitmap = this.firstLevelBitmap | 1 << levelIndex.firstLevelIndex;
        this.secondLevelBitmap[levelIndex.firstLevelIndex] = this.secondLevelBitmap[levelIndex.firstLevelIndex] | 1 << levelIndex.secondLevelIndex;
        this.setBlockFreeList(levelIndex.firstLevelIndex, levelIndex.secondLevelIndex, block);
    }
 
    private void removeFreeBlock(TlsfAllocator.Block block, int firstLevel, int secondLevel) {
        TlsfAllocator.Block next = block.nextFreeBlock;
        TlsfAllocator.Block previous = block.previousFreeBlock;
        if (previous != null) {
            previous.nextFreeBlock = next;
        }
 
        if (next != null) {
            next.previousFreeBlock = previous;
        }
 
        if (this.getBlockFromFreeList(firstLevel, secondLevel) == block) {
            this.setBlockFreeList(firstLevel, secondLevel, next);
            if (next == null) {
                this.secondLevelBitmap[firstLevel] = this.secondLevelBitmap[firstLevel] & ~(1 << secondLevel);
                if (this.secondLevelBitmap[firstLevel] == 0) {
                    this.firstLevelBitmap &= ~(1 << firstLevel);
                }
            }
        }
    }
 
    private void trimBlock(TlsfAllocator.Block block, long size) {
        if (Long.compareUnsigned(block.getSize(), size + 256L) > 0) {
            long remaining = block.getSize() - size;
            TlsfAllocator.Block remainingBlock = new TlsfAllocator.Block(
                remaining, block.heap, block.offsetFromHeap + size, null, null, block.nextPhysicalBlock, block
            );
            remainingBlock.setFree();
            TlsfAllocator.Block next = block.nextPhysicalBlock;
            if (next != null) {
                assert next.previousPhysicalBlock == block;
 
                next.previousPhysicalBlock = remainingBlock;
            }
 
            block.nextPhysicalBlock = remainingBlock;
            block.setSize(size);
            this.mergeBlockWithNext(remainingBlock);
            this.insertFreeBlock(remainingBlock);
        }
    }
 
    public TlsfAllocator.@Nullable Allocation allocate(long size, int align) {
        boolean isPowerOfTwo = Mth.isPowerOfTwo(align);
        int sizePadding = isPowerOfTwo && align <= 32 ? 0 : align;
        long alignedSize = alignUp(size + sizePadding, 32L);
 
        assert alignedSize <= 549755813888L;
 
        TlsfAllocator.IndexPair levelIndex = this.mappingSearch(alignedSize);
        int firstLevelIndex = levelIndex.firstLevelIndex;
        int secondLevelIndex = levelIndex.secondLevelIndex;
        long firstLevelSize = 1L << firstLevelIndex + 8 - 1;
        long secondLevelInterval = firstLevelSize / 8L;
        long slotSize = firstLevelSize + secondLevelIndex * secondLevelInterval;
        if (firstLevelIndex < 32) {
            int slBitmap = this.secondLevelBitmap[firstLevelIndex] & -1 << secondLevelIndex;
            if (slBitmap == 0) {
                int flBitmap = this.firstLevelBitmap & -1 << firstLevelIndex + 1;
                if (flBitmap == 0) {
                    return null;
                }
 
                firstLevelIndex = findFirstSignificantBit(flBitmap);
                slBitmap = this.secondLevelBitmap[firstLevelIndex];
            }
 
            secondLevelIndex = findFirstSignificantBit(slBitmap);
            TlsfAllocator.Block block = this.getBlockFromFreeList(firstLevelIndex, secondLevelIndex);
 
            assert block != null && block.getSize() >= alignedSize;
 
            this.removeFreeBlock(block, firstLevelIndex, secondLevelIndex);
            this.trimBlock(block, slotSize);
            block.setUsed();
            long gap = Long.remainderUnsigned(block.offsetFromHeap, align);
            long alignmentOffset = gap == 0L ? 0L : align - gap;
            long allocationOffset = block.offsetFromHeap + alignmentOffset;
            return new TlsfAllocator.Allocation(block, allocationOffset);
        } else {
            return null;
        }
    }
 
    private void mergeBlockWithPrevious(TlsfAllocator.Block block) {
        TlsfAllocator.Block previous = block.previousPhysicalBlock;
        if (previous != null && previous.isFree()) {
            assert previous.offsetFromHeap + previous.getSize() == block.offsetFromHeap;
 
            assert previous.nextPhysicalBlock == block;
 
            TlsfAllocator.IndexPair levelIndex = this.getLevelIndex(previous.getSize());
            this.removeFreeBlock(previous, levelIndex.firstLevelIndex, levelIndex.secondLevelIndex);
            TlsfAllocator.Block prevprev = previous.previousPhysicalBlock;
            if (prevprev != null) {
                assert prevprev.nextPhysicalBlock == previous;
 
                prevprev.nextPhysicalBlock = block;
            }
 
            block.previousPhysicalBlock = prevprev;
            block.setSize(block.getSize() + previous.getSize());
            block.offsetFromHeap = previous.offsetFromHeap;
            previous.previousPhysicalBlock = null;
            previous.nextPhysicalBlock = null;
            previous.nextFreeBlock = null;
            previous.previousFreeBlock = null;
        }
    }
 
    private void mergeBlockWithNext(TlsfAllocator.Block block) {
        TlsfAllocator.Block next = block.nextPhysicalBlock;
        if (next != null && next.isFree()) {
            assert next.offsetFromHeap - block.getSize() == block.offsetFromHeap;
 
            assert next.previousPhysicalBlock == block;
 
            TlsfAllocator.IndexPair levelIndex = this.getLevelIndex(next.getSize());
            this.removeFreeBlock(next, levelIndex.firstLevelIndex, levelIndex.secondLevelIndex);
            TlsfAllocator.Block nextnext = next.nextPhysicalBlock;
            if (nextnext != null) {
                assert nextnext.previousPhysicalBlock == next;
 
                nextnext.previousPhysicalBlock = block;
            }
 
            block.nextPhysicalBlock = nextnext;
            block.setSize(block.getSize() + next.getSize());
            next.previousPhysicalBlock = null;
            next.nextPhysicalBlock = null;
            next.nextFreeBlock = null;
            next.previousFreeBlock = null;
        }
    }
 
    public void free(TlsfAllocator.Allocation allocation) {
        if (!allocation.freed) {
            TlsfAllocator.Block block = allocation.block;
            block.setFree();
            this.mergeBlockWithPrevious(block);
            this.mergeBlockWithNext(block);
            this.insertFreeBlock(block);
            allocation.freed = true;
        }
    }
 
    public boolean isCompletelyFree() {
        if (Long.bitCount(this.firstLevelBitmap) == 1) {
            int firstLevelIndex = findFirstSignificantBit(this.firstLevelBitmap);
            int slBitmap = this.secondLevelBitmap[firstLevelIndex];
            if (Long.bitCount(slBitmap) == 1) {
                int secondLevelIndex = findFirstSignificantBit(slBitmap);
                TlsfAllocator.Block freeBlock = this.getBlockFromFreeList(firstLevelIndex, secondLevelIndex);
                return freeBlock != null && freeBlock.getSize() == this.totalMemorySize;
            }
        }
 
        return false;
    }
 
    @VisibleForDebug
    public void printAllocatorStatistics(String name) {
        int freeBlockCount = 0;
        long freeMemorySize = 0L;
        int levelFreeBlockCount = 0;
 
        for (int i = 0; i < 32; i++) {
            for (int j = 0; j < 8; j++) {
                levelFreeBlockCount = 0;
 
                for (TlsfAllocator.Block block = this.getBlockFromFreeList(i, j); block != null; block = block.nextFreeBlock) {
                    levelFreeBlockCount++;
                    freeMemorySize += block.getSize();
                }
 
                freeBlockCount += levelFreeBlockCount;
            }
        }
 
        double unusedPercent = (double)freeMemorySize / this.totalMemorySize * 100.0;
        LOGGER.debug("Uber buffer {}, size: {} -- free-listed memory: {} -- free-block count:{}", name, this.totalMemorySize, unusedPercent, freeBlockCount);
    }
 
    @OnlyIn(Dist.CLIENT)
    public static class Allocation {
        private final TlsfAllocator.Block block;
        private final long offsetFromHeap;
        private boolean freed = false;
 
        private Allocation(TlsfAllocator.Block block, long offsetFromHeap) {
            this.block = block;
            this.offsetFromHeap = offsetFromHeap;
        }
 
        public long getSize() {
            return this.block.getSize();
        }
 
        public TlsfAllocator.Heap getHeap() {
            return this.block.heap;
        }
 
        public long getOffsetFromHeap() {
            return this.offsetFromHeap;
        }
 
        public boolean isFreed() {
            return this.freed;
        }
    }
 
    @OnlyIn(Dist.CLIENT)
    private static class Block {
        private long size = 0L;
        final TlsfAllocator.Heap heap;
        long offsetFromHeap;
        TlsfAllocator.@Nullable Block nextFreeBlock;
        TlsfAllocator.@Nullable Block previousFreeBlock;
        TlsfAllocator.@Nullable Block nextPhysicalBlock;
        TlsfAllocator.@Nullable Block previousPhysicalBlock;
        private static final int BLOCK_HEADER_FREE_BIT = 1;
 
        private Block(
            long size,
            TlsfAllocator.Heap heap,
            long offsetFromHeap,
            TlsfAllocator.@Nullable Block nextFreeBlock,
            TlsfAllocator.@Nullable Block previousFreeBlock,
            TlsfAllocator.@Nullable Block nextPhysicalBlock,
            TlsfAllocator.@Nullable Block previousPhysicalBlock
        ) {
            this.heap = heap;
            this.offsetFromHeap = offsetFromHeap;
            this.nextFreeBlock = nextFreeBlock;
            this.previousFreeBlock = previousFreeBlock;
            this.nextPhysicalBlock = nextPhysicalBlock;
            this.previousPhysicalBlock = previousPhysicalBlock;
            this.setSize(size);
        }
 
        private boolean isFree() {
            return (this.size & 1L) == 1L;
        }
 
        private void setFree() {
            this.size |= 1L;
        }
 
        private void setUsed() {
            this.size &= -2L;
        }
 
        private long getSize() {
            return this.size & -2L;
        }
 
        private void setSize(long size) {
            long oldSize = this.size;
            this.size = size | oldSize & 1L;
        }
    }
 
    @OnlyIn(Dist.CLIENT)
    public static class Heap {
        private final long size;
 
        Heap(long size) {
            this.size = size;
        }
    }
 
    @OnlyIn(Dist.CLIENT)
    private record IndexPair(int firstLevelIndex, int secondLevelIndex) {
    }
}

引用的其他类

• Mth
  • 引用位置: 方法调用
  • 关联成员: Mth.isPowerOfTwo()