var (
	// 锁
	allPoolsMu Mutex

	// 全局的所有缓存池
	allPools []*Pool

	// victim cache 缓存池
	oldPools []*Pool
)

// Pool 一旦使用后，便不能再复制

// 在 Go 内存模型术语中，调用 Put(x) 方法在调用 Get 方法之前同步 
// 在 Go 内存模型术语中，调用 New 方法在调用 Get 方法之前同步
type Pool struct {
    // noCopy 可以添加到 struct 中，实现 "首次使用之后，无法被复制" 的功能，主要服务于 `go vet`
	// 假设一个缓存池对象 A 被对象 B 拷贝了，接着 A 被清空了，B 里面的缓存对象指针指向的对象将会不可控
	noCopy noCopy

	// 指向固定长度的数组，数组长度为处理器 P 的个数，转换后其实就是 [P]poolLocal 数组
	//    实际的底层数据结构是切片，不过下文中统一用数组描述，读者不必在意这个细节
	// 访问时根据处理器 P 的 ID (作为索引) 去访问
	// 优化点: 多个 goroutine 使用同一个缓存池时，可以减少竞争，提高性能
	//        类似于分段锁中降低锁粒度的设计理念
	local     unsafe.Pointer
	// local 数组的长度
	localSize uintptr
	
    // 上一轮的 local, 内容语义和 local 一致
	// 新一轮 GC 到来时，更新为当前 local 的值
	victim     unsafe.Pointer
	
	// 上一轮的 localSize, 内容语义和 localSize 一致
	// 新一轮 GC 到来时，更新为当前 localSize 的值
	victimSize uintptr

	// 创建对象的函数
	New func() any  
}

type poolLocal struct {
	poolLocalInternal

	// CPU Cache 是距离 CPU 最近的 Cache，如果能充分利用，会极大提升程序性能
	// 防止伪共享，凑齐 128 bytes 的整数倍 (这个小技巧非常值得学习)
	
	// 什么是CPU 伪共享？
	//   CPU CacheLine 通常是以 64 byte 或 128 byte 为单位
	//   在缓存池场景中，各个 P 的 poolLocal 以数组形式存储在一起
	//   假设 CPU CacheLine 为 128 byte，而 poolLocal 不足 128 byte 时
	//   CacheLine 将会带上其他 P 的 poolLocal 的内存数据，以凑齐一个整块的 CacheLine
	//   如果这时两个相邻的 P 同时在两个不同的 CPU 核上运行，将会同时去覆盖刷新 CacheLine 
	//   造成 CacheLine 的反复失效，那 CPU Cache 就失去了作用
	
	//   例如 两个相邻但是不同的处理器 P (PA, PB) 被分配在同一个 CacheLine
	//   此时 PA 要修改, PB 也要修改 (两者去竞争 同一个 CacheLine)
	//   当 PA 被修改时，缓存系统强制 PB 所在 CPU 核的 CacheLine 失效
	//   当 PB 被修改时，缓存系统强制 PA 所在 CPU 核的 CacheLine 失效
	//   最终导致 PA 和 PB 所在 CPU 核的 CacheLine 失效，降低性能
	
	// 如何避免 CPU 伪共享？
	//   将需要独立访问的变量放在不同的 CacheLine 中
	//   保证和 CacheLine 内存对齐
	
	// Linux 查看 CacheLine 单位大小
	// $ cat /sys/devices/system/cpu/cpu1/cache/index0/coherency_line_size
	pad [128 - unsafe.Sizeof(poolLocalInternal{})%128]byte
}

type poolLocalInternal struct {
    // 私有变量，只能由当前处理器操作
	private any
    // 共享变量，当前处理器可以执行 pushHead/popHead 操作，其他处理器只能执行 popTail 操作
	shared  poolChain 
}

// 队列节点示意图
// --------------------------------------------------------------------------
// | 节点 1, size: 64 | 节点 2, size: 32 | 节点 3, size: 16 | 节点 4, size: 8 |
// --------------------------------------------------------------------------

type poolChain struct {
	// head 表示头节点队列，只能由生产者操作，不存在竞争
	head *poolChainElt

	// tail 表示尾节点队列，由多个消费者操作，存在竞争
	tail *poolChainElt
}

