深入理解Golang sync.Map设计与实现

type Map struct {
    mu Mutex
    read atomic.Value // readOnly
    dirty map[interface{}]*entry
    misses int
}

// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {
    m       map[interface{}]*entry
    amended bool
}

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    // 1. 先查询只读的原子状态
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    // 2. 不存在，且amended为true，进入慢路径
    if !ok && read.amended {
        // 2.1 获取互斥锁
        m.mu.Lock()
        // 2.2 再次查询只读的原子状态，存在获取互斥锁期间read状态被更新的情况
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        // 2.3 仍然不存在，查询dirty
        if !ok && read.amended {
            e, ok = m.dirty[key]
            // 2.4 将统计数据累加，达到条件时，将dirty提升为read
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok {
        return nil, false
    }
    // 返回存储的数据
    return e.load()
}

func (m *Map) missLocked() {
     m.misses++
     if m.misses < len(m.dirty) {
         return
     }
     m.read.Store(readOnly{m: m.dirty})
     m.dirty = nil
     m.misses = 0
}

type entry struct {
     p unsafe.Pointer // *interface{}
}
func (e *entry) load() (value interface{}, ok bool) {
     p := atomic.LoadPointer(&e.p)

     if p == nil || p == expunged {
        return nil, false
     }
     return *(*interface{})(p), true
}

func (m *Map) Store(key, value interface{}) {
     // 1. 更新已存在的非擦除态对象
     // 使用CAS原子操作，避免加锁
     read, _ := m.read.Load().(readOnly)
     if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
     }

     // 2. 加锁
     m.mu.Lock()
     read, _ = m.read.Load().(readOnly)
     if e, ok := read.m[key]; ok {
         // 2.1.1 更新已存在的擦除态对象，先更新它的状态为nil，
         // 并将它添加到dirty中
         if e.unexpungeLocked() {
            // The entry was previously expunged, which implies that there is a
            // non-nil dirty map and this entry is not in it.
            m.dirty[key] = e
         }
         // 2.1.2 将nil更新为为new_value
         e.storeLocked(&value)
    } else if e, ok := m.dirty[key]; ok {
         // 2.2 更新存在与dirty中对象，将它的值更新为new_value
         e.storeLocked(&value)
    } else {
         // 2.3.1 添加一个新对象，先更新read.amended，表示dirty中存在
         // read不含有得key
         if !read.amended {
              m.dirtyLocked()
              m.read.Store(readOnly{m: read.m, amended: true})
         }
         // 2.3.2 将key对应的值存入dirty
         m.dirty[key] = newEntry(value)
     }
     m.mu.Unlock()
}

// 将entry中元素的状态由expunged修改为nil
func (e *entry) unexpungeLocked() (wasExpunged bool) {
     return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}

func (m *Map) dirtyLocked() {
     if m.dirty != nil {
        return
     }

      // 当dirty提升为read后，dirty会被置为nil
      // 因此当未来向dirty中添加元素时，需要先构建新dirty的状态
      // 因为dirty要包含所有有效的key元素，所以新构建dirty状态时，
      // 将read中存储有效值的数据也存储至dirty中
      read, _ := m.read.Load().(readOnly)
      m.dirty = make(map[interface{}]*entry, len(read.m))
      for k, e := range read.m {
           // 将包含有效值的元素存入dirty
           if !e.tryExpungeLocked() {
               m.dirty[k] = e
           }
      }
}

// 将entry中状态为nil的元素置为expunged，表示它已被逻辑删除
// 当返回值为true时，表示元素已被删除，否则，元素为一个有效值
func (e *entry) tryExpungeLocked() (isExpunged bool) {
      p := atomic.LoadPointer(&e.p)
      for p == nil {
          if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
              return true
          }
          p = atomic.LoadPointer(&e.p)
      }
      return p == expunged
}

// Delete deletes the value for a key.
func (m *Map) Delete(key interface{}) {
     m.LoadAndDelete(key)
}

func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
      //1. 使用原子操作查询read状态
      read, _ := m.read.Load().(readOnly)
      e, ok := read.m[key]
      if !ok && read.amended {
           //2. 未查到，加锁查询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)
                //3. 累计加锁的数量，触发状态提升
                m.missLocked()
           }
           m.mu.Unlock()
      }
      // 4. 查询到key，将key的值置为nil，进行逻辑上删除
     if ok {
          return e.delete()
     }
     return nil, false
}

// 将元素从逻辑上进行删除，将状态置为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
         }
      }
}

func (m *Map) Range(f func(key, value interface{}) bool) {
      read, _ := m.read.Load().(readOnly)
      // 1. dirty中包含read不存在的状态，
      // 将dirty提升为read.
      if read.amended {
          m.mu.Lock()
          read, _ = m.read.Load().(readOnly)
          if read.amended {
              read = readOnly{m: m.dirty}
              m.read.Store(read)
              m.dirty = nil
              m.misses = 0
          }
          m.mu.Unlock()
       }

       // 2. 遍历read，当动作函数返回false时，退出遍历。
       // 由于遍历过程中可能存在map的并发修改操作，因此当遍历该entry时，
       // 实际存储的值被删除时，则不再遍历.
       for k, e := range read.m {
           v, ok := e.load()
           if !ok {
               continue
           }
           if !f(k, v) {
                 break
           }
       }   
}

func (e *entry) load() (value interface{}, ok bool) {
      p := atomic.LoadPointer(&e.p)
      if p == nil || p == expunged {
          return nil, false
      }
      return *(*interface{})(p), true
}

func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) {
      // Avoid locking if it's a clean hit.
      read, _ := m.read.Load().(readOnly)
      if e, ok := read.m[key]; ok {
            actual, loaded, ok := e.tryLoadOrStore(value)
            if ok {
                return actual, loaded
            }
      }

      m.mu.Lock()
      read, _ = m.read.Load().(readOnly)
      if e, ok := read.m[key]; ok {
          if e.unexpungeLocked() {
              m.dirty[key] = e
          }
          actual, loaded, _ = e.tryLoadOrStore(value)
      } else if e, ok := m.dirty[key]; ok {
            actual, loaded, _ = e.tryLoadOrStore(value)
            m.missLocked()
      } else {
            if !read.amended {
                // We're adding the first new key to the dirty map.
                // Make sure it is allocated and mark the read-only map as incomplete.
                m.dirtyLocked()
                m.read.Store(readOnly{m: read.m, amended: true})
             }
             m.dirty[key] = newEntry(value)
             actual, loaded = value, false
      }
      m.mu.Unlock()

      return actual, loaded
}

func (e *entry) tryLoadOrStore(i interface{}) (actual interface{}, loaded, ok bool) {
      p := atomic.LoadPointer(&e.p)
      if p == expunged {
           return nil, false, false
      }
      if p != nil {
           return *(*interface{})(p), true, true
      }

      ic := i
      for {
            if atomic.CompareAndSwapPointer(&e.p, nil, unsafe.Pointer(&ic)) {
                  return i, false, true
            }
            p = atomic.LoadPointer(&e.p)
            if p == expunged {
                 return nil, false, false
            }
            if p != nil {
                   return *(*interface{})(p), true, true
            }
      }
}