catalog.c

嵌入式系统设计与实例开发实验教材二源码 多线程应用程序设计 串行端口程序设计 AD接口实验 CAN总线通信实验 GPS通信实验 Linux内核移植与编译实验 IC卡读写实验 SD驱动使

/*
 * linux/fs/hfs/catalog.c
 *
 * Copyright (C) 1995-1997  Paul H. Hargrove
 * This file may be distributed under the terms of the GNU General Public License.
 *
 * This file contains the functions related to the catalog B-tree.
 *
 * "XXX" in a comment is a note to myself to consider changing something.
 *
 * Cache code shamelessly stolen from 
 *     linux/fs/inode.c Copyright (C) 1991, 1992  Linus Torvalds
 *     re-shamelessly stolen Copyright (C) 1997 Linus Torvalds
 *
 * In function preconditions the term "valid" applied to a pointer to
 * a structure means that the pointer is non-NULL and the structure it
 * points to has all fields initialized to consistent values.
 *
 * The code in this file initializes some structures by calling
 * memset(&foo, 0, sizeof(foo)).  This produces the desired behavior
 * only due to the non-ANSI assumption that the machine representation
 */

#include "hfs.h"

/*================ Variable-like macros ================*/

/* Number of hash table slots */
#define C_HASHBITS  10
#define C_HASHSIZE  (1UL << C_HASHBITS)
#define C_HASHMASK  (C_HASHSIZE - 1)

/* Number of entries to fit in a single page on an i386.
 * Actually, now it's used to increment the free entry pool. */
#define CCACHE_INC (PAGE_SIZE/sizeof(struct hfs_cat_entry))
#define CCACHE_MAX (CCACHE_INC * 8)

/*================ File-local data types ================*/

/* The catalog record for a file */
typedef struct {
	hfs_byte_t	Flags;		/* Flags such as read-only */
	hfs_byte_t	Typ;		/* file version number = 0 */
	hfs_finfo_t	UsrWds;		/* data used by the Finder */
	hfs_lword_t	FlNum;		/* The CNID */
	hfs_word_t	StBlk;		/* obsolete */
	hfs_lword_t	LgLen;		/* The logical EOF of the data fork*/
	hfs_lword_t	PyLen;		/* The physical EOF of the data fork */
	hfs_word_t	RStBlk;		/* obsolete */
	hfs_lword_t	RLgLen;		/* The logical EOF of the rsrc fork */
	hfs_lword_t	RPyLen;		/* The physical EOF of the rsrc fork */
	hfs_lword_t	CrDat;		/* The creation date */
	hfs_lword_t	MdDat;		/* The modified date */
	hfs_lword_t	BkDat;		/* The last backup date */
	hfs_fxinfo_t	FndrInfo;	/* more data for the Finder */
	hfs_word_t	ClpSize;	/* number of bytes to allocate
					   when extending files */
	hfs_byte_t	ExtRec[12];	/* first extent record
					   for the data fork */
	hfs_byte_t	RExtRec[12];	/* first extent record
					   for the resource fork */
	hfs_lword_t	Resrv;		/* reserved by Apple */
} __attribute__((packed)) FIL_REC;

/* the catalog record for a directory */
typedef struct {
	hfs_word_t	Flags;		/* flags */
	hfs_word_t	Val;		/* Valence: number of files and
					   dirs in the directory */
	hfs_lword_t	DirID;		/* The CNID */
	hfs_lword_t	CrDat;		/* The creation date */
	hfs_lword_t	MdDat;		/* The modification date */
	hfs_lword_t	BkDat;		/* The last backup date */
	hfs_dinfo_t	UsrInfo;	/* data used by the Finder */
	hfs_dxinfo_t	FndrInfo;	/* more data used by Finder */
	hfs_byte_t	Resrv[16];	/* reserved by Apple */
} __attribute__((packed)) DIR_REC;