type poolChainElt struct {
	poolDequeue
	
	// next 由生产者原子性写入，由消费者原子性读取
	// 值只会从 nil 转换为非 nil
	
	// prev 由消费者原子性写入，由生产者原子性读取
	// 值只会从非 nil 转换为 nil
	next, prev *poolChainElt
}

type poolDequeue struct {
	// 经典的字段合并使用方法
    // 高 32 位 是 head, 指向下一个存放对象的索引 
    // 低 32 位 是 tail, 指向队列中最早 (下一个读取) 的对象索引
	
	// 索引区间 tail <= i < head, 表示消费者可以操作的索引区域
	// 消费者可以在该区间不断获取对象，直至获取到的对象为 nil
	headTail uint64

	// vals 表示队列元素容器，大小必须为 2 的 N 次幂
	// 容器会在初始化时指定容量，实现数据元素内存预初始化
	vals []eface
}

func (p *Pool) Put(x any) {
    ...
	
	l, _ := p.pin()
	if l.private == nil {
		// 优先设置私有变量
		l.private = x  
	} else {
		// 其次设置共享变量
		l.shared.pushHead(x)
	}
    
	...
}

func (c *poolChain) pushHead(val any) {
	d := c.head
	if d == nil {
		// 初始化头节点
		// 对象池元素数量从 8 个开始，必须为 2 的 N 次幂
		const initSize = 8 
		d = new(poolChainElt)
		d.vals = make([]eface, initSize)
		c.head = d
		storePoolChainElt(&c.tail, d)
	}
	
	if d.pushHead(val) {
		// 如果对象成功加入队列，直接返回
		return
	}

	// 如果当前队列已满，分配一个新的队列 (长度是当前队列的 2 倍)
	newSize := len(d.vals) * 2
	if newSize >= dequeueLimit {
		// 队列长度最大为 1073741824
		newSize = dequeueLimit
	}

	// 初始化新的队列
	d2 := &poolChainElt{prev: d}
	d2.vals = make([]eface, newSize)
	// 将头节点指向到新的队列
	c.head = d2
	// 将新的队列添加到链表中
	storePoolChainElt(&d.next, d2)
    // 将对象添加到新的队列
	d2.pushHead(val)
}

func (d *poolDequeue) pushHead(val any) bool {
	ptrs := atomic.LoadUint64(&d.headTail)
	head, tail := d.unpack(ptrs)
	if (tail+uint32(len(d.vals)))&(1<<dequeueBits-1) == head {
        // 说明队列已满 (tail 索引 + 当前队列元素个数) == head 索引
		return false
	}
	slot := &d.vals[head&uint32(len(d.vals)-1)]

	// 检测索引位置的对象是否和 popTail 方法操作冲突
	typ := atomic.LoadPointer(&slot.typ)
	if typ != nil {
		// 有其他 goroutine 正在调用 popTail 方法操作当前位置的对象
		// 所以队列实际上已满
		return false
	}
	
	// 执行到这里，typ == nil 
	// 说明即使存在 popTail 方法操作当前位置的对象，操作也已经结束了，冲突解除
	if val == nil {
		val = dequeueNil(nil)
	}
	// 使用归还的对象填充索引位置
	*(*any)(unsafe.Pointer(slot)) = val

	// head 索引 + 1
	atomic.AddUint64(&d.headTail, 1<<dequeueBits)
	return true
}

func (p *Pool) Get() any {
	l, pid := p.pin()
    // 首先尝试从当前处理器的私有变量获取对象
	x := l.private 
	// 从私有变量获取后，及时将私有变量置为 nil
	l.private = nil
	
	if x == nil {
		// 私有变量没有获取到对象，尝试从共享变量获取
		x, _ = l.shared.popHead()
		if x == nil {
			// 当前处理器 P 没有对象，尝试从其他处理器窃取
			x = p.getSlow(pid)
		}
	}

	// 如果从所有处理器的缓存池都没有获取到对象，并且 New 方法不为 nil
	// 那就调用 New 方法创建一个对象返回
	if x == nil && p.New != nil {
		x = p.New()
	}
	return x
}

func (c *poolChain) popHead() (any, bool) {
	d := c.head
	for d != nil {
        // 从队列头部开始获取对象
		if val, ok := d.popHead(); ok {  
			return val, ok
		}
		// 将当前队列前驱节点作为接下来要遍历的队列
		d = loadPoolChainElt(&d.prev)
	}
	return nil, false
}

