go sync.Pool 设计与实现

func (engine *Engine) ServeHTTP(w http.ResponseWriter, req *http.Request) {
  // 从 Pool 中获取 Context
  c := engine.pool.Get().(*Context)
  // 重置 writermem
  c.writermem.reset(w)
  // 重置 Request
  c.Request = req
  // 重置其他字段
  c.reset()
  engine.handleHTTPRequest(c)
  // 将 Context 对象放回 Pool
  engine.pool.Put(c)
}

// newPrinter allocates a new pp struct or grabs a cached one.
func newPrinter() *pp {
  // 从 Pool 中获取 pp 对象
  p := ppFree.Get().(*pp)
  p.panicking = false
  p.erroring = false
  p.wrapErrs = false
  p.fmt.init(&p.buf)
  return p
}

// free saves used pp structs in ppFree; avoids an allocation per invocation.
func (p *pp) free() {
  if cap(p.buf) > 64<<10 {
    return
  }
  // 重置 p.buf
  p.buf = p.buf[:0]
  p.arg = nil
  p.value = reflect.Value{}
  p.wrappedErr = nil
  // 将 pp 放回 Pool 中
  ppFree.Put(p)
}

type Pool struct {
    // noCopy 用于防止 Pool 被复制（可以使用 go vet 检测）
  noCopy noCopy
  // local 的主要作用是，多个 goroutine 同时访问 Pool 时，可以减少竞争，提升性能。
  // 实际类型是 [P]poolLocal。长度是 localSize。
  local unsafe.Pointer
  // []poolLocal 的长度。也就是 local 切片的长度
  localSize uintptr
  // 存放的是上一轮 GC 时的 local 字段的值。
  victim unsafe.Pointer
  // victim 数组的长度
  victimSize uintptr
  // 新建对象的方法。
  // Get 的时候如果 Pool 中没有对象可用，会调用这个方法来新建一个对象。
  New func() any
}

// 实际存储 Pool 的数据的结构体
type poolLocalInternal struct {
  // private 用于存储 Pool 的 Put 方法传入的数据。
  // Get 的时候如果 private 不为空，那么直接返回 private 中的数据。
  // 只能被当前 P 使用。
  private any
  // 本地 P 可以pushHead/popHead
  // 任何 P 都可以 popTail。
  shared poolChain
}
// Pool 中的 local 属性的元素类型。
// Pool 中的 local 是一个元素类型为 poolLocal 的切片，长度为 runtime.GOMAXPROCS(0)。
type poolLocal struct {
  poolLocalInternal
  // pad 用于填充 poolLocalInternal 到 cache line 的大小。
  // 为了避免伪共享，将 poolLocalInternal 放在第一个字段。
  pad [128 - unsafe.Sizeof(poolLocalInternal{})%128]byte
}