/* the catalog record for a thread */
typedef struct {
	hfs_byte_t		Reserv[8];	/* reserved by Apple */
	hfs_lword_t		ParID;		/* CNID of parent directory */
	struct hfs_name		CName;		/* The name of this entry */
}  __attribute__((packed)) THD_REC;

/* A catalog tree record */
struct hfs_cat_rec {
	hfs_byte_t		cdrType;	/* The type of entry */
	hfs_byte_t		cdrResrv2;	/* padding */
	union {
		FIL_REC fil;
		DIR_REC dir;
		THD_REC thd;
	} u;
} __attribute__((packed));

/*================ File-local variables ================*/
 
static LIST_HEAD(entry_in_use);
static LIST_HEAD(entry_unused);
static struct list_head hash_table[C_HASHSIZE];

static spinlock_t entry_lock = SPIN_LOCK_UNLOCKED;

static struct {
        int nr_entries;
        int nr_free_entries;
} entries_stat;

/*================ File-local functions ================*/

/*
 * brec_to_id
 *
 * Get the CNID from a brec
 */
static inline hfs_u32 brec_to_id(struct hfs_brec *brec)
{
	struct hfs_cat_rec *rec = brec->data;

	return hfs_get_nl((rec->cdrType==HFS_CDR_FIL) ?
				rec->u.fil.FlNum : rec->u.dir.DirID);
}

/*
 * hashfn()
 *
 * hash an (struct mdb *) and a (struct hfs_cat_key *) to an integer.
 */
static inline unsigned int hashfn(const struct hfs_mdb *mdb,
				  const struct hfs_cat_key *key)
{
	unsigned int hash;
	
	hash = (unsigned long) mdb | (unsigned long) key->ParID[3] | 
		hfs_strhash(key->CName.Name, key->CName.Len);
	hash = hash ^ (hash >> C_HASHBITS) ^ (hash >> C_HASHBITS*2);
	return hash & C_HASHMASK;
}

/*
 * hash()
 *
 * hash an (struct mdb *) and a (struct hfs_cat_key *)
 * to a pointer to a slot in the hash table.
 */
static inline struct list_head *hash(struct hfs_mdb *mdb,
				     const struct hfs_cat_key *key)
{
	return hash_table + hashfn(mdb, key);
}

static inline void insert_hash(struct hfs_cat_entry *entry)
{
	struct list_head *head = hash(entry->mdb, &entry->key);
	list_add(&entry->hash, head);
}

static inline void remove_hash(struct hfs_cat_entry *entry)
{
	list_del(&entry->hash);
	INIT_LIST_HEAD(&entry->hash);
}

/*
 * wait_on_entry()
 *
 * Sleep until a locked entry is unlocked.
 */
static inline void wait_on_entry(struct hfs_cat_entry * entry)
{
	while ((entry->state & HFS_LOCK)) {
		hfs_sleep_on(&entry->wait);
	}
}

/*
 * lock_entry()
 *
 * Obtain an exclusive lock on an entry.
 */
static void lock_entry(struct hfs_cat_entry * entry)
{
	wait_on_entry(entry);
	spin_lock(&entry_lock);
	entry->state |= HFS_LOCK;
	spin_unlock(&entry_lock);
}

/*
 * lock_entry()
 *
 * Relinquish an exclusive lock on an entry.
 */
static void unlock_entry(struct hfs_cat_entry * entry)
{
	spin_lock(&entry_lock);
	entry->state &= ~HFS_LOCK;
	spin_unlock(&entry_lock);
	hfs_wake_up(&entry->wait);
}

/* put entry on mdb dirty list. */
void hfs_cat_mark_dirty(struct hfs_cat_entry *entry)
{
        struct hfs_mdb *mdb = entry->mdb;

	spin_lock(&entry_lock);
	if (!(entry->state & HFS_DIRTY)) {
	        entry->state |= HFS_DIRTY;

		/* Only add valid (ie hashed) entries to the dirty list. */
		if (!list_empty(&entry->hash)) {
		        list_del(&entry->list);
			list_add(&entry->list, &mdb->entry_dirty);
		}
	}
	spin_unlock(&entry_lock);
}

