天天看點
傳回

論文筆記《Understanding_Real-World_Concurrency_Bugs_in_Go》論文筆記《Understanding_Real-World_Concurrency_Bugs_in_Go》

論文筆記《Understanding_Real-World_Concurrency_Bugs_in_Go》

論文會議：ASPLOS

年份：2019

參考文獻：Tu T, Liu X, Song L, et al. Understanding real-world concurrency bugs in Go[C]//Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. 2019: 865-878.

該部落格中文字部分為個人總結，圖檔和代碼部分均基本出自文獻，如有侵權，請指出

1. 論文概述

該論文主要針對 Go 語言中的并發程式設計，對開源市場上的 6 款主流程式包括 Docker、Kubernetes 和 gRPC 等做了 bug 分析和重制，并分析了他們的 bug fix commit。通過對這些 bug 進行分類和源碼分析與修複，得出未來Go 語言可進行工作的方向和需要注意的程式設計點。

2. 重點

2.1 bug 分類

論文将 bug 從兩個正交次元進行分析：

  • bug 起因
    • 共享記憶體（鎖）
    • 消息傳遞（channel）
  • bug 行為
    • 阻塞bug（死鎖）
    • 非阻塞Bug（資料競态）

2.2 bug 分析名額

論文裡提出 統計名額

l i f t ( A , B ) = P ( A B ) P ( A ) P ( B ) lift(A,B) = \frac{P(AB)}{P(A)P(B)} lift(A,B)=P(A)P(B)P(AB)​

A 指 bug 的起因類别

B 指修複 bug 政策類别

P(AB)指該 bug 是因 A 引起且被 B 修複的可能性

為1時則表示 AB 無關，大于 1 時則表示正相關

3. 并發程式設計 分類

為了更好地分析，也總結了Go語言對兩種并發程式設計的支援度：

  • 共享記憶體
    • lock/unlock (Mutex)
    • read/write lock (RWMutex)
    • 條件變量 (Cond)
    • 原子操作 (atomic)
    • WaitGroup

Go 語言的

RWMutex

與 C 語言的

pthread_rwlock_t

不同，寫鎖比讀鎖具有更高的優先級

  • 消息傳遞
    • channel: buffered/unbuffered
    • select: random
    • context: 跨goroutine攜帶特定于請求的資料或中繼資料

向

nil channel

發送和接收資料都将永久阻塞，但是向已關閉的

channel

發送資料和再次關閉将引發

panic

4. 對 Go 内部實作的分析

4.1 死鎖檢測器

go 内置的 死鎖檢測器 隻能檢測很少的并發 bug，為了占用最少的系統資源時間

檢測能力弱的原因有二：

  1. 當有少數幾個 goroutine 在跑時并不會得出阻塞的結果
  2. 僅檢測 goroutine 是否因 go 并發原語而阻塞，而不檢測其是否正在等待系統資源

4.2 資料競态檢測器

go run -race xxx.go

：用于檢測資料競态

在程式執行期間，競争檢測器為每個記憶體對象最多建立四個指向，以存儲對象的曆史通路。 它将每個新通路與存儲的影子值進行比較，以檢測可能的競争。

當其資料競态檢測器隻能檢測小部分的非阻塞 bug。原因有三：

  1. 并非所有非阻塞bug都是資料競争。競态檢測器并非旨在檢測其他類型
  2. 底層先發生算法的有效性取決于并發goroutine的交織
  3. 每個存儲對象隻有四個拷貝指向，檢測器無法保留很長的曆史記錄，并且可能會丢失資料競争

4.3 并發原語

Go的一些并發原語違反了以往的規則，故這也是造成 bug 的原因之一

急需新技術去和消息傳遞導緻的非阻塞bug 做鬥争和檢測

5. 源碼 bug 分析

本人對其中的主流軟體所産生的bug頗感興趣。

bug 1: 因

channel

 引起的阻塞 bug

作為示範，其介紹了 Kubernetes 中的一個消息傳遞的阻塞 Bug，僞代碼如下：

func finishReq(timeout time.Duration) r ob {
  // ch := make(chan ob) bug
  ch := make(chan ob, 1) // fix
  go func() {
    result := fn()
    ch <- result // block
  }
  select {
  	case result = <- ch:
    	return result
    case <- time.After(timeout):
    	return nil
  }
}

finishReq

函數使用匿名函數建立了一個子

goroutine

；子

goroutine

執行函數

fn()

并通過

channel

發送結果給父

goroutine

；而子

goroutine

将會因非緩存

channel

被阻塞，同時，父

goroutine

也會在

select

中被阻塞直到子協程發送

result

給

channel

或

timeout

發生。若

timeout

發生或兩者都可選，父函數将可能傳回

nil

，并且将沒有其他

goroutine

能接收

result

，子

goroutine

将永久阻塞，造成

goroutine

洩露。

