linux 1.0 内核注解 linux/fs/ext2/dcache.c
时间：2009-05-25 来源：taozhijiangscu
/********************************************
*Created By: Prometheus
*Date : 2009-5-25
********************************************/ /*
* linux/fs/ext2/dcache.c
*
* Copyright (C) 1992, 1993, 1994 Remy Card ([email protected])
* Laboratoire MASI - Institut Blaise Pascal
* Universite Pierre et Marie Curie (Paris VI)
*
*/ /*
* dcache.c contains the code that handles the directory cache used by
* lookup() and readdir()
*/ //其实就只是两个双向链表的维护，看看数据结构的功底了 #include <asm/segment.h> #include <linux/fs.h>
#include <linux/ext2_fs.h>
#include <linux/string.h> #ifndef DONT_USE_DCACHE #define DCACHE_NAME_LEN 32 struct dir_cache_entry {
unsigned short dev;
unsigned long dir;
unsigned long ino;
char name[DCACHE_NAME_LEN + 1];
int len;
struct dir_cache_entry * queue_prev; //哈希表的双向链表（但是不循环）
struct dir_cache_entry * queue_next;
struct dir_cache_entry * prev; //所有结构的双向链表（但是不循环）
struct dir_cache_entry * next;
}; static struct dir_cache_entry * first = NULL;
static struct dir_cache_entry * last = NULL;
static struct dir_cache_entry * first_free = NULL;
static int cache_initialized = 0;
#ifdef EXT2FS_DEBUG_CACHE
static int hits = 0;
static int misses = 0;
#endif #define CACHE_SIZE 128 static struct dir_cache_entry dcache[CACHE_SIZE]; #define HASH_QUEUES 16 static struct dir_cache_entry * queue_head[HASH_QUEUES];
static struct dir_cache_entry * queue_tail[HASH_QUEUES]; //哈希算法
#define hash(dev,dir) ((dev ^ dir) % HASH_QUEUES) /*
* Initialize the cache
*/
static void init_cache (void)
{
int i; dcache[0].prev = NULL;
dcache[0].next = &dcache[1];
dcache[0].queue_next = dcache[0].queue_prev = NULL;
for (i = 1; i < CACHE_SIZE - 1; i++) {
dcache[i].prev = &dcache[i - 1];
dcache[i].next = &dcache[i + 1];
dcache[i].queue_next = dcache[i].queue_prev = NULL;
}
dcache[i].prev = &dcache[i - 1];
dcache[i].next = NULL;
dcache[i].queue_next = dcache[i].queue_prev = NULL;
first_free = &dcache[0];
for (i = 0; i < HASH_QUEUES; i++) //哈希表队列的头尾
queue_tail[i] = queue_head[i] = NULL;
cache_initialized = 1;
} /*
* Find a name in the cache
*/
//这里queue选择了哈希数组的入口项，而后面的很多信息都是进行核实的
//函数可以返回NULL
static struct dir_cache_entry * find_name (int queue, unsigned short dev,
unsigned long dir,
const char * name, int len)
{
struct dir_cache_entry * p; for (p = queue_head[queue]; p != NULL && (p->dev != dev ||
p->dir != dir || p->len != len ||
strncmp (name, p->name, p->len) != 0);
p = p->queue_next)
;
return p;
} #ifdef EXT2FS_DEBUG_CACHE
/*
* List the cache entries for debugging
*/
static void show_cache (const char * func_name)
{
struct dir_cache_entry * p; printk ("%s: cache status\n", func_name);
for (p = first; p != NULL; p = p->next)
printk ("dev:%04x, dir=%4lu, name=%s\n",
p->dev, p->dir, p->name);
}
#endif /*
* Add an entry at the beginning of the cache
*/
//将入口添加到队列的最前面，同时修改first和last
static void add_to_cache (struct dir_cache_entry * p)
{
p->prev = NULL;
p->next = first;
if (first)
first->prev = p;
if (!last)
last = p;
first = p;
} /*
* Add an entry at the beginning of a queue
*/
//将项添加到哈希队列中的最前面
static void add_to_queue (int queue, struct dir_cache_entry * p)
{
p->queue_prev = NULL;
p->queue_next = queue_head[queue];
if (queue_head[queue])
queue_head[queue]->queue_prev = p;
if (!queue_tail[queue])
queue_tail[queue] = p;
queue_head[queue] = p;
} /*
* Remove an entry from the cache
*/
static void remove_from_cache (struct dir_cache_entry * p)
{
if (p->prev)
p->prev->next = p->next;
else //否则就是在顶端了
first = p->next;
if (p->next)
p->next->prev = p->prev;
else //否则就是在尾端了
last = p->prev;
p->prev = NULL;
p->next = NULL;
} /*
* Remove an entry from a queue
*/
static void remove_from_queue (int queue, struct dir_cache_entry * p)
{
if (p->queue_prev)
p->queue_prev->queue_next = p->queue_next;
else
queue_head[queue] = p->queue_next;
if (p->queue_next)
p->queue_next->queue_prev = p->queue_prev;
else
queue_tail[queue] = p->queue_prev;
p->queue_prev = NULL;
p->queue_next = NULL;
} /*
* Invalidate all cache entries on a device (called by put_super() when
* a file system is unmounted)
*/
//使得制定设备上的所有的目录缓冲都失效（从队列中删除）
void ext2_dcache_invalidate (unsigned short dev)
{
struct dir_cache_entry * p;
struct dir_cache_entry * p2; if (!cache_initialized)
init_cache ();
for (p = first; p != NULL; p = p2) {
p2 = p->next; //这个是很常用的，先保存下一个要处理的东西
if (p->dev == dev) {
remove_from_cache (p);
remove_from_queue (hash (p->dev, p->dir), p);
p->next = first_free; //记录成空闲的
first_free = p;
}
}
#ifdef EXT2FS_DEBUG_CACHE
show_cache ("dcache_invalidate");
#endif
} /*
* Lookup a directory entry in the cache
*/
unsigned long ext2_dcache_lookup (unsigned short dev, unsigned long dir,
const char * name, int len)
{
char our_name[EXT2_NAME_LEN];
int queue;
struct dir_cache_entry * p; if (!cache_initialized)
init_cache ();
if (len > DCACHE_NAME_LEN)
return 0;
memcpy (our_name, (char *) name, len);
our_name[len] = '\0';
#ifdef EXT2FS_DEBUG_CACHE
printk ("dcache_lookup (%04x, %lu, %s, %d)\n", dev, dir, our_name, len);
#endif
queue = hash (dev, dir);
if ((p = find_name (queue, dev, dir, our_name, len))) {
//这个才是真正的查找函数，而本身函数只是注重后续数据结构完整性的处理
//这里将找到的放置到了最前面，可能是为了下次快速找到而这样的
if (p != first) {
remove_from_cache (p);
add_to_cache (p);
}
if (p != queue_head[queue]) {
remove_from_queue (queue, p);
add_to_queue (queue, p);
}
#ifdef EXT2FS_DEBUG_CACHE
hits++;
printk ("dcache_lookup: %s,hit,inode=%lu,hits=%d,misses=%d\n",
our_name, p->ino, hits, misses);
show_cache ("dcache_lookup");
#endif
return p->ino;
} else {
#ifdef EXT2FS_DEBUG_CACHE
misses++;
printk ("dcache_lookup: %s,miss,hits=%d,misses=%d\n",
our_name, hits, misses);
show_cache ("dcache_lookup");
#endif
return 0;
}
} /*
* Add a directory entry to the cache
*
* This function is called by ext2_lookup(), ext2_readdir()
* and the functions which create directory entries
*/
void ext2_dcache_add (unsigned short dev, unsigned long dir, const char * name,
int len, unsigned long ino)
{
struct dir_cache_entry * p;
int queue; if (!cache_initialized)
init_cache ();
#ifdef EXT2FS_DEBUG_CACHE
printk ("dcache_add (%04x, %lu, %s, %d, %lu)\n",
dev, dir, name, len, ino);
#endif
if (len > DCACHE_NAME_LEN)
return;
queue = hash (dev, dir);
if ((p = find_name (queue, dev, dir, name, len))) {
p->dir = dir;
p->ino = ino;
if (p != first) {
remove_from_cache (p);
add_to_cache (p);
}
if (p != queue_head[queue]) {
remove_from_queue (queue, p);
add_to_queue (queue, p);
}
} else { //这个标示制定的目录结构不在缓冲中，添加进去
if (first_free) {
p = first_free; //取出空闲的缓冲项
first_free = p->next;
} else { //这里说明没有现成的空闲的缓冲项了，直接取出队列的最后一项来
//存储这个目录信息
//一般来说，如果既没有空闲项也没有实际存在的项，便可能是数据结构出问题了
if (!last)
panic ("dcache_add: last == NULL\n");
else { //这里将最后一项(应该是最近最没有被命中的项)先从队列中取出
//注意取出要维持两个链表的哦
p = last;
last = p->prev;
if (last)
last->next = NULL;
remove_from_queue (hash (p->dev, p->dir), p);
}
}
p->dev = dev; //记录缓冲的信息
p->dir = dir;
p->ino = ino;
strncpy (p->name, name, len);
p->len = len;
p->name[len] = '\0';
add_to_cache (p);
add_to_queue (queue, p);
}
#ifdef EXT2FS_DEBUG_CACHE
show_cache ("dcache_add");
#endif
} /*
* Remove a directory from the cache
*
* This function is called by the functions which remove directory entries
*/
void ext2_dcache_remove (unsigned short dev, unsigned long dir,
const char * name, int len)
{
struct dir_cache_entry * p;
int queue; if (!cache_initialized)
init_cache ();
#ifdef EXT2FS_DEBUG_CACHE
printk ("dcache_remove (%04x, %lu, %s, %d)\n", dev, dir, name, len);
#endif
if (len > DCACHE_NAME_LEN)
return;
queue = hash (dev, dir);
if ((p = find_name (queue, dev, dir, name, len))) {
remove_from_cache (p);
remove_from_queue (queue, p);
p->next = first_free; //像使得结构无效一样，这里也设置成空闲的
first_free = p;
}
#ifdef EXT2FS_DEBUG_CACHE
show_cache ("dcache_remove");
#endif
} #endif
文档地址：http://blogimg.chinaunix.net/blog/upfile2/090525140659.pdf
*Created By: Prometheus
*Date : 2009-5-25
********************************************/ /*
* linux/fs/ext2/dcache.c
*
* Copyright (C) 1992, 1993, 1994 Remy Card ([email protected])
* Laboratoire MASI - Institut Blaise Pascal
* Universite Pierre et Marie Curie (Paris VI)
*
*/ /*
* dcache.c contains the code that handles the directory cache used by
* lookup() and readdir()
*/ //其实就只是两个双向链表的维护，看看数据结构的功底了 #include <asm/segment.h> #include <linux/fs.h>
#include <linux/ext2_fs.h>
#include <linux/string.h> #ifndef DONT_USE_DCACHE #define DCACHE_NAME_LEN 32 struct dir_cache_entry {
unsigned short dev;
unsigned long dir;
unsigned long ino;
char name[DCACHE_NAME_LEN + 1];
int len;
struct dir_cache_entry * queue_prev; //哈希表的双向链表（但是不循环）
struct dir_cache_entry * queue_next;
struct dir_cache_entry * prev; //所有结构的双向链表（但是不循环）
struct dir_cache_entry * next;
}; static struct dir_cache_entry * first = NULL;
static struct dir_cache_entry * last = NULL;
static struct dir_cache_entry * first_free = NULL;
static int cache_initialized = 0;
#ifdef EXT2FS_DEBUG_CACHE
static int hits = 0;
static int misses = 0;
#endif #define CACHE_SIZE 128 static struct dir_cache_entry dcache[CACHE_SIZE]; #define HASH_QUEUES 16 static struct dir_cache_entry * queue_head[HASH_QUEUES];
static struct dir_cache_entry * queue_tail[HASH_QUEUES]; //哈希算法
#define hash(dev,dir) ((dev ^ dir) % HASH_QUEUES) /*
* Initialize the cache
*/
static void init_cache (void)
{
int i; dcache[0].prev = NULL;
dcache[0].next = &dcache[1];
dcache[0].queue_next = dcache[0].queue_prev = NULL;
for (i = 1; i < CACHE_SIZE - 1; i++) {
dcache[i].prev = &dcache[i - 1];
dcache[i].next = &dcache[i + 1];
dcache[i].queue_next = dcache[i].queue_prev = NULL;
}
dcache[i].prev = &dcache[i - 1];
dcache[i].next = NULL;
dcache[i].queue_next = dcache[i].queue_prev = NULL;
first_free = &dcache[0];
for (i = 0; i < HASH_QUEUES; i++) //哈希表队列的头尾
queue_tail[i] = queue_head[i] = NULL;
cache_initialized = 1;
} /*
* Find a name in the cache
*/
//这里queue选择了哈希数组的入口项，而后面的很多信息都是进行核实的
//函数可以返回NULL
static struct dir_cache_entry * find_name (int queue, unsigned short dev,
unsigned long dir,
const char * name, int len)
{
struct dir_cache_entry * p; for (p = queue_head[queue]; p != NULL && (p->dev != dev ||
p->dir != dir || p->len != len ||
strncmp (name, p->name, p->len) != 0);
p = p->queue_next)
;
return p;
} #ifdef EXT2FS_DEBUG_CACHE
/*
* List the cache entries for debugging
*/
static void show_cache (const char * func_name)
{
struct dir_cache_entry * p; printk ("%s: cache status\n", func_name);
for (p = first; p != NULL; p = p->next)
printk ("dev:%04x, dir=%4lu, name=%s\n",
p->dev, p->dir, p->name);
}
#endif /*
* Add an entry at the beginning of the cache
*/
//将入口添加到队列的最前面，同时修改first和last
static void add_to_cache (struct dir_cache_entry * p)
{
p->prev = NULL;
p->next = first;
if (first)
first->prev = p;
if (!last)
last = p;
first = p;
} /*
* Add an entry at the beginning of a queue
*/
//将项添加到哈希队列中的最前面
static void add_to_queue (int queue, struct dir_cache_entry * p)
{
p->queue_prev = NULL;
p->queue_next = queue_head[queue];
if (queue_head[queue])
queue_head[queue]->queue_prev = p;
if (!queue_tail[queue])
queue_tail[queue] = p;
queue_head[queue] = p;
} /*
* Remove an entry from the cache
*/
static void remove_from_cache (struct dir_cache_entry * p)
{
if (p->prev)
p->prev->next = p->next;
else //否则就是在顶端了
first = p->next;
if (p->next)
p->next->prev = p->prev;
else //否则就是在尾端了
last = p->prev;
p->prev = NULL;
p->next = NULL;
} /*
* Remove an entry from a queue
*/
static void remove_from_queue (int queue, struct dir_cache_entry * p)
{
if (p->queue_prev)
p->queue_prev->queue_next = p->queue_next;
else
queue_head[queue] = p->queue_next;
if (p->queue_next)
p->queue_next->queue_prev = p->queue_prev;
else
queue_tail[queue] = p->queue_prev;
p->queue_prev = NULL;
p->queue_next = NULL;
} /*
* Invalidate all cache entries on a device (called by put_super() when
* a file system is unmounted)
*/
//使得制定设备上的所有的目录缓冲都失效（从队列中删除）
void ext2_dcache_invalidate (unsigned short dev)
{
struct dir_cache_entry * p;
struct dir_cache_entry * p2; if (!cache_initialized)
init_cache ();
for (p = first; p != NULL; p = p2) {
p2 = p->next; //这个是很常用的，先保存下一个要处理的东西
if (p->dev == dev) {
remove_from_cache (p);
remove_from_queue (hash (p->dev, p->dir), p);
p->next = first_free; //记录成空闲的
first_free = p;
}
}
#ifdef EXT2FS_DEBUG_CACHE
show_cache ("dcache_invalidate");
#endif
} /*
* Lookup a directory entry in the cache
*/
unsigned long ext2_dcache_lookup (unsigned short dev, unsigned long dir,
const char * name, int len)
{
char our_name[EXT2_NAME_LEN];
int queue;
struct dir_cache_entry * p; if (!cache_initialized)
init_cache ();
if (len > DCACHE_NAME_LEN)
return 0;
memcpy (our_name, (char *) name, len);
our_name[len] = '\0';
#ifdef EXT2FS_DEBUG_CACHE
printk ("dcache_lookup (%04x, %lu, %s, %d)\n", dev, dir, our_name, len);
#endif
queue = hash (dev, dir);
if ((p = find_name (queue, dev, dir, our_name, len))) {
//这个才是真正的查找函数，而本身函数只是注重后续数据结构完整性的处理
//这里将找到的放置到了最前面，可能是为了下次快速找到而这样的
if (p != first) {
remove_from_cache (p);
add_to_cache (p);
}
if (p != queue_head[queue]) {
remove_from_queue (queue, p);
add_to_queue (queue, p);
}
#ifdef EXT2FS_DEBUG_CACHE
hits++;
printk ("dcache_lookup: %s,hit,inode=%lu,hits=%d,misses=%d\n",
our_name, p->ino, hits, misses);
show_cache ("dcache_lookup");
#endif
return p->ino;
} else {
#ifdef EXT2FS_DEBUG_CACHE
misses++;
printk ("dcache_lookup: %s,miss,hits=%d,misses=%d\n",
our_name, hits, misses);
show_cache ("dcache_lookup");
#endif
return 0;
}
} /*
* Add a directory entry to the cache
*
* This function is called by ext2_lookup(), ext2_readdir()
* and the functions which create directory entries
*/
void ext2_dcache_add (unsigned short dev, unsigned long dir, const char * name,
int len, unsigned long ino)
{
struct dir_cache_entry * p;
int queue; if (!cache_initialized)
init_cache ();
#ifdef EXT2FS_DEBUG_CACHE
printk ("dcache_add (%04x, %lu, %s, %d, %lu)\n",
dev, dir, name, len, ino);
#endif
if (len > DCACHE_NAME_LEN)
return;
queue = hash (dev, dir);
if ((p = find_name (queue, dev, dir, name, len))) {
p->dir = dir;
p->ino = ino;
if (p != first) {
remove_from_cache (p);
add_to_cache (p);
}
if (p != queue_head[queue]) {
remove_from_queue (queue, p);
add_to_queue (queue, p);
}
} else { //这个标示制定的目录结构不在缓冲中，添加进去
if (first_free) {
p = first_free; //取出空闲的缓冲项
first_free = p->next;
} else { //这里说明没有现成的空闲的缓冲项了，直接取出队列的最后一项来
//存储这个目录信息
//一般来说，如果既没有空闲项也没有实际存在的项，便可能是数据结构出问题了
if (!last)
panic ("dcache_add: last == NULL\n");
else { //这里将最后一项(应该是最近最没有被命中的项)先从队列中取出
//注意取出要维持两个链表的哦
p = last;
last = p->prev;
if (last)
last->next = NULL;
remove_from_queue (hash (p->dev, p->dir), p);
}
}
p->dev = dev; //记录缓冲的信息
p->dir = dir;
p->ino = ino;
strncpy (p->name, name, len);
p->len = len;
p->name[len] = '\0';
add_to_cache (p);
add_to_queue (queue, p);
}
#ifdef EXT2FS_DEBUG_CACHE
show_cache ("dcache_add");
#endif
} /*
* Remove a directory from the cache
*
* This function is called by the functions which remove directory entries
*/
void ext2_dcache_remove (unsigned short dev, unsigned long dir,
const char * name, int len)
{
struct dir_cache_entry * p;
int queue; if (!cache_initialized)
init_cache ();
#ifdef EXT2FS_DEBUG_CACHE
printk ("dcache_remove (%04x, %lu, %s, %d)\n", dev, dir, name, len);
#endif
if (len > DCACHE_NAME_LEN)
return;
queue = hash (dev, dir);
if ((p = find_name (queue, dev, dir, name, len))) {
remove_from_cache (p);
remove_from_queue (queue, p);
p->next = first_free; //像使得结构无效一样，这里也设置成空闲的
first_free = p;
}
#ifdef EXT2FS_DEBUG_CACHE
show_cache ("dcache_remove");
#endif
} #endif
文档地址：http://blogimg.chinaunix.net/blog/upfile2/090525140659.pdf
相关阅读 更多 +