// poolChain 是 poolDequeue 的动态大小版本。
//
// 这是作为 poolDequeues 的双向链表队列实现的，其中每个 dequeue 都是前一个 dequeue 大小的两倍。
// 一旦 dequeue 填满，就会分配一个新的 dequeue，并且 pushHead 只会 push 到最新的 dequeue。
// pop 可以从头部或者尾部进行，一旦 dequeue 空了，它就会从 poolChain 中删除。
//
// poolChain 的实现是一个双向链表，每个 poolChainElt 都是一个 poolDequeue。
//（也就是元素是 poolDequeue 的双向链表）
type poolChain struct {
  // head 是要推送到的 poolDequeue。
  // 只能由生产者访问，因此不需要同步。
  head *poolChainElt
  // tail 是从 poolDequeue 中 pop 的节点。
  // 这是由消费者访问的，因此读取和写入必须是原子的。
  tail *poolChainElt
}
// poolChainElt 是 poolChain 中的元素。
type poolChainElt struct {
  poolDequeue
  // next 和 prev 链接到此 poolChain 中相邻的 poolChainElts。
  //
  // next 由生产者原子写入，由消费者原子读取。 它只从 nil 过渡到 non-nil。
  // prev 由消费者原子写入，由生产者原子读取。 它只会从 non-nil 过渡到 nil。
  next, prev *poolChainElt
}
// poolDequeue 是一个无锁的固定大小的单生产者、多消费者队列。
// 单个生产者既可以从头部 push 也可以从头部 pop，消费者只可以从尾部 pop。
//
// 它有一个附加功能，它会清空不使用的槽，从而避免不必要的对象保留。
type poolDequeue struct {
  // headTail 将 32 位头索引和 32 位尾索引打包在一起。
  // 两者都是 vals modulo len(vals)-1 的索引。
  //
  // tail = 队列尾的索引
  // head = 下一个要填充的插槽的索引
  //
  // [tail, head) 范围内的槽位归消费者所有。
  // 消费者继续拥有此范围之外的槽，直到它清空槽，此时所有权传递给生产者。
  //
  // 头索引存储在最高有效位中，以便我们可以原子地对它做 add 操作，同时溢出是无害的。
  headTail uint64
  // vals 是存储在此 dequeue 中的 interface{} 值的环形缓冲区。它的大小必须是 2 的幂。
  // （队列存储的元素，接口类型）
  //
  // 如果插槽为空，则 vals[i].typ 为 nil，否则为非 nil。
  // 一个插槽仍在使用中，直到 *both* 尾部索引超出它并且 typ 已设置为 nil。（both？）
  // 这由消费者原子地设置为 nil，并由生产者原子地读取。
  vals []eface
}

// Get 从 Pool 中获取一个对象
func (p *Pool) Get() any {
  // ...
  // pin 将当前的 goroutine 和 P 绑定，禁止被抢占，返回当前 P 的本地缓存（poolLocal）和 P 的 ID。
  l, pid := p.pin()
  // 先看 private 是否为 nil，如果不为 nil，就直接返回 private，并将 private 置为 nil。
  x := l.private
  l.private = nil
  if x == nil {
    // 尝试从本地 shared 的头部取。
    x, _ = l.shared.popHead()
    if x == nil { // 如果本地 shared 的头部取不到，就从其他 P 的 shared 的尾部取。
      x = p.getSlow(pid)
    }
  }
  // 将当前的 goroutine 和 P 解绑，允许被抢占。
  runtime_procUnpin()
  // ...
  // 如果 x 为 nil 并且 p.New 不为 nil，则返回 p.New() 的结果。
  // 没有就 New 一个。
  if x == nil && p.New != nil {
    x = p.New()
  }
  return x
}

// 从其他 P 的 shared 的尾部取。
func (p *Pool) getSlow(pid int) any {
  // 获取 local 的大小和 local。
  size := runtime_LoadAcquintptr(&p.localSize) // load-acquire
  locals := p.local                            // load-consume
  // 尝试从其他 P 的 shared 的尾部取。
  for i := 0; i < int(size); i++ {
    l := indexLocal(locals, (pid+i+1)%int(size)) // pid+i+1 的用途从下一个 P 开始取。
    if x, _ := l.shared.popTail(); x != nil { // 尝试从每一个 P 的 shared 的尾部取，获取到则返回。
      return x
    }
  }
  // 尝试从 victim cache 取。
  // 我们在尝试从所有主缓存中偷取之后执行此操作，
  // 因为我们希望 victim cache 中的对象尽可能地老化。
  size = atomic.LoadUintptr(&p.victimSize)
  if uintptr(pid) >= size { // 如果 pid 大于 size，会发生越界，直接返回 nil。这意味着 gomaxprocs 相比上一次 poolCleanup 的时候变大了。
    return nil
  }
  locals = p.victim
  l := indexLocal(locals, pid)
  if x := l.private; x != nil { // victim 实际上也是一个 poolLocal 数组，每个 poolLocal 都有一个 private 字段，这个字段就是 victim cache。
    l.private = nil
    return x
  }
  for i := 0; i < int(size); i++ {
    l := indexLocal(locals, (pid+i)%int(size))
    if x, _ := l.shared.popTail(); x != nil {
      return x
    }
  }
  // 将 victim cache 标记为空，以便将来的 Get 不会再考虑它。
  atomic.StoreUintptr(&p.victimSize, 0)
  return nil
}