解決辦法是将無緩沖

channel

聲明為有一個緩沖的

channel

這樣就可以保證子

goroutine

一定能發送

result

到

channel

了，即不會被阻塞

bug 2：錯用

WaitGroup

 

var group sync.WaitGroup
group.Add(len(pm.plugins))
for _,p := range pm.plugins {
  go func(p *plugin) {
    defer group.Done()
  }(p)
  // group.Wait() bug
}
group.Wait() // fix

Wait()

在循環内，該循環将會被永久阻塞，bug 修複是将

Wait()

移到循環體之外，讓

goroutine

全部建構完，確定

Done()

函數能全部執行完

bug 3：因

context

 引起的阻塞 bug 

// —————— bug ——————
htcx, hcancel := context.WithCancel(ctx)
if timeout > 0 {
  hctx, hcancel = context.WithTimeout(ctx, timeout)
}

// —————— fix ——————
var htcx context.Context
var hcancel context.CancelFunc
if timeout > 0 {
  hctx, hcancel = context.WithTimeout(ctx, timeout)
} else {
  hctx, hcancel = context.WithCancel(ctx)
}

在 bug 的版本中，針對

context

初始化了兩次，一次是

WithCancel

，一次是

WitchTimeout

。而在 Go 1.14 源碼中，兩次都會在源碼中，進行

goroutine

的建立，建立的源碼如下：

// propagateCancel arranges for child to be canceled when parent is.
func propagateCancel(parent Context, child canceler) {
	...

	if p, ok := parentCancelCtx(parent); ok {
		...
	} else {
		atomic.AddInt32(&goroutines, +1)
    // 建立了 goroutine 并且會阻塞直到父子協程 done
		go func() {
			select {
			case <-parent.Done():
				child.cancel(false, parent.Err())
			case <-child.Done():
			}
		}()
	}
}

這将導緻沒有辦法去發送消息把

WithCancel

建立的

goroutine

關閉掉。

解決辦法是避免建立額外的

context

，初始化隻一次就夠，不要改變指向

bug 4：因

channel

 和

lock

 的混合使用導緻的阻塞 bug 

func goroutine1() {
  m.Lock()
  // ch <- request bug-block
  // fix
  select {
  	case ch <- request:
    default:
  }
  m.UnLock()
}

func goroutine2() {
  for {
    m.Lock() // block
    m.UnLock()
    request <- ch
  }
}

在 bug 版本中，當

goroutine1

執行到

ch <- request

的時候，其将阻塞；當

goroutine2

執行到

m.Lock()

的時候，也會阻塞，這就導緻了循環等待而死鎖。

解決辦法之一是使用

select

加

default

使

goroutine1

釋放鎖資源

bug5：因匿名函數導緻的資料競态 

for i := 17;i <= 21;i++ {
  // bug
  go func() {
    apiVersion := fmt.Sprintf("v1.%d", i)
    ...
  }()
  // fix
  go func(i int) {
    apiVersion := fmt.Sprintf("v1.%d", i)
    ...
  }(i)
}

在

go

關鍵字後進行協程建立時，建立需要一定資源和運作時間，此時外部循環 i 已經運作到 21，在 bug 版本中，将隻能得到 1.21

bug6：因濫用

WaiGroup

 而導緻的非阻塞bug 

func (p *peer) send() {
  p.mu.Lock()
  defer p.mu.UnLock()
  switch p.status {
  case idle:
    // fix
    p.wg.Add(1)
    go func() {
    	// p.wg.Add(1) bug
    	...
    	p.wg.Done()
    }()
  case stopped:
  }
}

func(p *peer) stop() {
  p.mu.Lock()
  p.status = stopped
  p.mu.UnLock()
  p.wg.Wait()
}

在 bug 版本中，無法保證在

goroutine

中的

Add()

一定在

Wait()

前執行，有可能直接執行了

Wait()

解決辦法是将

Add()

方法從

goroutine

建立中移出，與

Wait()

處于同一級别中。

bug7：因關閉

channel

 兩次而導緻的bug 

// ———— bug ————
select {
case <- c.closed:
default:
  close(c.closed)
}

// ———— fix ————
Once.Do(func() {
  close(c.closed)
})

當有多個

goroutine

運作時，将有可能同時運作到

default

并進行多次關閉而導緻抛出

panic

解決辦法是使用

Once

進行一次關閉

bug8：因

select

 和

channel

 導緻的非阻塞 bug 

ticker := time.NewTicker()
for {
  // fix add begin
  select {
  case <- stopCh:
    return
  default:
  }
  // fix add end
  f() // heavy function
  select {
  case <- stopCh:
    return
  case <- ticker:
  }
}

在沒有添加

fix

的版本中，當執行到 select 的時候，若從

stopCh

中接收到消息的同時，

ticker

也同樣觸發了，則無法保證哪項會被選擇，如果選擇了

case2

，則