/* delete an entry and remove it from the hash table. */
static void delete_entry(struct hfs_cat_entry *entry)
{
        if (!(entry->state & HFS_DELETED)) {
	        entry->state |= HFS_DELETED;
		list_del(&entry->hash);
		INIT_LIST_HEAD(&entry->hash);

	        if (entry->type == HFS_CDR_FIL) {
		  /* free all extents */
		  entry->u.file.data_fork.lsize = 0;
		  hfs_extent_adj(&entry->u.file.data_fork);
		  entry->u.file.rsrc_fork.lsize = 0;
		  hfs_extent_adj(&entry->u.file.rsrc_fork);
		}
	}
}


static inline void init_entry(struct hfs_cat_entry *entry)
{
	memset(entry, 0, sizeof(*entry));
	hfs_init_waitqueue(&entry->wait);
	INIT_LIST_HEAD(&entry->hash);
	INIT_LIST_HEAD(&entry->list);
}

/*
 * hfs_cat_alloc()
 *
 * Try to allocate another entry. 
 */
static inline struct hfs_cat_entry *hfs_cat_alloc(void)
{
        struct hfs_cat_entry *entry;

	if (!HFS_NEW(entry))
	        return NULL;

	init_entry(entry);
	return entry;
}

/* this gets called with the spinlock held. */
static int grow_entries(void)
{
        struct hfs_cat_entry *entry;
	int i;
	
	for (i = 0; i < CCACHE_INC; i++) {
	        if (!(entry = hfs_cat_alloc()))
		        break;
		list_add(&entry->list, &entry_unused);
	}

	entries_stat.nr_entries += i;
	entries_stat.nr_free_entries += i;
	        
	return i;
}

/*
 * __read_entry()
 *
 * Convert a (struct hfs_cat_rec) to a (struct hfs_cat_entry).
 */
static void __read_entry(struct hfs_cat_entry *entry,
			 const struct hfs_cat_rec *cat)
{
	entry->type = cat->cdrType;

	if (cat->cdrType == HFS_CDR_DIR) {
		struct hfs_dir *dir = &entry->u.dir;

		entry->cnid = hfs_get_nl(cat->u.dir.DirID);

		dir->magic = HFS_DIR_MAGIC;
		dir->flags = hfs_get_ns(cat->u.dir.Flags);
		memcpy(&entry->info.dir.dinfo, &cat->u.dir.UsrInfo, 16);
		memcpy(&entry->info.dir.dxinfo, &cat->u.dir.FndrInfo, 16);
		entry->create_date = hfs_get_nl(cat->u.dir.CrDat);
		entry->modify_date = hfs_get_nl(cat->u.dir.MdDat);
		entry->backup_date = hfs_get_nl(cat->u.dir.BkDat);
		dir->dirs = dir->files = 0;
		hfs_init_waitqueue(&dir->read_wait);
		hfs_init_waitqueue(&dir->write_wait);
	} else if (cat->cdrType == HFS_CDR_FIL) {
		struct hfs_file *fil = &entry->u.file;

		entry->cnid = hfs_get_nl(cat->u.fil.FlNum);

		fil->magic = HFS_FILE_MAGIC;

		fil->data_fork.fork = HFS_FK_DATA;
		fil->data_fork.entry = entry;
		fil->data_fork.lsize = hfs_get_hl(cat->u.fil.LgLen);
		fil->data_fork.psize = hfs_get_hl(cat->u.fil.PyLen) >>
						     HFS_SECTOR_SIZE_BITS;
		hfs_extent_in(&fil->data_fork, cat->u.fil.ExtRec);

		fil->rsrc_fork.fork = HFS_FK_RSRC;
		fil->rsrc_fork.entry = entry;
		fil->rsrc_fork.lsize = hfs_get_hl(cat->u.fil.RLgLen);
		fil->rsrc_fork.psize = hfs_get_hl(cat->u.fil.RPyLen) >>
						     HFS_SECTOR_SIZE_BITS;
		hfs_extent_in(&fil->rsrc_fork, cat->u.fil.RExtRec);

		memcpy(&entry->info.file.finfo, &cat->u.fil.UsrWds, 16);
		memcpy(&entry->info.file.fxinfo, &cat->u.fil.FndrInfo, 16);

		entry->create_date = hfs_get_nl(cat->u.fil.CrDat);
		entry->modify_date = hfs_get_nl(cat->u.fil.MdDat);
		entry->backup_date = hfs_get_nl(cat->u.fil.BkDat);
		fil->clumpablks = (hfs_get_hs(cat->u.fil.ClpSize)
					/ entry->mdb->alloc_blksz)
						>> HFS_SECTOR_SIZE_BITS;
		fil->flags = cat->u.fil.Flags;
	} else {
		hfs_warn("hfs_fs: entry is neither file nor directory!\n");
	}
}