// 将当前的 goroutine 和 P 绑定，禁止被抢。
func (p *Pool) pin() (*poolLocal, int) {
  // procPin 函数的目的是为了当前 G 绑定到 P 上。
  pid := runtime_procPin() // 返回当前 P 的 id。
  // 在 pinSlow 中，我们会存储 local，然后再存储 localSize，
  // 这里我们以相反的顺序读取。 由于我们禁用了抢占，
  // 因此 GC 不能在两者之间发生。
  s := runtime_LoadAcquintptr(&p.localSize) // load-acquire
  l := p.local                              // load-consume
  if uintptr(pid) < s {                     // pid < s，说明当前 P 已经初始化过了。
    return indexLocal(l, pid), pid // 返回当前 P 的 poolLocal。
  }
  return p.pinSlow() // 如果当前 P 没有初始化过，那么就调用 pinSlow()。
}
func (p *Pool) pinSlow() (*poolLocal, int) {
  // 在互斥锁下重试。
  // 在固定时无法锁定互斥锁。
  runtime_procUnpin()       // 解除当前 P 的绑定。
  allPoolsMu.Lock()         // 加全局锁。
  defer allPoolsMu.Unlock() // 解锁。
  pid := runtime_procPin()  // 重新绑定当前 P。
  // 在固定时不会调用 poolCleanup。（无法被抢占，GC 不会发生）
  s := p.localSize
  l := p.local
  if uintptr(pid) < s { // 这其实是一个 double-checking，如果在加锁期间，其他 goroutine 已经初始化过了，就直接返回。
    return indexLocal(l, pid), pid
  }
  // p.local == nil 说明 pool 还没有初始化过。
  if p.local == nil { // 如果当前 P 没有初始化过，那么就将当前 P 添加到 allPools 中。
    allPools = append(allPools, p)
  }
  // 当 local 数组为空，或者和当前的 runtime.GOMAXPROCS 不一致时，
  // 将触发重新创建 local 数组，以和 P 的个数保持一致。
  // 如果在 GC 之间更改了 GOMAXPROCS，我们将重新分配数组并丢弃旧数组。
  size := runtime.GOMAXPROCS(0)                            // 获取当前 GOMAXPROCS（也就是 P 的个数）
  local := make([]poolLocal, size)                         // 创建一个 poolLocal 数组
  atomic.StorePointer(&p.local, unsafe.Pointer(&local[0])) // store-release // 将当前 P 的 poolLocal 添加到 p.local 中
  runtime_StoreReluintptr(&p.localSize, uintptr(size))     // store-release // 将当前 P 的 poolLocal 添加到 p.localSize 中
  return &local[pid], pid                                  // 返回当前 P 关联的 poolLocal，以及当前 P 的 id。
}

// l 指向了 poolLocal 数组的首地址，i 是数组的索引。
// 返回了数组中第 i 个元素，其类型是 poolLocal。
func indexLocal(l unsafe.Pointer, i int) *poolLocal {
  lp := unsafe.Pointer(uintptr(l) + uintptr(i)*unsafe.Sizeof(poolLocal{}))
  return (*poolLocal)(lp)
}

var (
  // 保护 allPools 和 oldPools 的互斥锁。
  allPoolsMu Mutex
  // allPools 是所有非空 primary cache 的 pool 的集合。
  // 该集合由 allPoolsMu 和 pinning 保护，或者 STW 保护。
  allPools []*Pool
  // oldPools 是所有可能非空 victim cache 的 pool 的集合。
  oldPools []*Pool
)

func poolCleanup() {
  // 在垃圾收集开始时，这个函数会被调用。
  // 它不能分配并且可能不应该调用任何运行时函数。
  // 从 allPools 中删除 victim 缓存。
  for _, p := range oldPools {
    p.victim = nil // 作用是让 GC 可以回收 victim 缓存中的对象。
    p.victimSize = 0
  }
  // 将 primary 缓存移动到 victim 缓存。
  for _, p := range allPools {
    p.victim = p.local
    p.victimSize = p.localSize
    p.local = nil
    p.localSize = 0
  }
  // 具有非空主缓存的池现在具有非空 victim 缓存，并且没有池具有 primary 缓存。
  oldPools, allPools = allPools, nil
}