func (d *poolDequeue) popHead() (any, bool) {
	var slot *eface
	for {
		ptrs := atomic.LoadUint64(&d.headTail)
		// 高 32 bit 是 head
		// 低 32 bit 是 tail
		head, tail := d.unpack(ptrs)
		if tail == head {
			// 头尾相等，说明队列为空
			return nil, false
		}
		
		// head 索引指向下一个新对象的索引位置，所以使用前先减 1
		head--
		ptrs2 := d.pack(head, tail)
		if atomic.CompareAndSwapUint64(&d.headTail, ptrs, ptrs2) {
			// CAS 操作成功，移除头部的对象，此时 head 指向 head - 1
			// vals 切片的长度是 2 的 N 次幂，因此 len(d.vals)-1 之后，低的 N 位全是 1
			// 和 head 进行与运算之后，可以获取到对象的索引下标
			// 例如: 切片长度 = 32, len(d.vals)-1 = 31
			//      head = 5, 索引下标 = 5 & 31 = 5
			//      head = 25, 索引下标 = 25 & 31 = 25
			slot = &d.vals[head&uint32(len(d.vals)-1)]
			break
		}
	}
	
	val := *(*any)(unsafe.Pointer(slot))
	if val == dequeueNil(nil) {
        // 获取到的对象是 nil
		val = nil
	}
	// 重置索引位置的元素
	*slot = eface{}
	// 返回获取到的对象
	return val, true
}

func (p *Pool) getSlow(pid int) any {
	// 原子加载 localSize 字段
	size := runtime_LoadAcquintptr(&p.localSize) 
	locals := p.local                            
	
	// 尝试从其他处理器获取对象
	for i := 0; i < int(size); i++ {
		// 注意这里定位处理器 P 的索引计算方式
		// pid+i+1 是为了忽略当前处理器 P
		l := indexLocal(locals, (pid+i+1)%int(size))
        // 从队列尾部获取，减少并发冲突
		if x, _ := l.shared.popTail(); x != nil { 
			return x
		}
	}

	// 如果从其他处理器没有获取到对象，尝试从 victim 缓存中获取 (也就是上一轮对象池中的对象)
	// 这样做可以尽可能地复用对象
	size = atomic.LoadUintptr(&p.victimSize)
	if uintptr(pid) >= size {
		// 当前处理器不存在于 victim 中，可能原因如下:
		// 1. victim 已经被标记为空
		// 2. 当前处理器比 victim 的长度要大，属于 "后来创建的"
		// 此时直接返回即可，否则会发生处理器 pid 索引越界错误
		return nil
	}

	// 下面开始尝试从 victim 中获取对象
	
    // 尝试从尾部处理器的私有变量获取对象
	locals = p.victim
	l := indexLocal(locals, pid)
	if x := l.private; x != nil {
		l.private = nil
		return x
	}
	
	// 尝试从其他处理器获取对象
	for i := 0; i < int(size); i++ {
        // 注意这里定位处理器 P 的索引计算方式和刚才的不同
		// 这里不需要忽略任何处理器
		l := indexLocal(locals, (pid+i)%int(size))
		// 从队列尾部获取，减少并发冲突
		if x, _ := l.shared.popTail(); x != nil { 
			return x
		}
	}
	
	// 将 victim 缓存标记为空，后续请求直接返回，避免多余的查询
	atomic.StoreUintptr(&p.victimSize, 0)

	return nil
}

func (c *poolChain) popTail() (any, bool) {
	d := loadPoolChainElt(&c.tail)
	if d == nil {
		// 如果链表尾部节点为 nil, 直接返回
		return nil, false
	}

	for {
		// 在队列尾部节点出队之前，提前加载 d.next 指针很重要 (删除链表节点的边界条件)
		// 因为 d 节点的尾元素出队之后，d 节点可能会变为 nil, 这样永远无法找到 d.next 节点了
		d2 := loadPoolChainElt(&d.next)

		if val, ok := d.popTail(); ok {
			return val, ok
		}

		if d2 == nil {
			// 如果 next 节点都变成 nil 了，说明队列已经空了
			return nil, false
		}
		
		// 代码执行到这里，说明尾部节点 (d) 为 nil
		// 这时就可以将其删除了，防止下次调用 popTail 时发生错误 (误以为队列已空)
		if atomic.CompareAndSwapPointer((*unsafe.Pointer)(unsafe.Pointer(&c.tail)), unsafe.Pointer(d), unsafe.Pointer(d2)) {
			// 删除 d2 的前驱节点，也就是 d (因为此时前驱节点已经没有数据了)
			storePoolChainElt(&d2.prev, nil)
		}
		d = d2
	}
}

