在 rpi2 上實作 spinlock

[descent (「雄辯是銀，沉默是金」)]

process 同步機制有 spinlock, mutex, semaphore, 我的學習方式是簡化再簡化, 然後
用程式碼實作他們, 否則我只會有「名詞」上的理解, 而不會真的理解。有了 spinlock
就有了基本的 process 同步機制。

以下的參考資料幫助我完成這個實作:

Linux核同步机制之（一）：原子操作 ( http://goo.gl/Z9PJOC )
Linux核同步机制之（四）：spin lock ( http://goo.gl/AHTbku )
Linux解:基于最新的Linux4.0核 ( http://goo.gl/D9Ni5h ) p164 代碼清單 7.1, 以及
第七章, 這部份把容易搞混的 memory barrier, compiler/cpu 的亂序執行做了一個很好
的說明。


由於要分解這些功能並簡化他們, 通常我會設計簡單的測試方式並輔以實作的小程式來理
解他們, spinlock 的測試讓我大傷腦筋, 之前的想法是要先實作 process switch, 才能
測試 spinlock, 我也的確做了某些成果, 不過在我愈來愈會設計這些小實驗後, 已經變
得很擅長這件事情。我想到一個更好的方法, 不用先實作 process switch, 我在 rpi2
寫個 pthread 程式, 然後呼叫我自己寫的 my_spin_lock, my_spin_unlock 取代
pthread_spin_lock, pthread_spin_unlock, 若行為一樣, 就代表我成功了。


spinlock.c
  1 #include "spinlock.h"
  2
  3 #include <stdio.h>
  4
 37
 38 void spinlock_init(Spinlock *spinlock)
 39 {
 40   spinlock->val_ = 0;
 41 }
 42
 43 int spin_lock(Spinlock *spinlock)
 44 {
 77 #if 0
 78 lock_mutex:
 79   if(spinlock->val_ == 1)
 80     goto lock_mutex;
 81   else
 82     spinlock->val_ = 1;
 83
 84 #endif
103         unsigned long tmp;
104         int result;
105
106         __asm__ __volatile__("@ atomic_add\n"
107 "1:     ldrex   %0, [%3]\n"
108 "       cmp     %0, #1\n"
109        "beq 1b\n"
110        "mov %0, #1\n"
111 "       strex   %1, %0, [%3]\n"
112 "       teq     %1, #0\n"
113 "       bne     1b"
114         : "=&r" (result), "=&r" (tmp), "+Qo"(spinlock->val_)
115         : "r" (&spinlock->val_)
116         : "cc");
118 }
119
120 int spin_unlock(Spinlock *spinlock)
121 {
122   spinlock->val_ = 0;
123 }
124
125 #ifdef TEST
126 #include <pthread.h>
127 #include <signal.h>
128
129 FILE *fs;
130 Spinlock sp;
131 pthread_spinlock_t spinlock;
132
133 int run=1;
134
135 void* write_file_1(void *p)
136 {
137   int time=0;
138   pthread_t tid = pthread_self();
139
140   while(run)
141   {
142 #ifdef PTHREAD_FUNC
143     pthread_spin_lock(&spinlock);
144 #else
145     spin_lock(&sp);
146 #endif
147     //printf("111\n");
148     fprintf(fs, "%d ## thread 1 ## %d\n", time, tid);
149     fprintf(fs, "%d ## thread 11\n", time);
150     fprintf(fs, "%d ## thread 111\n", time);
151 #if 1
152 #ifdef PTHREAD_FUNC
153     pthread_spin_unlock(&spinlock);
154 #else
155     spin_unlock(&sp);
156 #endif
157 #endif
158     ++time;
159   }
160   // printf("thread 1 exit\n");
161 }
162
163 void* write_file_2(void *p)
164 {
165   int time = 0;
166   pthread_t tid = pthread_self();
167
168   while(run)
169   {
170 #ifdef PTHREAD_FUNC
171     pthread_spin_lock(&spinlock);
172 #else
173     spin_lock(&sp);
174 #endif
175     //printf("222\n");
176     fprintf(fs, "%d ## thread 2 long string 0123456789 ## %d\n", time,
tid);
177     fprintf(fs, "%d ## thread 22 long string 0123456789\n", time);
178     fprintf(fs, "%d ## thread 222 long string 0123456789\n", time);
179 #ifdef PTHREAD_FUNC
180     pthread_spin_unlock(&spinlock);
181 #else
182     spin_unlock(&sp);
183 #endif
184     ++time;
185   }
186   // printf("thread 2 exit\n");
187 }
188
189 void* write_file_3(void *p)
190 {
191   int time = 0;
192   pthread_t tid = pthread_self();
193   int i;
194
195   while(run)
196   {
197 #ifdef PTHREAD_FUNC
198     pthread_spin_lock(&spinlock);
199 #else
200     spin_lock(&sp);
201 #endif
202     fprintf(fs, "%d ## thread 3 long string
ABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()~ ## %d\n", time, tid);
203     fprintf(fs, "%d ## thread 33 long string
ABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()~\n", time);
204     fprintf(fs, "%d ## thread 333 long string
ABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()~\n", time);
205 #ifdef PTHREAD_FUNC
206     pthread_spin_unlock(&spinlock);
207 #else
208     spin_unlock(&sp);
209 #endif
210     ++time;
211   }
212   // printf("thread 2 exit\n");
213 }
214
215 static void* sig_thread (void *arg)
216 {
217   sigset_t *set = arg;
218   int s, sig;
219
220   printf("sig thread pid: %d\n", getpid());
221
222   for (;;)
223   {
224     s = sigwait (set, &sig);
225     if (s == 0)
226     {
227       printf ("Signal handling thread got signal %d\n", sig);
228       if (sig == SIGINT)
229       {
230         run = 0;
231         //break;
232       }
233     }
234   }
235 }
236
237 int ret1, ret2, ret3;
238
239 int main(int argc, char *argv[])
240 {
241   pthread_t thread0, thread1, thread2, thread;
242   sigset_t set;
243
244 #ifdef PTHREAD_FUNC
245   pthread_spin_init(&spinlock, 0);
246   printf("init pthread spinlock\n");
247 #else
248   spinlock_init(&sp);
249   printf("init my spinlock\n");
250 #endif
251
252   sigemptyset (&set);
253   sigaddset (&set, SIGQUIT);
254   sigaddset (&set, SIGINT);
255   int s = pthread_sigmask (SIG_BLOCK, &set, NULL);
256   if (s != 0)
257   {
258     perror("pthread_sigmask");
259     return -1;
260   }
261
262
263   printf("open %s to write\n", FN);
264   fs = fopen(FN, "w");
265   if (fs == NULL)
266   {
267     perror("open fail");
268     return -1;
269   }
270
271   pthread_create (&thread, NULL, &sig_thread, (void *) &set);
272   pthread_create(&thread0, NULL, write_file_1, NULL);
273   pthread_create(&thread1, NULL, write_file_2, NULL);
274   pthread_create(&thread2, NULL, write_file_3, NULL);
275
276   pthread_join(thread0, (void **)&ret1);
277   pthread_join(thread1, (void **)&ret2);
278   pthread_join(thread2, (void **)&ret3);
279
280   fclose(fs);
281   printf("test end\n");
282
283   return 0;
284 }
285 #endif



spinlock.c L77 ~ 84 是 c 版本的演算法, 為什麼不能用這個版本, 因為需要 atomic
操作, 這大家都知道, 不多說了; 困難的是怎麼實作 atomic, spinlock.c L103 ~ 116
是我參考 linux 3.10.37 arch/arm/include/asm/atomic.h atomic_add 改出來的 (因為
我自己寫的都有問題 ... 冏), 這 inline assembly 實在太難, 我沒能完全看懂,
ldrex/strex 可以在 armv6, cortex armv7-A 上使用, 我在 rpi2 執行這個測試, 這個
版本應該也可以在 cortex m3 上執行, 這才是我真正的目的。

x86 可參考 arch/x86/include/asm/atomic.h 來實作。


arch/arm/include/asm/atomic.h
  1 /*
  2  *  arch/arm/include/asm/atomic.h
  3  *
  4  *  Copyright (C) 1996 Russell King.
  5  *  Copyright (C) 2002 Deep Blue Solutions Ltd.
  6  *
  7  * This program is free software; you can redistribute it and/or modify
  8  * it under the terms of the GNU General Public License version 2 as
  9  * published by the Free Software Foundation.
 10  */
 11 #ifndef __ASM_ARM_ATOMIC_H
 12 #define __ASM_ARM_ATOMIC_H
 13
 14 #include <linux/compiler.h>
 15 #include <linux/types.h>
 16 #include <linux/irqflags.h>
 17 #include <asm/barrier.h>
 18 #include <asm/cmpxchg.h>
 19
 20 #define ATOMIC_INIT(i) { (i) }
 21
 22 #ifdef __KERNEL__
 23
 24 /*
 25  * On ARM, ordinary assignment (str instruction) doesn't clear the local
 26  * strex/ldrex monitor on some implementations. The reason we can use it
for
 27  * atomic_set() is the clrex or dummy strex done on every exception
return.
 28  */
 29 #define atomic_read(v) (*(volatile int *)&(v)->counter)
 30 #define atomic_set(v,i) (((v)->counter) = (i))
 31
 32 #if __LINUX_ARM_ARCH__ >= 6
 33
 34 /*
 35  * ARMv6 UP and SMP safe atomic ops.  We use load exclusive and
 36  * store exclusive to ensure that these are atomic.  We may loop
 37  * to ensure that the update happens.
 38  */
 39 static inline void atomic_add(int i, atomic_t *v)
 40 {
 41  unsigned long tmp;
 42  int result;
 43
 44  __asm__ __volatile__("@ atomic_add\n"
 45 "1: ldrex %0, [%3]\n"
 46 " add %0, %0, %4\n"
 47 " strex %1, %0, [%3]\n"
 48 " teq %1, #0\n"
 49 " bne 1b"
 50  : "=&r" (result), "=&r" (tmp), "+Qo" (v->counter)
 51  : "r" (&v->counter), "Ir" (i)
 52  : "cc");
 53 }



程式有 3 個 thread 在寫同一個檔案 /tmp/xyz1, 按下 ctrl-c 會收到 SIGINT, 程式會
正確的處理這個 SIGINT 然後結束整個程式 (這並不容易, 請參考《thread 和 signal
( http://goo.gl/9dKfjj )》)。spinlock test result 為失敗與成功的內容。一開始的
實作並不正確, 所以我特別用了 pthread_spin_lock, pthread_spin_unlock 來測試, 發
現使用 pthread_spin_lock/pthread_spin_unlock 就會得到正確的結果。


spinlock test result
失敗:
237 ## thread 1 ## 1985418336
237 ## thread 3 long string ABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()~ ##
1968641120
206 ## thread 2 long string 0123456789 ## 1977029728

成功:
6 ## thread 1 ## 1985877088
6 ## thread 11
6 ## thread 111
0 ## thread 2 long string 0123456789 ## 1977488480
0 ## thread 22 long string 0123456789
0 ## thread 222 long string 0123456789
7 ## thread 1 ## 1985877088
7 ## thread 11
7 ## thread 111
1 ## thread 2 long string 0123456789 ## 1977488480
1 ## thread 22 long string 0123456789
1 ## thread 222 long string 0123456789



每個 thread 應該以 3 行為輸出單位, 若是被混在一起, 表示雖然有某個 thread 取得
了 spinlock, 但其他的 thread 並沒有 busy loop, 而是也取得了同樣的 spinlock 並
進入了 critical section, 造成了失敗的結果。

check_result.c 則是用來檢查 /tmp/xyz1 是否是正確。整個測試在 rpi2 上完成。

不知道是不是還需要 memory barrier, dsb, isb, dmb 這些指令。驗證 spinlock
function 是否正確非常困難, 我也不確定這個版本一定是對的, 因為只要有一個失敗案
例, 這個 spinlock 實作就不正確了, 若用上了有 bug 的 spinlock function, 那程式
會很難除錯, 若核4 有這樣的程式碼應該會嚇死不少程式人。

spinlock 做出來了, 那 mutex 呢? 把 spinlock.c L109 改成讓出 cpu 的程式碼就可以
了, 這就是俗稱的去「睡覺」。你說要怎麼做? 這在 process switch 的階段就已經會了
, 所以你得搞懂那個才行。

實作完 spinlock 後還有使用 spinlock 的議題, 非常的複雜, 感覺起來 mutex 是比較
好的, 那為什麼還要設計 spinlock, 又中斷部份的程式碼為什麼要 spinlock 而不用
mutex 呢?

source code:
https://github.com/descent/progs/tree/master/spinlock ( https://goo.gl/DMYSMX
)

ref:

理解 Memory barrier (存屏障) ( http://goo.gl/EmxZYv )
Memory Barrier in Lock API ( http://goo.gl/xjrYyl )
Linux x86 spinlock 實現之分析 ( http://goo.gl/u1Csis )
分析Linux中Spinlock在ARM及X86平台上的 ( http://goo.gl/g0tUQB )


DMB, DSB, ISB:


http://www.07net01.com/linux/ARM_Cortex_M3_xuexibiji_4_5__14436_1347159341.html
( http://goo.gl/AbQwn0 )

http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0489c/CIHGHHIE.html
( http://goo.gl/ZyZNWD )

// 本文使用 Blog2BBS 自動將Blog文章轉成縮址的BBS純文字 http://goo.gl/TZ4E17 //

blog 版本:
http://descent-incoming.blogspot.tw/2015/11/spinlock-on-raspberry-pi-2.html

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.246.154
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1447594047.A.9E1.html
推 winken2004: 推
推 laladeer: 推
推 ho83leo: 推