// Put 将 x 添加到 Pool 中。
func (p *Pool) Put(x any) {
  if x == nil {
    return
  }
  // ...
  // 获取 poolLocal
  l, _ := p.pin() // 将当前 goroutine 与 P 绑定。获取当前 P 关联的 poolLocal，以及当前 P 的 id。
  if l.private == nil { // 优先放入 private
    l.private = x
  } else { // 如果 private 已经有值了，就放入 shared
    l.shared.pushHead(x) // 这部分其他 P 也是可以访问的。
  }
  runtime_procUnpin() // 解除当前 P 的绑定。
  // ...
}

// 添加一个元素到队列头部
func (c *poolChain) pushHead(val any) {
  // 链表头
  d := c.head
  if d == nil { // 链表为空
    // 初始化链表。
    // 新建 poolChainElt，然后 c 的 head 和 tail 都指向这个新建的元素。
    const initSize = 8 // 初始化大小为 8
    // 新建一个节点，类型为 poolChainElt
    d = new(poolChainElt)
    d.vals = make([]eface, initSize)
    // 将 c 的 head 和 tail 都指向这个新建的元素
    c.head = d
    // 使用原子操作保存 c.tail，因为其他 goroutine 也可能会修改 c.tail。
    storePoolChainElt(&c.tail, d)
  }
  // poolQueue 还没满的时候可以成功 push，pushHead 会返回 true。
  // poolQueue 满的时候 pushHead 返回 false。
  if d.pushHead(val) {
    return
  }
  // 当前 dequeue 已满。分配一个两倍大小的新 dequeue。
  newSize := len(d.vals) * 2
  if newSize >= dequeueLimit { // 限制单个 dequeue 的最大大小
    newSize = dequeueLimit
  }
  // 新建 poolChainElt，然后 c 的 head 指向这个新建的元素。
  // 同时，d 的 next 指向这个新建的元素。
  d2 := &poolChainElt{prev: d} // 因为是加到队列头，所以 prev 指向 d
  d2.vals = make([]eface, newSize)
  c.head = d2
  storePoolChainElt(&d.next, d2)
  d2.pushHead(val)
}

// pushHead 在队列的头部添加 val。
// 如果队列已满，则返回 false。
// 它只能由单个生产者调用。（也就是当前 goroutine 绑定的 P）
//
// 注意：head 指向的是下一个要插入的元素的位置，所以插入的时候，先将 head 指向的位置设置为 val，然后 head++。
func (d *poolDequeue) pushHead(val any) bool {
  // 读取 head 和 tail 的值。
  ptrs := atomic.LoadUint64(&d.headTail)
  head, tail := d.unpack(ptrs)
  if (tail+uint32(len(d.vals)))&(1<<dequeueBits-1) == head { // 队列满了
    // 不能直接 tail == head，因为初始化的时候，head 和 tail 都是 0
    return false
  }
  // 取模意味着，当 head 超过 len(d.vals) 时，会从头开始。也就是一个环。
  slot := &d.vals[head&uint32(len(d.vals)-1)] // 获取 head 对应的槽位。
  // push 只有当前协程能 push，所以不需要加锁。
  // 但是 popTail 可能会在另一个协程中执行，所以需要判断当前的槽位是否被 popTail 释放了。
  // 因为 popTail 的操作是先 cas 修改 headTail，然后再获取 slot 的值，最后才将 slot 置 0 的。
  // 如果修改了 headTail 之后还没有来得及将 slot 置 0，那么这里就会判断出槽位还没有被释放。
  typ := atomic.LoadPointer(&slot.typ) // 获取槽位的类型
  if typ != nil {                      // 槽位不为空
    // 队列依然是满的
    return false
  }
  // 如果 typ 已经是 nil，那么这里后续的操作是安全的。
  if val == nil { // put 进来的值是 nil，使用 dequeueNil 代替
    val = dequeueNil(nil)
  }
  // 将 val 赋值给槽位
  *(*any)(unsafe.Pointer(slot)) = val
  // 增加 head。为什么是 1<<dequeueBits 呢？
  // 因为 head 是高 32 位，所以要左移 32 位
  // 本质上是：head = head + 1
  atomic.AddUint64(&d.headTail, 1<<dequeueBits)
  return true
}