f()

将會無用功地執行了一遍

解決辦法是在

f()

之前，每次循環前去捕獲

stopCh

的信号

bug9：因

Timer

 導緻的非阻塞 bug 

// bug
timer := time.NewTimer(0)
if dur > 0 {
  timer = time.NewTimer(dur)
}
select {
case <-timer.C:
case <- ctx.Done():
  return nil
}

// fix
var timeout <-chan time.Time
if dur > 0 {
  timeout = time.NewTImer(dur).C
}
select {
case <-timeout:
case <-ctx.Done():
  return nil
}

與 bug3 類似，但是，當dur不大于0時，庫内部

goroutine

将在建立計時器後立即向

timer.C

通道發送信号，進而導緻函數過早傳回（第8行）。 解決方法是避免在第1行建立計時器。

補充

在 Go 1.14 中，若傳入

NewTimer

的整數

d <= 0

，将會抛出

panic

6. 分析總結

觀察結論1

通過分析幾款主流軟體和分析Go語言和其他語言的對比，發現

goroutine

的執行時間比 C 語言短，并且建立更為頻繁，靜态和運作時皆如此。

觀察結論2

分析幾款主流軟體源碼後發現，共享記憶體并發程式設計還是廣泛主要使用的，但消息通信也有占用一部分的代碼量

意義1

随着goroutines的大量使用和新型并發原語的出現，Go程式可能會引入更多的并發bug。

觀察結論3

與普遍認為消息傳遞不太容易出錯相反，在研究Go應用程式中，更多的阻塞錯誤是由錯誤的消息傳遞引起的，而不是由錯誤的共享記憶體保護引起的。

觀察結論4

盡管有的錯誤是傳統并發錯誤，但也可以合理推測有的錯誤是因為 Go 的新型的内部實作方式或語義造成的 bug

由共享記憶體同步引起的大多數阻塞錯誤都具有與傳統語言相同的原因和修複。 但是，由于Go對現有原語的新實作或新的程式設計語義，其中一些 bug 又與傳統語言有所不同。

觀察結論5

由消息傳遞引起的所有阻塞錯誤都與Go的新文法（例如 channel）有關。 它們可能很難檢測到，尤其是當消息傳遞操作與其他同步機制混用時。

意義2

與通常的看法相反，消息傳遞比共享記憶體可能導緻更多的阻塞錯誤。 論文呼籲

注意消息傳遞程式設計中的潛在危險，并提出該領域中的錯誤檢測的研究問題。

觀察結論6

論文研究中的大多數阻塞錯誤（傳統的共享記憶體錯誤和消息傳遞錯誤）都可以通過簡單的解決方案來解決，并且許多修複都與錯誤原因直接相關。

意義3

Go阻塞bug産生的原因和修複之間的高度相關性及其修複的簡單性表明，有希望開發出全自動或半自動化的工具來修複Go的阻塞bug。

意義4

簡單的運作時死鎖檢測器對檢測 Go阻塞bug 無效。 未來的研究應側重于建構新穎的阻止錯誤檢測技術，例如，結合使用靜态和動态阻塞模式檢測。

觀察結論7

大約三分之二的 共享記憶體 非阻塞bug 是由傳統原因引起的。 Go的新多線程語義和新庫貢獻了其餘的三分之一。

意義5

Go引入的用于簡化多線程程式設計的新程式設計模型和新庫本身可能是更多并發性錯誤的原因。

觀察結論8

與共享記憶體通路相比，消息傳遞引起的非阻塞bug要少得多。 通道規則以及将通道與其他特定于Go的語義和庫一起使用的複雜性是這些無阻塞bug發生的原因。

意義6

如果使用正确，則消息傳遞比共享記憶體通路不太容易發生非阻塞bug。 但是，消息傳遞的複雜設計可能會導緻在與其他特定于語言的功能結合時很難發現這些錯誤。

觀察結論9

傳統的共享記憶體同步技術仍然是Go中非阻塞錯誤的主要修複方法，而channel不僅被廣泛用于修複與通道相關的錯誤，而且還用于修複共享記憶體的錯誤。

意義7

盡管Go程式員繼續使用傳統的共享記憶體保護機制來修複非阻塞性錯誤，但在某些情況下，他們更喜歡使用消息傳遞修複，這可能是因為他們将消息傳遞視為更安全的跨線程通信方式。

意義8

簡單的傳統資料競賽檢測器無法有效檢測所有類型的Go非阻塞錯誤。 未來的研究可以利用我們的錯誤分析來開發更具資訊性，特定于Go的非阻塞錯誤檢測器。

go 文獻 并發程式設計
上一篇: python自動化測試流程_Python+Appium實作自動化測試的使用步驟
下一篇: ADVHAT: REAL-WORLD ADVERSARIAL ATTACK ON ARCFACE FACE ID SYSTEM 筆記

繼續閱讀