深入Go：sync.Map

func main() {
    m := make(map[int]int)

    go func() {
        for i := 0; i < 100000; i += 1 {
            m[i] = i
        }
    }()
    for i := 0; i < 100000; i += 1 {
        _ = m[i]
    }
}

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
  // 如果在读map的时候检测到hashWriting flag为1（即，有协程在写该map）则panic
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
}

// expunged是初始化时随机生成的哨兵值，
// 标志该值已经从map的read中删除且不存在于dirty中。
var expunged = unsafe.Pointer(new(interface{}))

type entry struct {
    // p为指针，可指向：
  // -> nil，表示对应键值已从map的read中删除，但存在于dirty中
  // -> expunged，表示对应键值已从map中删除，但不存在于dirty中
  // -> 其他地址，指向真实数据
    p unsafe.Pointer
}

type readOnly struct {
    m       map[interface{}]*entry
    amended bool // 如果dirty包含read中不包含的entry指针时为true。
}

type Map struct {
   mu Mutex
  
   // read包含并发安全的map部分，访问它（的entries）永远不用加锁
   // 当entry需要从read删除时，并不直接删除该entry的指针e，
   // 而是将e.p置为nil。
   // 除了进行写操作且对应键的entry的e.p == expunged时，
   // （此时也不是对read加锁，而是对dirty加锁）
   // 对read中的键值进行读、写和删除都不用加锁。
   read atomic.Value // readOnly

   // dirty包括map中需要加锁读写的部分。
   // 为保证从dirty至read的更新耗时足够小，
   // 因此需要把read中从expunged状态恢复的entry加入dirty
   // （此时read仍未被加锁，是写到dirty从而对dirty加锁）。
   // 当向dirty写的时候，如果dirty为nil，
   // 则需要浅拷贝read（unplunged entries除外，详情见Store代码）
   dirty map[interface{}]*entry

   // misses是计算read更新后访问map时获取mu的计数器
   // 当misses数量超过dirty长度时，dirty会跃升为新的read并将dirty置为nil
   misses int
}

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !ok && read.amended { // 如果找不到，且dirty含有新键值
        m.mu.Lock()
        // 双重检查，避免另一协程已经将read替换为dirty
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
      // 从dirty中获取
            e, ok = m.dirty[key]
      // 增加misses计数，如果超过len(dirty)则将read替换为dirty并将dirty置为nil
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok { // 未找到对应键
        return nil, false
  }
    return e.load() // 返回真实值
}

func (m *Map) Store(key, value interface{}) {
    read, _ := m.read.Load().(readOnly)
  // tryStore：当e.p为expunged时返回false，否则存储
    if e, ok := read.m[key]; ok && e.tryStore(&value) { 
    // 这里，未加锁尝试store
    // 因为read的entry非expunged时，要么dirty为空则无需操作dirty
    // 否则该entry指针一定和dirty中对应的entry指针指向同一entry
    // 因此只需改这里就可以使dirty中值保持一致（从而也无需加锁）
        return 
    } 

    m.mu.Lock() // 否则需要加锁访问
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
        if e.unexpungeLocked() { // 此前e为expunged状态，将对应`e.p`置为nil
            // expunged状态说明此时dirty不为nil且该键不在dirty中，直接存到dirty
            m.dirty[key] = e
        }
        e.storeLocked(&value) // 然后store pointer到entry e
    } else if e, ok := m.dirty[key]; ok { // 此时为dirty中有值的状态
        e.storeLocked(&value)
    } else { // 此时为dirty中无该值的状态
        if !read.amended { // 此时为dirty中第一个值
            m.dirtyLocked() // 创建m.dirty并根据read初始化，如下
/*
func (m *Map) dirtyLocked() {
    if m.dirty != nil { // 此时m.dirty一定是nil，否则不会调用dirtyLocked
        return
    }

    read, _ := m.read.Load().(readOnly)
    m.dirty = make(map[interface{}]*entry, len(read.m))
    for k, e := range read.m { // 处理read中每个entry
        if !e.tryExpungeLocked() { // 将read中含空指针的entry变为expunged并返回true
            m.dirty[k] = e // 因此read中为expunged的entry在dirty中一定不存在对应entry
        }
    }
}*/
      // 现在有dirty了，改动amended
            m.read.Store(readOnly{m: read.m, amended: true}) 
        }
        m.dirty[key] = newEntry(value) // 在dirty中存储新值，此时该值仅在dirty中存在
    }
    m.mu.Unlock()
}

// LoadAndDelete被Delete调用，是实施删除键值的函数
func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
    read, _ := m.read.Load().(readOnly)
  e, ok := read.m[key] // 如果在read中找到，直接跳到下方e.delete()
    if !ok && read.amended { // 说明仅仅存在于dirty中
        m.mu.Lock()
        read, _ = m.read.Load().(readOnly) // 双重检查
        e, ok = read.m[key]
        if !ok && read.amended {
            e, ok = m.dirty[key]
            delete(m.dirty, key) // 在dirty中删除，此时read、dirty中都不再有该键
            m.missLocked() // 增加misses，如果需要则用dirty替换read
        }
        m.mu.Unlock()
    }
    if ok {
        return e.delete() // 如果有真实值，则将其置为nil
/*
func (e *entry) delete() (value interface{}, ok bool) {
    for {
        p := atomic.LoadPointer(&e.p)
        if p == nil || p == expunged {
            return nil, false
        }
        if atomic.CompareAndSwapPointer(&e.p, p, nil) {
            return *(*interface{})(p), true
        }
    }
} */
    }
    return nil, false
}