// popHead 会从链表头部 pop 出一个元素。
// 返回值：
// 1. any：pop 出的元素。
// 2. bool：是否成功 pop 出元素。
func (c *poolChain) popHead() (any, bool) {
  d := c.head
  // d == nil 的情况：
  // 1. 链表为空。
  // 2. 链表只有一个元素，且这个元素已经 pop 完了。（被其他协程 pop 了）
  for d != nil {
    // 这是因为，在我们拿到 d 之后，还没来得及 pop 的话，其他协程可能已经 pop 了。
    // 所以需要 for 循环。典型的无锁编程。
    //
    // poolQueue 还没空的时候可以成功 pop，popHead 会返回 true。
    if val, ok := d.popHead(); ok {
      return val, ok
    }
    // 之前的 dequeue 中可能仍有未消费的元素，因此尝试后退。
    d = loadPoolChainElt(&d.prev) // 获取下一个 poolChainElt
  }
  return nil, false
}

// popHead 删除并返回队列头部的元素。
// 如果队列为空，则返回 false。
// 它只能由单个生产者调用。（也就是当前 goroutine 绑定的 P）
func (d *poolDequeue) popHead() (any, bool) {
  // slot 用来保存从队列头部取出的值
  var slot *eface
  for { // 获取不到槽会继续循环，直到获取到槽或者发现队列为空为止。
    ptrs := atomic.LoadUint64(&d.headTail)
    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) {
      // 成功获取到槽
      slot = &d.vals[head&uint32(len(d.vals)-1)]
      break
    }
  }
  // 成功获取到 slot，将 slot 的值取出来
  // head - 1 了，说明这个槽是可以被安全使用的，所以不需要加锁。
  // 因为 popTail 不会影响到 head，所以不会影响到这里。
  // 另外，pushHead 也没有影响，因为在实际使用中，只有一个协程会 pushHead。
  val := *(*any)(unsafe.Pointer(slot))
  if val == dequeueNil(nil) {
    val = nils
  }
  *slot = eface{} // 将 slot 置 0
  return val, true
}

// 从队列尾取出一个元素
func (c *poolChain) popTail() (any, bool) {
  // 获取链表尾部的 poolChainElt
  // 如果链表为空，返回 nil，false
  d := loadPoolChainElt(&c.tail)
  if d == nil {
    return nil, false
  }
  for {
    // 在我们 popTail 之前获取 next 指针很重要。
    // 一般来说，d 可能暂时为空，但如果 next 在 pop 之前为非 nil，
    // 并且 pop 失败，则 d 永久为空，这是唯一可以安全地将 d 从链中删除的条件。
    //
    // 解析：next 非 nil，但是 pop 失败：d 肯定是空的了，这个时候我们可以安全地将 d 从链表中删除。
    d2 := loadPoolChainElt(&d.next)
    // poolQueue 还没空的时候可以成功 pop，popTail 会返回 true。
    if val, ok := d.popTail(); ok {
      return val, ok
    }
    // 队列已经空了
    if d2 == nil {
      // d 是唯一的 dequeue。它现在是空的，但以后可能会有新的元素 push 进来。
      return nil, false
    }
    // 链表的尾部已经被消费完了，所以转到下一个 dequeue。
    // 尝试从链表中删除它，这样下一次 pop 就不必再次查看空的 dequeue。
    // （本质：移除空的 tail 元素）
    //
    // 开始处理 d2，d2 是 d 的下一个 dequeue。（开始尝试从 d2 中 pop）
    // cas：c.tail 由 d 变为 d2。
    // 如果 cas 成功，说明 d2 是最新的 tail，d 可以被移除。
    // d2 的 prev 指针设置为 nil，这样 gc 可以回收 d。（d2 没有下一个元素了）
    //
    // c.tail(d) 指向下一个 poolChainElt
    // 同时下一个 poolChainElt 的 prev 指针(d)设置为 nil。
    if atomic.CompareAndSwapPointer((*unsafe.Pointer)(unsafe.Pointer(&c.tail)), unsafe.Pointer(d), unsafe.Pointer(d2)) {
      // 我们赢得了竞争。清除 prev 指针，以便垃圾收集器可以收集空的 dequeue，
      // 以便 popHead 的时候不做多余的查找操作。
      storePoolChainElt(&d2.prev, nil)
    }
    // d 指向 d2，继续处理下一个 dequeue
    d = d2
  }
}