/*
 * count_dir_entries()
 *
 * Count the number of files and directories in a given directory.
 */
static inline void count_dir_entries(struct hfs_cat_entry *entry,
				     struct hfs_brec *brec)
{
	int error = 0;
	hfs_u32 cnid;
	hfs_u8 type;

	if (!hfs_cat_open(entry, brec)) {
		while (!(error = hfs_cat_next(entry, brec, 1, &cnid, &type))) {
			if (type == HFS_CDR_FIL) {
				++entry->u.dir.files;
			} else if (type == HFS_CDR_DIR) {
				++entry->u.dir.dirs;
			}
		} /* -ENOENT is normal termination */
	}
	if (error != -ENOENT) {
		entry->cnid = 0;
	}
}

/*
 * read_entry()
 *
 * Convert a (struct hfs_brec) to a (struct hfs_cat_entry).
 */
static inline void read_entry(struct hfs_cat_entry *entry,
			      struct hfs_brec *brec)
{
	int need_count;
	struct hfs_cat_rec *rec = brec->data;

	__read_entry(entry, rec);

	need_count = (rec->cdrType == HFS_CDR_DIR) && rec->u.dir.Val;

	hfs_brec_relse(brec, NULL);

	if (need_count) {
		count_dir_entries(entry, brec);
	}
}

/*
 * __write_entry()
 *
 * Convert a (struct hfs_cat_entry) to a (struct hfs_cat_rec).
 */
static void __write_entry(const struct hfs_cat_entry *entry,
			  struct hfs_cat_rec *cat)
{
	if (entry->type == HFS_CDR_DIR) {
		const struct hfs_dir *dir = &entry->u.dir;

		hfs_put_ns(dir->flags,             cat->u.dir.Flags);
		hfs_put_hs(dir->dirs + dir->files, cat->u.dir.Val);
		hfs_put_nl(entry->cnid,            cat->u.dir.DirID);
		hfs_put_nl(entry->create_date,     cat->u.dir.CrDat);
		hfs_put_nl(entry->modify_date,     cat->u.dir.MdDat);
		hfs_put_nl(entry->backup_date,     cat->u.dir.BkDat);
		memcpy(&cat->u.dir.UsrInfo, &entry->info.dir.dinfo, 16);
		memcpy(&cat->u.dir.FndrInfo, &entry->info.dir.dxinfo, 16);
	} else if (entry->type == HFS_CDR_FIL) {
		const struct hfs_file *fil = &entry->u.file;

		cat->u.fil.Flags = fil->flags;
		hfs_put_nl(entry->cnid,            cat->u.fil.FlNum);
		memcpy(&cat->u.fil.UsrWds, &entry->info.file.finfo, 16);
		hfs_put_hl(fil->data_fork.lsize, cat->u.fil.LgLen);
		hfs_put_hl(fil->data_fork.psize << HFS_SECTOR_SIZE_BITS,
 							cat->u.fil.PyLen);
		hfs_put_hl(fil->rsrc_fork.lsize, cat->u.fil.RLgLen);
		hfs_put_hl(fil->rsrc_fork.psize << HFS_SECTOR_SIZE_BITS,
 							cat->u.fil.RPyLen);
		hfs_put_nl(entry->create_date,     cat->u.fil.CrDat);
		hfs_put_nl(entry->modify_date,     cat->u.fil.MdDat);
		hfs_put_nl(entry->backup_date,     cat->u.fil.BkDat);
		memcpy(&cat->u.fil.FndrInfo, &entry->info.file.fxinfo, 16);
		hfs_put_hs((fil->clumpablks * entry->mdb->alloc_blksz)
				<< HFS_SECTOR_SIZE_BITS, cat->u.fil.ClpSize);
		hfs_extent_out(&fil->data_fork, cat->u.fil.ExtRec);
		hfs_extent_out(&fil->rsrc_fork, cat->u.fil.RExtRec);
	} else {
		hfs_warn("__write_entry: invalid entry\n");
	}
}

