1. Đồng bộ hóa trong Linux kernel.
Linux kernel là một hệ điều hành đa nhiệm, nó tồn tại các luồng thực thi chia sẻ dữ liệu dùng chung với nhau, do đó việc đảm bảo các tài nguyên này không bị truy cập đồng thời từ nhiều tiến trình hay đồng bộ hóa tiến trình là hết sức cần thiết.
Trong lập trình, các đoạn code truy cập đến phần dữ liệu dùng chung được gọi là Critical Region. Trên góc nhìn thực tế đầy tiền mặt, thì chẳng hạn như có 1 cột ATM VCB đang dựng đấy, người nào muốn rút tiền thì phải nhét thẻ(card) và gõ pass mang tiền về. Rõ ràng là để đưa thẻ cho cây ATM thì cần tiếp cận được cái lỗ (nhận thẻ) của nó, có thể coi cãi lỗ đấy là key, ai sở hữu key đó thì mới có thể rút tiền được, ngược lại sẽ phải đứng đợi đến khi cái lỗ đấy trống để đút vào.
Còn trong thế giới phần mềm thì bạn có thể tưởng tượng ra việc bạn có một dãy đèn LED và có 2 thread (hoặc process) đều cố gắng ghi các giá trị khách nhau vào vị trí đèn, điều gì sẽ xảy ra ? Đây chính là trường hợp Race condition (sách tiếng việt gọi là miền găng). Bởi vì việc thread nào chạy trước, thread nào chạy sau hoàn toàn phụ thuộc vào giải thuật lập lịch và về cơ bản là chúng ta không đoán trước được, nên kết quả của viêc này chúng ta không đoán trước được.
. Qua hai ví dụ trên, dễ thấy việc nhiều luồng thực thi truy cập cùng một tài nguyên tại cùng một thời điểm là không an toàn, ẩn chứa nhiều hiểm nguy, côn trùng. Do đó, tốt nhất là nên ngăn chặn việc truy cập đồng thời này, tức là khi một luồng thực thi đang truy cập và sử dụng tài nguyên dùng chung, thì chúng ta cần đảm bảo nó sẽ hoàn thành việc sử dụng tài nguyên này trước khi một luồng thực thi khác có thể truy cập, hay nói cách khác, thao tác này phải là atomic, không thể bị ngắt quãng. Để tránh race condition, các nhà khoa học tiền bối đã phát minh ra một số phương pháp, đa số dựa trên kỹ thuật locking.
1. Mutex trong Linux.
Mutex là gì ? Theo 1 góc nào đó trên wiki thì: khái niệm “mutex” thường được sử dụng để mô tả một cấu trúc ngăn cản hai tiến trình cũng thực hiện một đoạn mã hoặc truy cập một dữ liệu cùng lúc. Vậy về mặt khoa học, Mutex là gì? Mutex là một khóa “loại trừ lẫn nhau”. Tại mỗi thời điểm chỉ có 1 thread có thể giữ khóa. Mutex có thể được sử dụng để tránh race condition. Một khi mutex bị lock thì chỉ có thread đã lock nó mới có thể unlock nó. Do đó, mỗi khi bạn muốn truy cập 1 tài nguyên dùng chung thì đầu tiên bạn phải khóa mutex (trong trường hợp bạn dành được khóa) rồi mới sử dụng tài nguyên, và nhớ phải unlock nó cho người khác dùng sau khi bạn đã hoàn thành công việc.
struct mutex {
atomic_t count;
spinlock_t wait_lock;
struct list_head wait_list;
};Một mutex có thể được khởi tạo bằng DEFINE_MUTEX(name) - trong trường hợp mutex được khai báo vả khởi tạo ở compile time. Hoặc mutex_init(struct mutex *lock)- trong trường hợp chúng ta muốn khởi tạo mutex ở run-time.
Khi mutex đã được khởi tạo thì chúng ta có thể lock hay unlock nó. Kernel API cung cấp 5 hàm cho các tác vụ này, bao gồm 3 hàm được sử dụng cho việc lock, một hàm cho việc unlock, hàm còn lại dùng cho việc kiểm tra tình trạng mutex.
mutex_lockSử dụng để lock/acquire mutex. Nếu mutex không khả dụng, thì task hiện tại sẽ được cho vào trạng thái sleep cho đến khi nó giành được mutex.mutex_lock_interruptibleTương tự như hàm mutex_lock, tuy nhiên trong thời gian đợi mutex, ta có thể interrupt task, chẳng hạn với CTRL+C.mutex_trylockGiống như cái tên của nó, nếu không dành được lock nó sẽ return chứ không đợi chờ gì cả.mutex_unlockHàm này được sử dụng để giải phóng một mutex mà nó đã khóa trước đó (cùng 1 thread - task). Ai thắt nút thì người đó phải mở nút. Lưu ý rằng khi một process đang sở hữu một mutex, thì process đó chỉ có thể kết thúc nếu nó đã unlock cho mutex nó đang nắm giữ.mutex_is_lockedkiểm tra xem mutex có đang bị lock không (có thể dùng chúng với mutex_trylock).
Tại một thời điểm thì có một và chỉ một task có thể nắm giữ mutex, hơn nữa chỉ có task đang nắm giữ Mutex mới có thể thực hiện các thay đổi trạng thái của Mutex. Quyền sở hữu mutex không có tính đệ quy, tức là khi bạn không thể gọi đến hàm lock() của một mutex mà ta đã gọi hàm lock() thành công trước đó.
Khi một task không dành được quyền sử dụng thì nó sẽ được chuyển sang trạng thái “ngủ” (sleep) và scheduler sẽ đưa nó vào hàng đợi để dành processor cho một task khác. Điều này có nghĩ là mutex chỉ có thể được sử dụng trong process context, chúng ta KHÔNG thể sử dụng mutex khi đang ở trong interrupt context được.
2. Completion Variable
Một trong các pattern phổ biến trong kernel programming là khởi tạo một số activity bên ngoài luồng thực thi hiện tại, sau đó đợi đến khi activity đó hoàn thành(async), Activity này có thể là tạo một kernel thread hoặc một user-space process mới, một request đến một process đã tồn tại, hoặc một số hardware-based action. Ví dụ:
struct semaphore sem;
init_MUTEX_LOCKED(&sem);
start_external_task(&sem);
down(&sem);(Code trên sẽ làm giảm performance, hơn nữa vì semaphore đã bị loại bỏ trong các bản kernel > 3.x nên code này không compile được đâu :gach: )
external_task sau đó có thể gọi up(&sem) khi công việc của nó hoàn thành.
Completion interface được dùng trong trường hợp này, nó cho phép một thread có thể thông báo với một thread khác rằng nó đã hoàn thành công việc. Do kỹ thuật này khá thông dụng, nên Linux kernel cung cấp Completion variable để thực hiện các thao tác này.
Compiletion variable trong linux kernel được biểu diễn bằng struct completion, cấu trúc dữ liệu này và các function thao tác trên nó được khai báo trong file header: linix/completion.h
Tạo một completion tại compile time bằng macro: DECLARE_COMPLETION(my_completion);
Trường hợp cần khởi tạo ở runtime:
struct comletion my_completion;
Sau đấy chúng ta cần báo cho thread biết nó cần đợi completion.
struct init_completion(&my_completion);
wait_for_completion(struct completion *c);
function này tạo ra một uninterruptible wait(tức là chúng ta không thể kill được process cho đến khi cái completion được set là đã hoàn thành).
Thread đang được đợi, sẽ thông báo cho calling thead rằng nó đã hoàn thành công việc bằng cách gọi một trong hai hàm sau:
complete(struct completion *c); Chỉ wake up một thread duy nhất
compelete_all(struct completion *c); Weke up tất cả các thread đang đợi
Một completion thường là one-shot device, tức là nó chỉ được dùng 1 lần sau đó sẽ bị discard. Tuy nhiên, việc sử dụng lại một completion là khả dĩ. Nếu complete_all không được sử dụng, thì struct completion có thể được sử dụng lại một cách dễ dàng. Nếu complete_all đã dược gọi, thì completion variable cần được tái tạo trước khi sử dụng với macro:
INIT_COMPLETION(struct completion c);
Appendex: void complete_and_exit(struct completion *c, long retval);
Một ứng dụng phổ biến của completion variable trong Linux kernel là dùng để kiểm tra việc load các offload-firmware cho các thiết bị PCIe hay USB.
3. Spinlocks
Mặc dù mutex rất hữu ích, nhưng trong kernel việc xử lý race condition được thực hiện bằng một kỹ thuật tên là spinlock. Không giống như mutex, spinlocks có thẻ được sử dụng được ở trong các đoạn code không thể sleep, ví dụ như các interrupt handlers. Khi được sử dụng đúng cách, spinlock cung cấp hiệu năng cao hơn so với mutex. Tuy nhiên spinlock cũng có một tập các ràng buộc riêng của nó.
Một spinlock là một mutual exclusion device có thể có hai và chỉ hai trạng thái “locked” và “unlocked”. Nó thường được implement như một bit trong một số int.
Nếu như lock là khả dụng, thì “locked” bit được set và code sẽ tiếp tục thực thi (đi vào critical section). Ngược lại, nếu một ai đó đã set bit “locked” từ trước, thì code sẽ đi vào một vòng lặp nhỏ, và lặp đi lặp lại việc kiểm tra lock cho đến khi bit “locked” được unset. Vòng lặp này được gọi là spin.
Đây cũng là điểm khác biệt giữa Mutex và Spinlock.
Trong thời gian spinlock đang “xoay” thì processor sẽ không thể thực thi các tác vụ khác, còn mutex thì processor có thể chuyển sang làm việc khác. Thoạt nghe thì có vẻ spinlock đã lãng phí tài nguyên (processor), tuy nhiên thực tế thì với các trường hợp mà thời gian chờ đợi để truy cập dữ liệu dùng chung của task là rất nhỏ, và tần suất vào ra miền dùng chung cao, thì việc sử dụng spinlock vẫn cho hiệu quả hơn hẳn vì nó không tốn chi phí thực hiện các context switch.
Tất nhiên, việc set và unset “locked” bit cần được thực hiện trong ngữ cảnh atomic, điểu này đảm bảo rằng chỉ có một thread duy nhất có thể dành được lock, kể cả nếu như có nhiều spin đang hoạt động.
Cần cẩn thận với deadlocks trên hyperthreaded processors.
Spinlock được tạo ra để hướng đến việc sử dụng trên multiprocessor systems.
4. Spinlock API
Để sử dụng được spinlock trong kernel thì các config CONFIG_PREEMPT và CONFIG_SMP phải được enable. ( Không có preemption và multi core thì bạn không cần mấy cái kỹ thuật này làm gì cả).
Các hàm và cấu trúc liên quan của spinlock được khai báo trong file header linux/spinlock.h
Và cũng giống như mutex, spinlock api cung cấp hai khả năng khởi tạo một spinlock:
- Khởi tạo spinlock ở compile time:
DEFINE_SPINLOCK(lock); - Khởi tạo spinlock ở runtime:
void spin_lock_init(spinlock_t *lock);
Trước khi vào miền găng, cần phải dành được lock bằng lời gọi hàm sau:
spin_lock(spinlock_t *lock);
Khi code của bạn gọi hàm này, nó sẽ spin đến khi lock khả dụng, lưu ý là tất cả các spin là không thể ngắt.(Cẩn thận deadlock)
Sau khi thực hiện xong các tác vụ cần thiết, chúng ta giải phóng lock:
void spin_unlock(spinlock_t *lock);
5. Spinlocks and atomic context
Thử tưởng tượng trong lúc driver của bạn đang yêu cầu một spinlock và đang chuẩn bị thực hiện công việc của nó trong miền găng thì ở một nơi nào đó, nó bị mất quyền sử dụng processor.(Có thể nó gọi đến một hàm nào đó khiến processor sleep). Hoặc trong hệ thống SMP, kernel gạt tác vụ hiện tại ra khỏi processor để dành chỗ cho một tác vụ khác có độ ưu tiên cao hơn. Vấn đề là, hiện tại code của bạn hiện tại đang giữ lock, và nó sẽ không được giải phóng tại bất kỳ thời điểm có thể dự báo trong tương lai. Nếu một số thread khác cố gắng lấy cùng lock đó, nó sẽ đợi thời gian rất dài. Trong trường hợp tệ nhất, toàn hệ thống có thể rơi vào deadlock.
May mắn là, spinlock có thể xử lý trường hợp kernel preemption bởi chính nó. Mỗi khi task nắm giữ một spinlock. preemption sẽ bị vô hiệu hóa trên processor liên quan. Kể cả đối với hệ thống đơn tiến trình, preemption cũng cần được vô hiệu hóa theo cách này để tránh vi phạm các nguyên tắc của miền găng. (Do đó spinlock cần sử dụng một cách chính xác nếu không hiệu năng hệ thống sẽ bị giảm kinh khủng).
Tuy nhiên, việc tránh cho process sleep trong khi đang giữ lock là một điều khó khăn hơn nhiều; nhiều kernel functions có thể sleep, và điều này không phải lúc nào cũng được ghi chép một cách rõ ràng trong tài liệu. Do đó khi sử dụng spinlock, cần phải quan tâm đến tất cả function liên quan trong code của bạn.
Mặc dù spinlock có thể được sử dụng trong các hàm xử lý ngắt, tuy nhiên, trong những trường hợp này, code của bạn phải vô hiệu hóa interrupt trên processor hiện tại trước khi gọi yêu cầu sở hữu spinlock, nếu không làm như vậy, có thể xảy ra trường hợp một interrupt khác xảy ra trong lúc code của bạn đang xử lý với tài nguyên dùng chung, lúc này hàm xử lý ngắt thứ hai cũng sẽ yêu cầu spinlock từ kernel, tuy nhiên do hàm xử lý ngắt đầu tiên đang nắm giữ nó nên hàm thứ hai này sẽ phải chờ đợi. Tuy nhiên, do hàm xử lý đầu tiên đã bị hàm thứ hai dành mất Processor nên nó sẽ không bao giờ giải phóng spinlock đang nắm giữ, và gây ra deadlock trong hệ thống.
Luật lệ quan trọng cuối cùng trong việc sử dụng spinlock là spinlocks phải luôn luôn được giữ trong khoảng thời gian ngắn nhất có thể. Spinlock bị giữ càng lâu, thì processor đợi spinlock sẽ bị block càng lâu, và nguy cơ các processor này rơi vào spinning khác càng nhiều hơn. Thời gian giữ lock dài cũng khiến processor đứng trong scheduler lâu hơn, điều này khiến cho process khác có priority cao hơn phải đợi lâu hơn.
Một driver được viết tệ hại có thể khiến tất cả các process phải ngồi đợi lock quá lâu => Performance giảm tụt quần
6. Spinlock Functions.
a. Các function có thể lock một spinlock Spinock api cung cấp khá nhiều hàm lock để sử dụng trong các ngữ cảnh khách nhau
void spin_lock(spinlock_t *lock);//Đã nói ở phần trênvoid spin_lock_irqsave(spinlock_t *lock, unsigned long flags);Hàm này sử dụng khi bạn cần lock giữa HARD IRQ và bottom halfvoid spin_lock_irq(spinlock_t *lock)
Giống hàm trên nhưng nó không lưu lại trạng thái của interrupt mà sẽ luôn enable interrupts khi code giải phóng spinlock.void spin_lock_bh(spinlock_t *lock);
Sử dụng khi cần tạo lock giữa Process context và Bottom half interrupt. Hàm này vô hiệu hóa software interrupts trước khi obtain lock, nhưng vẫn để hardware interrupts hoạt động.
b. Tương ứng với các hàm trên chúng ta có 4 hàm để unlock một spinlockvoid spin_unlock(spinlock_t *lock);void spin_unlock_restore(spinlock_t *lock, unsigned log flags);void spin_unlock_irq(spinlock_t *lock);void spin_unlock_bh(spinlock_t *lock);
no blocking version
int spin_trylock(spinlock_t *lock);int spin_trylock_bh(spinlock_t *lock);
7. Practice make perfect
Bây giờ đến phần ví dụ, phần này sẽ dùng lại device driver đã viết trong bài Character device, và thêm phần xử lý miền găng vào. Nhưng trước hết, hãy viết một user-program để việc test được dễ dàng và rõ ràng hơn. Tạo một file code mới có tên là: oni_test_app.c
#include<stdio.h>
#include<stdlib.h>
#include<errno.h>
#include<fcntl.h>
#include<string.h>
#include<unistd.h>
#define BUFFER_LENGTH 256 ///< The buffer length (crude but fine)
static char receive[BUFFER_LENGTH]; ///< The receive buffer from the LKM
int main(){
int ret, fd;
char stringToSend[BUFFER_LENGTH];
printf("Starting device test code example...\n");
fd = open("/dev/oni_chrdev", O_RDWR); // Open the device with read/write access
if (fd < 0){
perror("Failed to open the device...");
return errno;
}
printf("Type in a short string to send to the kernel module:\n");
scanf("%[^\n]%*c", stringToSend); // Read in a string (with spaces)
printf("Writing message to the device [%s].\n", stringToSend);
ret = write(fd, stringToSend, strlen(stringToSend)); // Send the string to the LKM
if (ret < 0){
perror("Failed to write the message to the device.");
return errno;
}
printf("Press ENTER to read back from the device...\n");
getchar();
printf("Reading from the device...\n");
ret = read(fd, receive, BUFFER_LENGTH); // Read the response from the LKM
if (ret < 0){
perror("Failed to read the message from the device.");
return errno;
}
printf("The received message is: [%s]\n", receive);
printf("End of the program\n");
return 0;
}Compile file test vừa tạo bằng command sau:
$gcc oni_chrdev_test.c -o testBây giờ insert module vào kernel và chạy thử file test bằng quyền sudo, thực hiện các bước theo chỉ dẫn in ra, nhận được kết quả như sau:
$ sudo ./test
$ Starting device test code example...
$ Type in a short string to send to the kernel module"
$ Linux kernel
$ Writing message to the device [Linux kernel]
$ Press ENTER to read back from the device...
$ Reading from the device...
$ The received message is: [nguyen phi]
$ End of the programGiải thích: khi chạy file test, nó sẽ yêu cầu nhập vào một string ngắn từ bàn phím, string này sẽ được lưu copy vào kernel space và lưu ở biến msg của module. Sau đó, khi người dùng ấn Enter, giá trị của msg sẽ được copy ngược lại ra user-app và in ra màn hình.
Bây giờ hãy thử một bài test để chứng tỏ tính không đồng bộ của device driver hiện tại:
-Mở 2 tab terminal và chạy sudo ./test ở cả 2 tab.
-Ở tab đầu tiên, nhập vào chuỗi “Temp1”, rồi để nó ở đấy, tức là chương trình đã ghi chuỗi “Temp1” vào device.
-Ở tab 2, nhập vào chuỗi “Temp2”, sau đó gõ enter để đọc, thì chương trình sẽ in ra The received message is: Temp2
-Quay lại tab đầu tiên, bây giờ gõ Enter, thì màn hình sẽ in ra The received message is: Temp2. Tức là thay vì in ra chuỗi “Temp1” thì nó lại in ra “Temp2”
. Lý do là vì cả 2 chương trình test đều dùng chung resource là device file oni_chrdev. Chương trình 2 chạy sau, nên hàm write của nó đã overwrite giá trị biến msg. Sau đó khi p2 thực hiện hàm read, nó cũng xóa luôn msg, nên p1 thực hiện hàm read sau sẽ chỉ đọc được một chuỗi rỗng, ngược lại nếu thực hiện read của p1 trước p2, thì giá trị in ra cũng là [Temp2] chứ không phải [Temp1] như mong đợi.
Để giải quyết vấn đề này, chúng ta sẽ chỉ cho phép một instance của device file (fd) được mở tại cùng 1 thời điểm. Mình sẽ khai báo một mutex và lock nó ở hàm open và unlock ở hàm release. Đầu tiên phải thêm header chứa mutex vào và định nghĩa 1 mutex để sử dụng:
#include <linux/mutex.h>
........
static DEFINE_MUTEX(oni_mutex);
Bây giờ cần sửa hàm oni_open, hiện tại hàm này đang không làm gì cả. Hàm này sẽ kiểm tra xem mutex có đang vô chủ không, nếu có thì không cần làm gì cả, ngược lại, nó sẽ return lỗi device file đang bận và không cho phép user-app mở device file.
static int oni_open(struct inode* node, struct file *filp)
{
if(!mutex_trylock(&oni_mutex))
{
printk(KERN_ALERT "Oni chardev: Device in use by another process");
return -EBUSY;
}
return 0;
}
Đến đây, nếu một process “P1” dành được mutex, nó sẽ mở được device file, nhưng các process khác sẽ không bao giờ động đến device file được, kể cả khi P1 đã đóng device file, vì hiện tại, mình chưa tạo đoạn code giải phóng mutex. Để làm điều này, mình sửa hàm oni_release như sau:
static int oni_open(struct inode* node, struct file *filp)
{
mutex_unlock(&oni_mutex);
return 0;
}Compile lại device driver và insert nó vào kernel. Mở 2 tab terminal. Ở tab đầu tiên chạy 1 process test:
sudo ./test
Kết quả hiện ra như sau:
Starting device test code example...
Type in a short string to send to the kernel module:
Mở tiếp 1 process khác ở tab thứ 2: sudo ./test. Kết quả hiện ra như sau:
Starting device test code example...
Failed to open the device ...: Device or resource busy.Như vậy, với việc thêm Mutex vào hàm open và release, bây giờ chỉ có 1 fd có thể được mở tại cùng một thời điểm.
Tiếp theo, thay vì dùng Mutex, hãy thử dùng spinlock. Thay header linux/mutex.h bằng linux/spinlock.h>.
Cũng giống như Mutex, để dùng được spinlock, ta cần định nghĩa nó trước thay dòng DEFINE_MUTEX(oni_mutex> bằng DEFINE_SPINLOCK(my_lock);
Sửa nội dung hàm open và release thành như sau:
static int oni_open(struct inode* node, struct file *filp)
{
spin_lock(&my_lock);
return 0;
}static int oni_open(struct inode* node, struct file *filp)
{
spin_lock(&my_lock);
return 0;
}Với code này, khi mở một process test thứ 2, nó sẽ phải đợi (spin) đến khi process đầu tiên đóng device file thì nó mới được mở device file để thực hiện các tác vụ.
Leave a Comment