linux 1.0 内核注解 linux/fs/ext2/dcache.c

taozhijiangscu

/********************************************
*Created By: Prometheus
*Date        : 2009-5-25   
********************************************/
/*
*  linux/fs/ext2/dcache.c
*
*  Copyright (C) 1992, 1993, 1994  Remy Card (
card@masi.ibp.fr
)
*                                  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
#include
#include
#include
#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
/*
* 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


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/90306/showart_1944103.html