實作 spinlock on raspberry pi 2

這應該是我學習 os 拼圖的最後一塊了, 我已經會實作開機程式, context switch, system call, fork, exec, elf loader, 記憶體管理, mmu 設定, romfs 檔案系統, 剩下應該就是 process 的同步機制。這些主題深入下去都會花上不少時間, 我只取最簡單的實作方式, 主要觀念有完成就可以, 實作並不完美, 但由於我的簡化, 他們都變的很容易理解, 這是簡化後帶來的價值。剩下的工作便是把所有的努力組合起來, 這也是件大工程。os 當然還有其他主題, 不過我認為這樣應該對 os 有達到「略懂」的境界了。

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

由於工作時間就耗掉了我生活的不少時間, 幾乎沒有時間學習一個大主題, 我的 compiler 學習之路只好緩一點 (在 os 上花了很大時間, 想換換口味), 偷空學習這些被我化繁為簡的零星主題。

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

Linux内核同步机制之（一）：原子操作
Linux内核同步机制之（四）：spin lock
Linux设备驱动开发详解:基于最新的Linux4.0内核 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/x86/include/asm/spinlock.h 的實作。

3.10.27/arch/arm/include/asm/spinlock.h
74 static inline void arch_spin_lock(arch_spinlock_t *lock)
75 {
76 unsigned long tmp;
77 u32 newval;
78 arch_spinlock_t lockval;
79
80 __asm__ __volatile__(
81 "1: ldrex %0, [%3]\n"
82 " add %1, %0, %4\n"
83 " strex %2, %1, [%3]\n"
84 " teq %2, #0\n"
85 " bne 1b"
86 : "=&r" (lockval), "=&r" (newval), "=&r" (tmp)
87 : "r" (&lock->slock), "I" (1 << TICKET_SHIFT)
88 : "cc");
89
90 while (lockval.tickets.next != lockval.tickets.owner) {
91 wfe();
92 lockval.tickets.owner = ACCESS_ONCE(lock->tickets.owner);
93 }
94
95 smp_mb();
96 }

3.10.27/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》)。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

ref:

DMB, DSB, ISB:

人體汽肛 - 風馳電掣, 人車一體

blog 文章

2015年11月3日星期二