- 論壇徽章:
- 0
|
第6章. 常見的例子
讓我們一步步看一下一個簡單的例子：一個對映射號的緩存(譯者案：原文“a cache of number to name mappings”，虛存子系統(tǒng)不熟，恐怕翻譯不確)。該緩存保存了對象的使用有多頻繁這個數(shù)據(jù)，當它滿了，拋出最少使用的那個。
6.1. 都在用戶上下文
在第一個例子中，我們假定所有的操作都發(fā)生在用戶上下文(也就是，都在系統(tǒng)調用中)，所以允許睡眠。這意味著我們可以使用信號量來保護cache和其中的所有對象。下面是代碼：
- #include <linux/list.h>
- #include <linux/slab.h>
- #include <linux/string.h>
- #include <asm/semaphore.h>
- #include <asm/errno.h>
- struct object
- {
- struct list_head list;
- int id;
- char name[32];
- int popularity;
- };
- /* 保護緩存、緩存號和其中的對象 */
- static DECLARE_MUTEX(cache_lock);
- static LIST_HEAD(cache);
- static unsigned int cache_num = 0;
- #define MAX_CACHE_SIZE 10
- /* 必須持有cache_lock信號量 */
- static struct object *__cache_find(int id)
- {
- struct object *i;
- list_for_each_entry(i, &cache, list)
- if (i->id == id) {
- i->popularity++;
- return i;
- }
- return NULL;
- }
- /* 必須持有cache_lock信號量 */
- static void __cache_delete(struct object *obj)
- {
- BUG_ON(!obj);
- list_del(&obj->list);
- kfree(obj);
- cache_num--;
- }
- /* 必須持有cache_lock信號量 */
- static void __cache_add(struct object *obj)
- {
- list_add(&obj->list, &cache);
- if (++cache_num > MAX_CACHE_SIZE) {
- struct object *i, *outcast = NULL;
- list_for_each_entry(i, &cache, list) {
- if (!outcast || i->popularity < outcast->popularity)
- outcast = i;
- }
- __cache_delete(outcast);
- }
- }
- /* 對上面函數(shù)的調用，這才是信號量發(fā)揮作用的地方──譯注 */
- int cache_add(int id, const char *name)
- {
- struct object *obj;
- if ((obj = kmalloc(sizeof(*obj), GFP_KERNEL)) == NULL)
- return -ENOMEM;
- strlcpy(obj->name, name, sizeof(obj->name));
- obj->id = id;
- obj->popularity = 0;
- down(&cache_lock);
- __cache_add(obj);
- up(&cache_lock);
- return 0;
- }
- void cache_delete(int id)
- {
- down(&cache_lock);
- __cache_delete(__cache_find(id));
- up(&cache_lock);
- }
- int cache_find(int id, char *name)
- {
- struct object *obj;
- int ret = -ENOENT;
- down(&cache_lock);
- obj = __cache_find(id);
- if (obj) {
- ret = 0;
- strcpy(name, obj->name);
- }
- up(&cache_lock);
- return ret;
- }
注意我們總是保證在持有cache_lock信號量的情況下對緩存添加、刪除和查找操作：緩存結構自身與其中的對象都被該信號量保護起來。這種情況很簡單，因為我們?yōu)橛脩艨截悢?shù)據(jù)，而不允許用戶直接訪問對象。
這里有一個輕量（而且很常見）的優(yōu)化：在cache_add中，我們先設置對象的各個域，然后再獲取鎖。這是安全的，因為沒有人能夠在我們把對象加入到cache之前就訪問它。
6.2. 從中斷上下文中訪問
現(xiàn)在我們來考慮一下cache_find會在中斷上下文中被調用的情況：這個“中斷上下文”或者是硬件中斷，或者是softirq。我們使用一個timer來從cache中刪除對象。
改寫了的代碼在下面，用標準的補丁形式給出：以-開始的行是被刪除了的，以+開始的行是新添加了的。
- --- cache.c.usercontext 2003-12-09 13:58:54.000000000 +1100
- +++ cache.c.interrupt 2003-12-09 14:07:49.000000000 +1100
- @@ -12,7 +12,7 @@
- int popularity;
- };
-
- -static DECLARE_MUTEX(cache_lock);
- +static spinlock_t cache_lock = SPIN_LOCK_UNLOCKED;
- static LIST_HEAD(cache);
- static unsigned int cache_num = 0;
- #define MAX_CACHE_SIZE 10
- @@ -55,6 +55,7 @@
- int cache_add(int id, const char *name)
- {
- struct object *obj;
- + unsigned long flags;
-
- if ((obj = kmalloc(sizeof(*obj), GFP_KERNEL)) == NULL)
- return -ENOMEM;
- @@ -63,30 +64,33 @@
- obj->id = id;
- obj->popularity = 0;
-
- - down(&cache_lock);
- + spin_lock_irqsave(&cache_lock, flags);
- __cache_add(obj);
- - up(&cache_lock);
- + spin_unlock_irqrestore(&cache_lock, flags);
- return 0;
- }
-
- void cache_delete(int id)
- {
- - down(&cache_lock);
- + unsigned long flags;
- +
- + spin_lock_irqsave(&cache_lock, flags);
- __cache_delete(__cache_find(id));
- - up(&cache_lock);
- + spin_unlock_irqrestore(&cache_lock, flags);
- }
-
- int cache_find(int id, char *name)
- {
- struct object *obj;
- int ret = -ENOENT;
- + unsigned long flags;
-
- - down(&cache_lock);
- + spin_lock_irqsave(&cache_lock, flags);
- obj = __cache_find(id);
- if (obj) {
- ret = 0;
- strcpy(name, obj->name);
- }
- - up(&cache_lock);
- + spin_unlock_irqrestore(&cache_lock, flags);
- return ret;
- }
注意一下，如果中斷原來是開啟著的，spin_lock_irqsave會關掉它們；否則（我們已經處在中斷服務例程中）就什么也不做。這些函數(shù)可以安全地在任何上下文中調用。
不幸的是，cache_add調用了帶有GFP_KERNEL標志的kmalloc，這只是在用戶上下文才是合法的。我假定cache_add仍然只會在用戶上下文中被調用，否則就應該給cache_add添加參數(shù)了。（譯注：我覺得作者的意思是說，如果打算讓cache_add能在中斷和用戶兩種上下文中使用，應該添加一個參數(shù)來表達究竟是在哪種上下文中調用的。FIXME）
6.3. 把對象暴露在文件之外
如果對象包含更多的信息，僅僅提供拷貝函數(shù)是不夠的：其它代碼可能會需要保持一個指向對象的指針，例如，不想每次訪問它都要先查找。這就產生了兩個問題。
第一個問題是，我們采用cache_lock來保護對象，我們必須把這些函數(shù)定義為非static的，這樣其它文件中的代碼才能使用。這使得鎖的使用更加技巧化，再也不是在同一地方了。
第二個問題是生命期問題。如果其它結構保留了一個指向我們的對象的指針，它多半期望該指針總是有效的。很不幸，這只在你持有鎖時才會得到保證，否則其它人可能調用cache_delete來刪除對象──還可能更糟糕，在刪除之后又添加了另一個對象，還在原來的地址上。
但是由于只有一把鎖，你也不能總持有它，否則其它人就完全無法工作了。
該問題的解決是使用引用計數(shù)：每個持有指向對象的指針的人，在他們第一次獲得該指針時，遞增一次引用計數(shù)；當他們使用完畢，遞減一次引用計數(shù)。誰把引用計數(shù)減到了零，就知道可以刪除了，于是執(zhí)行刪除操作。
下面是代碼:
- --- cache.c.interrupt 2003-12-09 14:25:43.000000000 +1100
- +++ cache.c.refcnt 2003-12-09 14:33:05.000000000 +1100
- @@ -7,6 +7,7 @@
- struct object
- {
- struct list_head list;
- + unsigned int refcnt;
- int id;
- char name[32];
- int popularity;
- @@ -17,6 +18,35 @@
- static unsigned int cache_num = 0;
- #define MAX_CACHE_SIZE 10
-
- +static void __object_put(struct object *obj)
- +{
- + if (--obj->refcnt == 0)
- + kfree(obj);
- +}
- +
- +static void __object_get(struct object *obj)
- +{
- + obj->refcnt++;
- +}
- +
- +void object_put(struct object *obj)
- +{
- + unsigned long flags;
- +
- + spin_lock_irqsave(&cache_lock, flags);
- + __object_put(obj);
- + spin_unlock_irqrestore(&cache_lock, flags);
- +}
- +
- +void object_get(struct object *obj)
- +{
- + unsigned long flags;
- +
- + spin_lock_irqsave(&cache_lock, flags);
- + __object_get(obj);
- + spin_unlock_irqrestore(&cache_lock, flags);
- +}
- +
- /* Must be holding cache_lock */
- static struct object *__cache_find(int id)
- {
- @@ -35,6 +65,7 @@
- {
- BUG_ON(!obj);
- list_del(&obj->list);
- + __object_put(obj);
- cache_num--;
- }
-
- @@ -63,6 +94,7 @@
- strlcpy(obj->name, name, sizeof(obj->name));
- obj->id = id;
- obj->popularity = 0;
- + obj->refcnt = 1; /* The cache holds a reference */
-
- spin_lock_irqsave(&cache_lock, flags);
- __cache_add(obj);
- @@ -79,18 +111,15 @@
- spin_unlock_irqrestore(&cache_lock, flags);
- }
-
- -int cache_find(int id, char *name)
- +struct object *cache_find(int id)
- {
- struct object *obj;
- - int ret = -ENOENT;
- unsigned long flags;
-
- spin_lock_irqsave(&cache_lock, flags);
- obj = __cache_find(id);
- - if (obj) {
- - ret = 0;
- - strcpy(name, obj->name);
- - }
- + if (obj)
- + __object_get(obj);
- spin_unlock_irqrestore(&cache_lock, flags);
- - return ret;
- + return obj;
- }
我們把引用計數(shù)操作封裝進標準的‘get’和‘put’函數(shù)中。現(xiàn)在我們可以用cache_find返回對象的指針了，它具有引用計數(shù)功能。這樣，持有對象指針的用戶就可以睡眠了（例如，調用copy_to_user把名字拷貝到用戶空間。）（譯注：最后一句的意思是說，持有對象指針的用戶不必象以前那樣為了保證指針的合法性就一直持有鎖了。引用計數(shù)本身跟鎖以及是否可以睡眠一點關系都沒有）
另一點要注意的是，我說“每個指向對象的指針都應該有一個引用計數(shù)”──因此當對象剛被插入到cache中時，其引用計數(shù)應當為1。有些不同版本的實現(xiàn)并不使用引用計數(shù)，但它們更加復雜。
6.3.1. 為引用計數(shù)使用原子操作
實踐中，refcnt的類型應該是atomic_t。在include/asm/atomic.h中定義了幾個原子操作：這些操作保證了從系統(tǒng)的所有CPU的角度看，都是原子的。因此不需要鎖。這種情況下，原子操作要比自旋鎖簡單的多，盡管復雜情況下使用自旋鎖要來得清晰。使用atomic_inc和atomic_dec_and_test來取代標準的加減操作符，再也不用為引用計數(shù)上鎖了。
- --- cache.c.refcnt 2003-12-09 15:00:35.000000000 +1100
- +++ cache.c.refcnt-atomic 2003-12-11 15:49:42.000000000 +1100
- @@ -7,7 +7,7 @@
- struct object
- {
- struct list_head list;
- - unsigned int refcnt;
- + atomic_t refcnt;
- int id;
- char name[32];
- int popularity;
- @@ -18,33 +18,15 @@
- static unsigned int cache_num = 0;
- #define MAX_CACHE_SIZE 10
-
- -static void __object_put(struct object *obj)
- -{
- - if (--obj->refcnt == 0)
- - kfree(obj);
- -}
- -
- -static void __object_get(struct object *obj)
- -{
- - obj->refcnt++;
- -}
- -
- void object_put(struct object *obj)
- {
- - unsigned long flags;
- -
- - spin_lock_irqsave(&cache_lock, flags);
- - __object_put(obj);
- - spin_unlock_irqrestore(&cache_lock, flags);
- + if (atomic_dec_and_test(&obj->refcnt))
- + kfree(obj);
- }
-
- void object_get(struct object *obj)
- {
- - unsigned long flags;
- -
- - spin_lock_irqsave(&cache_lock, flags);
- - __object_get(obj);
- - spin_unlock_irqrestore(&cache_lock, flags);
- + atomic_inc(&obj->refcnt);
- }
-
- /* Must be holding cache_lock */
- @@ -65,7 +47,7 @@
- {
- BUG_ON(!obj);
- list_del(&obj->list);
- - __object_put(obj);
- + object_put(obj);
- cache_num--;
- }
-
- @@ -94,7 +76,7 @@
- strlcpy(obj->name, name, sizeof(obj->name));
- obj->id = id;
- obj->popularity = 0;
- - obj->refcnt = 1; /* The cache holds a reference */
- + atomic_set(&obj->refcnt, 1); /* The cache holds a reference */
-
- spin_lock_irqsave(&cache_lock, flags);
- __cache_add(obj);
- @@ -119,7 +101,7 @@
- spin_lock_irqsave(&cache_lock, flags);
- obj = __cache_find(id);
- if (obj)
- - __object_get(obj);
- + object_get(obj);
- spin_unlock_irqrestore(&cache_lock, flags);
- return obj;
- }
6.4. 保護對象自身
在上面的例子中，我們都假定對象(除了引用計數(shù))自從創(chuàng)建之后就不會被更改。如果我們希望允許改變name(譯者案，指struct object中的name域)，有三種可能：
*
你可以把cache_lock變成非static的，告訴人們改變name之前先獲得鎖。
*
你也可以提供一個cache_obj_rename函數(shù)，該函數(shù)先獲得鎖，然后為調用者改變name。你需要告訴每一個需要改變name的人使用這個函數(shù)。
*
你也可以用cache_lock只保護cache自身，而使用另一把鎖來保護name域。
理論上，你可以把鎖的使用細粒度化(fine-grained)到這樣的程度：為每個域維持一把鎖。實踐中，最通用的變體是：
*
一把用來保護基礎設施(infrastructure.本例中是cache鏈表)和所有對象的鎖。至今為止我們在示例中看到的便是這種情況。
*
一把用來保護基礎設施(包括對象結構中的鏈表指針)的鎖，另一把放在對象內部，用來保護對象的其它域.
*
多把鎖來保護基礎設施(例如，Hash表的每一個鏈都用一把鎖保護)，可能配合使用每個對象一把的鎖。
下面是“每個對象一把的鎖”的實現(xiàn)：
- --- cache.c.refcnt-atomic 2003-12-11 15:50:54.000000000 +1100
- +++ cache.c.perobjectlock 2003-12-11 17:15:03.000000000 +1100
- @@ -6,11 +6,17 @@
-
- struct object
- {
- + /* 下面兩個域，由cache_lock來保護 */
- struct list_head list;
- + int popularity;
- +
- atomic_t refcnt;
- +
- + /* Doesn't change once created. */
- int id;
- +
- + spinlock_t lock; /* Protects the name */
- char name[32];
- - int popularity;
- };
-
- static spinlock_t cache_lock = SPIN_LOCK_UNLOCKED;
- @@ -77,6 +84,7 @@
- obj->id = id;
- obj->popularity = 0;
- atomic_set(&obj->refcnt, 1); /* cache本身占一個引用計數(shù) */
- + spin_lock_init(&obj->lock);
-
- spin_lock_irqsave(&cache_lock, flags);
- __cache_add(obj);
注意我的策略是popularity域由cache_lock來保護，而不是每個對象一把的鎖。這是因為它(就象對象內部的struct list_head域一樣)在邏輯上是屬于基礎設施的一部分的。這樣，當在__cache_add查找最少使用的對象時，我就不必去獲取每個對象一把的鎖了。
這個策略還有一處要注意：id域是不可更改的，這樣我就不必在__cache_find()時去獲取每個對象一把的鎖來保護它。每個對象一把的鎖，在這里，只是被調用者使用來保護name域的讀和寫。
另外，注意我在注釋里說明了哪些數(shù)據(jù)由哪些鎖來保護。這是非常重要的，因為它描述了代碼運行時的行為，(倘若不加注釋)僅僅靠閱讀代碼是很難獲得認識的。這正如Alan Cox所說，“鎖是用來保護數(shù)據(jù)的，而非代碼。” |
|
免費注冊
發(fā)表于 2005-11-25 17:45