/*
 * write_entry()
 *
 * Write a modified entry back to the catalog B-tree. this gets called
 * with the entry locked.
 */
static void write_entry(struct hfs_cat_entry * entry)
{
	struct hfs_brec brec;
	int error;

	if (!(entry->state & HFS_DELETED)) {
		error = hfs_bfind(&brec, entry->mdb->cat_tree,
				  HFS_BKEY(&entry->key), HFS_BFIND_WRITE);
		if (!error) {
			if ((entry->state & HFS_KEYDIRTY)) {
				/* key may have changed case due to a rename */
				entry->state &= ~HFS_KEYDIRTY;
				if (brec.key->KeyLen != entry->key.KeyLen) {
					hfs_warn("hfs_write_entry: key length "
						 "changed!\n");
					error = 1;
				} else {
					memcpy(brec.key, &entry->key,
					       entry->key.KeyLen);
				}
			} else if (entry->cnid != brec_to_id(&brec)) {
				hfs_warn("hfs_write_entry: CNID "
					 "changed unexpectedly!\n");
				error = 1;
			}
			if (!error) {
				__write_entry(entry, brec.data);
			}
			hfs_brec_relse(&brec, NULL);
		}
		if (error) {
			hfs_warn("hfs_write_entry: unable to write "
				 "entry %08x\n", entry->cnid);
		}
	}
}


/* this gets called with the spinlock held. */
static struct hfs_cat_entry *find_entry(struct hfs_mdb *mdb,
					const struct hfs_cat_key *key)
{
	struct list_head *tmp, *head = hash(mdb, key);
	struct hfs_cat_entry * entry;

	tmp = head;
	for (;;) {
		tmp = tmp->next;
		entry = NULL;
		if (tmp == head)
			break;
		entry = list_entry(tmp, struct hfs_cat_entry, hash);
		if (entry->mdb != mdb)
			continue;
		if (hfs_cat_compare(&entry->key, key)) {
			continue;
		}
		entry->count++;
		break;
	}

	return entry;
}


/* be careful. this gets called with the spinlock held. */
static struct hfs_cat_entry *get_new_entry(struct hfs_mdb *mdb,
					   const struct hfs_cat_key *key,
					   const int read)
{
	struct hfs_cat_entry *entry;
	struct list_head *head = hash(mdb, key);
	struct list_head *tmp;

add_new_entry:
	tmp = entry_unused.next;
	if ((tmp != &entry_unused) ) {
		list_del(tmp);
		entries_stat.nr_free_entries--;
		entry = list_entry(tmp, struct hfs_cat_entry, list);
		list_add(&entry->list, &entry_in_use);
		list_add(&entry->hash, head);
		entry->mdb = mdb;
		entry->count = 1;
		memcpy(&entry->key, key, sizeof(*key));
		entry->state = HFS_LOCK;
		spin_unlock(&entry_lock);

		if (read) {
		   struct hfs_brec brec;