func (d *poolDequeue) popTail() (any, bool) {
	var slot *eface
	for {
		ptrs := atomic.LoadUint64(&d.headTail)
		head, tail := d.unpack(ptrs)
		if tail == head {
            // 头尾相等，说明队列为空
			return nil, false
		}
		
		ptrs2 := d.pack(head, tail+1)
		if atomic.CompareAndSwapUint64(&d.headTail, ptrs, ptrs2) {
			// CAS 操作成功，移除尾部的对象，此时 tail 指向 tail + 1
			slot = &d.vals[tail&uint32(len(d.vals)-1)]
			break
		}
	}
	
	val := *(*any)(unsafe.Pointer(slot))
	if val == dequeueNil(nil) {
		val = nil
	}
	
	// 通过重置元素为 nil 的方式通知 pushHead 方法 (因为这两个方法存在并发操作同一位置元素的可能)
	// 当前位置的元素已经操作完成 (pushHead 方法操作当前元素时会检测否和 popTail 方法冲突)
	// 先重置 val, 再重置 typ
	slot.val = nil
	atomic.StorePointer(&slot.typ, nil)

	return val, true
}

func (p *Pool) pin() (*poolLocal, int) {
	pid := runtime_procPin()
    // 原子加载 localSize 字段
	s := runtime_LoadAcquintptr(&p.localSize) 
	l := p.local      
	if uintptr(pid) < s {
		// 如果 pid 小于 local 数组的长度
		// 说明对应的 poolLocal 对象已经创建，直接返回即可
		return indexLocal(l, pid), pid
	}
	
	// 代码执行到这里，一般是因为两种原因：
	// 1. 缓存池还未创建
	// 2. 处理器 P 的数量被动态调整了
	return p.pinSlow()
}

func (p *Pool) pinSlow() (*poolLocal, int) {
	runtime_procUnpin()
	allPoolsMu.Lock()
	defer allPoolsMu.Unlock()
	pid := runtime_procPin()
	
	// 加锁完成，就不需要原子性加载了
	s := p.localSize
	l := p.local
	if uintptr(pid) < s {
		// 双重检测
		// local 数组已经发生变化 (加锁期间被其他线程修改)
		// 直接返回即可
		return indexLocal(l, pid), pid
	}
	if p.local == nil {
		allPools = append(allPools, p)
	}
	
	// 使用处理器 P 的数量作为数组长度
	size := runtime.GOMAXPROCS(0)
	// 初始化新的 local 数组
	local := make([]poolLocal, size)
    // 原子更新 local 字段
	atomic.StorePointer(&p.local, unsafe.Pointer(&local[0]))
    // 原子更新 localSize 字段
	runtime_StoreReluintptr(&p.localSize, uintptr(size))     
	return &local[pid], pid
}

func indexLocal(l unsafe.Pointer, i int) *poolLocal {
	lp := unsafe.Pointer(uintptr(l) + uintptr(i)*unsafe.Sizeof(poolLocal{}))
	return (*poolLocal)(lp)
}

func init() {
    runtime_registerPoolCleanup(poolCleanup)
}

func poolCleanup() {
	// 函数会在 GC 过程中的 STW 阶段被调用

	// 清理 victim 缓存对象池
	for _, p := range oldPools {
		p.victim = nil
		p.victimSize = 0
	}

	// 将当前所有缓存池对象移动到 victim 缓存池对象
	for _, p := range allPools {
		p.victim = p.local
		p.victimSize = p.localSize
		p.local = nil
		p.localSize = 0
	}

	// 将全局缓存池移动到全局 victim 缓存池
	// 将全局 victim 重置为 nil
	oldPools, allPools = allPools, nil
}