// popHead 和 popTail 都有取值，然后将槽置空的过程，但是它们的实现是不一样的。
// 在 popHead 中，是直接将槽的值设置为 eface{}，而在 popTail 中，
// 先将 val 设置为 nil，然后将 typ 通过原子操作设置为 nil。
// 这样在 pushHead 的时候就可以安全操作了，只要先使用原子操作判断 typ 是否为 nil 就可以了。
// popTail removes and returns the element at the tail of the queue.
// It returns false if the queue is empty. It may be called by any
// number of consumers.
//
// popTail 删除并返回队列尾部的元素。
// 如果队列为空，则返回 false。
// 它可以被任意数量的消费者调用。（如何保证并发安全？原子操作）
func (d *poolDequeue) popTail() (any, bool) {
  // slot 用来保存从队列尾取出来的值
  var slot *eface
  // 获取队列尾部的值
  for {
    ptrs := atomic.LoadUint64(&d.headTail)
    head, tail := d.unpack(ptrs)
    if tail == head {
      // Queue is empty.
      // 队列为空，直接返回
      return nil, false
    }
    // Confirm head and tail (for our speculative check
    // above) and increment tail. If this succeeds, then
    // we own the slot at tail.
    //
    // 确认 head 和 tail（对于我们上面的推测性检查）并增加 tail。
    // 如果成功，那么我们就拥有 tail 的插槽。
    ptrs2 := d.pack(head, tail+1) // 新的 headTail
    // 如果返回 false，说明从 Load 到 CompareAndSwap 期间，有其他 goroutine 修改了 headTail。
    // 则需要重新 Load，再次尝试（再次执行 for 循环）。
    if atomic.CompareAndSwapUint64(&d.headTail, ptrs, ptrs2) {
      // Success.
      slot = &d.vals[tail&uint32(len(d.vals)-1)]
      break
    }
  }
  // 成功获取到 slot，将 slot 的值取出来
  // 问题来了：
  // 在这里 cas 成功的时候，这个 slot 实际上可能是还没有释放的，在这个时候，pushHead 其实不能写入到这个 slot 中。
  // 因此，我们可以在 pushHead 的代码中看到，会先判断 slot.typ 是否为 nil，如果不为 nil，说明 slot 还没有被释放，那么就直接 return 了。
  // 这种情况发生在 poolDequeue 满了的时候。
  // We now own slot.
  val := *(*any)(unsafe.Pointer(slot))
  if val == dequeueNil(nil) { // 这是什么情况？非空，但是值等于 dequeueNil(nil) ？
    val = nil
  }
  // 取出值之后，将 slot 置 0。
  // 在 poolDequeue 中，值是允许为 nil 的，但是 pool 的 Put 中判断值为 nil 的时候就直接 return 了。
  // 告诉 pushHead 我们已经操作完这个插槽。
  // 将插槽归零也很重要，这样我们就不会留下可能使该对象比必要时间更长的引用。
  //
  // 我们首先写入 val，然后通过原子写入 typ 来发布我们已完成此插槽。
  slot.val = nil
  atomic.StorePointer(&slot.typ, nil) // 为什么要用原子操作？因为 pushHead 也会读取这个值，所以需要保证读取的是最新的值。
  // 此时 pushHead 可以操作这个槽了。
  return val, true
}