- 论坛徽章:
- 0
|
第6章. 常见的例子
让我们一步步看一下一个简单的例子：一个对映射号的缓存(译者案：原文“a cache of number to name mappings”，虚存子系统不熟，恐怕翻译不确)。该缓存保存了对象的使用有多频繁这个数据，当它满了，抛出最少使用的那个。
6.1. 都在用户上下文
在第一个例子中，我们假定所有的操作都发生在用户上下文(也就是，都在系统调用中)，所以允许睡眠。这意味着我们可以使用信号量来保护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);
- }
- }
- /* 对上面函数的调用，这才是信号量发挥作用的地方──译注 */
- 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信号量的情况下对缓存添加、删除和查找操作：缓存结构自身与其中的对象都被该信号量保护起来。这种情况很简单，因为我们为用户拷贝数据，而不允许用户直接访问对象。
这里有一个轻量（而且很常见）的优化：在cache_add中，我们先设置对象的各个域，然后再获取锁。这是安全的，因为没有人能够在我们把对象加入到cache之前就访问它。
6.2. 从中断上下文中访问
现在我们来考虑一下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会关掉它们；否则（我们已经处在中断服务例程中）就什么也不做。这些函数可以安全地在任何上下文中调用。
不幸的是，cache_add调用了带有GFP_KERNEL标志的kmalloc，这只是在用户上下文才是合法的。我假定cache_add仍然只会在用户上下文中被调用，否则就应该给cache_add添加参数了。（译注：我觉得作者的意思是说，如果打算让cache_add能在中断和用户两种上下文中使用，应该添加一个参数来表达究竟是在哪种上下文中调用的。FIXME）
6.3. 把对象暴露在文件之外
如果对象包含更多的信息，仅仅提供拷贝函数是不够的：其它代码可能会需要保持一个指向对象的指针，例如，不想每次访问它都要先查找。这就产生了两个问题。
第一个问题是，我们采用cache_lock来保护对象，我们必须把这些函数定义为非static的，这样其它文件中的代码才能使用。这使得锁的使用更加技巧化，再也不是在同一地方了。
第二个问题是生命期问题。如果其它结构保留了一个指向我们的对象的指针，它多半期望该指针总是有效的。很不幸，这只在你持有锁时才会得到保证，否则其它人可能调用cache_delete来删除对象──还可能更糟糕，在删除之后又添加了另一个对象，还在原来的地址上。
但是由于只有一把锁，你也不能总持有它，否则其它人就完全无法工作了。
该问题的解决是使用引用计数：每个持有指向对象的指针的人，在他们第一次获得该指针时，递增一次引用计数；当他们使用完毕，递减一次引用计数。谁把引用计数减到了零，就知道可以删除了，于是执行删除操作。
下面是代码:
- --- 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;
- }
我们把引用计数操作封装进标准的‘get’和‘put’函数中。现在我们可以用cache_find返回对象的指针了，它具有引用计数功能。这样，持有对象指针的用户就可以睡眠了（例如，调用copy_to_user把名字拷贝到用户空间。）（译注：最后一句的意思是说，持有对象指针的用户不必象以前那样为了保证指针的合法性就一直持有锁了。引用计数本身跟锁以及是否可以睡眠一点关系都没有）
另一点要注意的是，我说“每个指向对象的指针都应该有一个引用计数”──因此当对象刚被插入到cache中时，其引用计数应当为1。有些不同版本的实现并不使用引用计数，但它们更加复杂。
6.3.1. 为引用计数使用原子操作
实践中，refcnt的类型应该是atomic_t。在include/asm/atomic.h中定义了几个原子操作：这些操作保证了从系统的所有CPU的角度看，都是原子的。因此不需要锁。这种情况下，原子操作要比自旋锁简单的多，尽管复杂情况下使用自旋锁要来得清晰。使用atomic_inc和atomic_dec_and_test来取代标准的加减操作符，再也不用为引用计数上锁了。
- --- 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. 保护对象自身
在上面的例子中，我们都假定对象(除了引用计数)自从创建之后就不会被更改。如果我们希望允许改变name(译者案，指struct object中的name域)，有三种可能：
*
你可以把cache_lock变成非static的，告诉人们改变name之前先获得锁。
*
你也可以提供一个cache_obj_rename函数，该函数先获得锁，然后为调用者改变name。你需要告诉每一个需要改变name的人使用这个函数。
*
你也可以用cache_lock只保护cache自身，而使用另一把锁来保护name域。
理论上，你可以把锁的使用细粒度化(fine-grained)到这样的程度：为每个域维持一把锁。实践中，最通用的变体是：
*
一把用来保护基础设施(infrastructure.本例中是cache链表)和所有对象的锁。至今为止我们在示例中看到的便是这种情况。
*
一把用来保护基础设施(包括对象结构中的链表指针)的锁，另一把放在对象内部，用来保护对象的其它域.
*
多把锁来保护基础设施(例如，Hash表的每一个链都用一把锁保护)，可能配合使用每个对象一把的锁。
下面是“每个对象一把的锁”的实现：
- --- 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本身占一个引用计数 */
- + 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域的读和写。
另外，注意我在注释里说明了哪些数据由哪些锁来保护。这是非常重要的，因为它描述了代码运行时的行为，(倘若不加注释)仅仅靠阅读代码是很难获得认识的。这正如Alan Cox所说，“锁是用来保护数据的，而非代码。” |
|
免费注册
发表于 2005-11-25 17:45
