Viewing file:  catalog.c (39.37 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
/*
* 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;
if (hfs_bfind(&brec, mdb->cat_tree,
HFS_BKEY(key), HFS_BFIND_READ_EQ)) {
/* uh oh. we failed to read the record.
* the entry doesn't actually exist. */
goto read_fail;
}
read_entry(entry, &brec);
/* error */
if (!entry->cnid) {
goto read_fail;
}
/* we don't have to acquire a spinlock here or
* below for the unlocking bits as we're the first
* user of this entry. */
entry->state &= ~HFS_LOCK;
hfs_wake_up(&entry->wait);
}
return entry;
}
/* try to allocate more entries. grow_entries() doesn't release
* the spinlock. */
if (grow_entries())
goto add_new_entry;
spin_unlock(&entry_lock);
return NULL;
read_fail:
/* short-cut hfs_cat_put by doing everything here. */
spin_lock(&entry_lock);
list_del(&entry->hash);
list_del(&entry->list);
init_entry(entry);
list_add(&entry->list, &entry_unused);
entries_stat.nr_free_entries++;
spin_unlock(&entry_lock);
return NULL;
}
/*
* get_entry()
*
* Try to return an entry for the indicated file or directory.
* If ('read' == 0) then no attempt will be made to read it from disk
* and a locked, but uninitialized, entry is returned.
*/
static struct hfs_cat_entry *get_entry(struct hfs_mdb *mdb,
const struct hfs_cat_key *key,
const int read)
{
struct hfs_cat_entry * entry;
#if defined(DEBUG_CATALOG) || defined(DEBUG_ALL)
hfs_warn("hfs_get_entry: mdb=%p key=%s read=%d\n",
mdb, key->CName.Name, read);
#endif
spin_lock(&entry_lock);
entry = find_entry(mdb, key);
if (!entry) {
return get_new_entry(mdb, key, read);
}
spin_unlock(&entry_lock);
wait_on_entry(entry);
return entry;
}
/*
* new_cnid()
*
* Allocate a CNID to use for a new file or directory.
*/
static inline hfs_u32 new_cnid(struct hfs_mdb *mdb)
{
/* If the create succeeds then the mdb will get dirtied */
return htonl(mdb->next_id++);
}
/*
* update_dir()
*
* Update counts, times and dirt on a changed directory
*/
static void update_dir(struct hfs_mdb *mdb, struct hfs_cat_entry *dir,
int is_dir, int count)
{
/* update counts */
if (is_dir) {
mdb->dir_count += count;
dir->u.dir.dirs += count;
if (dir->cnid == htonl(HFS_ROOT_CNID)) {
mdb->root_dirs += count;
}
} else {
mdb->file_count += count;
dir->u.dir.files += count;
if (dir->cnid == htonl(HFS_ROOT_CNID)) {
mdb->root_files += count;
}
}
/* update times and dirt */
dir->modify_date = hfs_time();
hfs_cat_mark_dirty(dir);
}
/*
* Add a writer to dir, excluding readers.
*
* XXX: this is wrong. it allows a move to occur when a directory
* is being written to.
*/
static inline void start_write(struct hfs_cat_entry *dir)
{
if (dir->u.dir.readers || waitqueue_active(&dir->u.dir.read_wait)) {
hfs_sleep_on(&dir->u.dir.write_wait);
}
++dir->u.dir.writers;
}
/*
* Add a reader to dir, excluding writers.
*/
static inline void start_read(struct hfs_cat_entry *dir)
{
if (dir->u.dir.writers || waitqueue_active(&dir->u.dir.write_wait)) {
hfs_sleep_on(&dir->u.dir.read_wait);
}
++dir->u.dir.readers;
}
/*
* Remove a writer from dir, possibly admitting readers.
*/
static inline void end_write(struct hfs_cat_entry *dir)
{
if (!(--dir->u.dir.writers)) {
hfs_wake_up(&dir->u.dir.read_wait);
}
}
/*
* Remove a reader from dir, possibly admitting writers.
*/
static inline void end_read(struct hfs_cat_entry *dir)
{
if (!(--dir->u.dir.readers)) {
hfs_wake_up(&dir->u.dir.write_wait);
}
}
/*
* create_entry()
*
* Add a new file or directory to the catalog B-tree and
* return a (struct hfs_cat_entry) for it in '*result'.
*/
static int create_entry(struct hfs_cat_entry *parent, struct hfs_cat_key *key,
const struct hfs_cat_rec *record, int is_dir,
hfs_u32 cnid, struct hfs_cat_entry **result)
{
struct hfs_mdb *mdb = parent->mdb;
struct hfs_cat_entry *entry;
struct hfs_cat_key thd_key;
struct hfs_cat_rec thd_rec;
int error, has_thread;
if (result) {
*result = NULL;
}
/* keep readers from getting confused by changing dir size */
start_write(parent);
/* create a locked entry in the cache */
entry = get_entry(mdb, key, 0);
if (!entry) {
/* The entry exists but can't be read */
error = -EIO;
goto done;
}
if (entry->cnid) {
/* The (unlocked) entry exists in the cache */
error = -EEXIST;
goto bail2;
}
/* limit directory valence to signed 16-bit integer */
if ((parent->u.dir.dirs + parent->u.dir.files) >= HFS_MAX_VALENCE) {
error = -ENOSPC;
goto bail1;
}
has_thread = is_dir || (record->u.fil.Flags & HFS_FIL_THD);
if (has_thread) {
/* init some fields for the thread record */
memset(&thd_rec, 0, sizeof(thd_rec));
thd_rec.cdrType = is_dir ? HFS_CDR_THD : HFS_CDR_FTH;
memcpy(&thd_rec.u.thd.ParID, &key->ParID,
sizeof(hfs_u32) + sizeof(struct hfs_name));
/* insert the thread record */
hfs_cat_build_key(cnid, NULL, &thd_key);
error = hfs_binsert(mdb->cat_tree, HFS_BKEY(&thd_key),
&thd_rec, 2 + sizeof(THD_REC));
if (error) {
goto bail1;
}
}
/* insert the record */
error = hfs_binsert(mdb->cat_tree, HFS_BKEY(key), record,
is_dir ? 2 + sizeof(DIR_REC) :
2 + sizeof(FIL_REC));
if (error) {
if (has_thread && (error != -EIO)) {
/* at least TRY to remove the thread record */
(void)hfs_bdelete(mdb->cat_tree, HFS_BKEY(&thd_key));
}
goto bail1;
}
/* update the parent directory */
update_dir(mdb, parent, is_dir, 1);
/* complete the cache entry and return success */
__read_entry(entry, record);
unlock_entry(entry);
if (result) {
*result = entry;
} else {
hfs_cat_put(entry);
}
goto done;
bail1:
/* entry really didn't exist, so we don't need to really delete it.
* we do need to remove it from the hash, though. */
entry->state |= HFS_DELETED;
remove_hash(entry);
unlock_entry(entry);
bail2:
hfs_cat_put(entry);
done:
end_write(parent);
return error;
}
/*================ Global functions ================*/
/*
* hfs_cat_put()
*
* Release an entry we aren't using anymore.
*
* nothing in hfs_cat_put goes to sleep now except on the initial entry.
*/
void hfs_cat_put(struct hfs_cat_entry * entry)
{
if (entry) {
wait_on_entry(entry);
/* just in case. this should never happen. */
if (!entry->count) {
hfs_warn("hfs_cat_put: trying to free free entry: %p\n",
entry);
return;
}
#if defined(DEBUG_CATALOG) || defined(DEBUG_ALL)
hfs_warn("hfs_cat_put: %p(%u) type=%d state=%lu\n",
entry, entry->count, entry->type, entry->state);
#endif
spin_lock(&entry_lock);
if (!--entry->count) {
if ((entry->state & HFS_DELETED))
goto entry_deleted;
if ((entry->type == HFS_CDR_FIL)) {
/* clear out any cached extents */
if (entry->u.file.data_fork.first.next) {
hfs_extent_free(&entry->u.file.data_fork);
}
if (entry->u.file.rsrc_fork.first.next) {
hfs_extent_free(&entry->u.file.rsrc_fork);
}
}
/* if we put a dirty entry, write it out. */
if ((entry->state & HFS_DIRTY)) {
entry->state ^= HFS_DIRTY | HFS_LOCK;
write_entry(entry);
entry->state &= ~HFS_LOCK;
}
list_del(&entry->hash);
entry_deleted: /* deleted entries have already been removed
* from the hash list. */
list_del(&entry->list);
if (entries_stat.nr_free_entries > CCACHE_MAX) {
HFS_DELETE(entry);
entries_stat.nr_entries--;
} else {
init_entry(entry);
list_add(&entry->list, &entry_unused);
entries_stat.nr_free_entries++;
}
}
spin_unlock(&entry_lock);
}
}
/*
* hfs_cat_get()
*
* Wrapper for get_entry() which always calls with ('read'==1).
* Used for access to get_entry() from outside this file.
*/
struct hfs_cat_entry *hfs_cat_get(struct hfs_mdb *mdb,
const struct hfs_cat_key *key)
{
return get_entry(mdb, key, 1);
}
/* invalidate all entries for a device */
static void invalidate_list(struct list_head *head, struct hfs_mdb *mdb,
struct list_head *dispose)
{
struct list_head *next;
next = head->next;
for (;;) {
struct list_head *tmp = next;
struct hfs_cat_entry * entry;
next = next->next;
if (tmp == head)
break;
entry = list_entry(tmp, struct hfs_cat_entry, list);
if (entry->mdb != mdb) {
continue;
}
if (!entry->count) {
list_del(&entry->hash);
INIT_LIST_HEAD(&entry->hash);
list_del(&entry->list);
list_add(&entry->list, dispose);
continue;
}
hfs_warn("hfs_fs: entry %p(%u) busy on removed device %s.\n",
entry, entry->count,
hfs_mdb_name(entry->mdb->sys_mdb));
}
}
/* delete entries from a list */
static void delete_list(struct list_head *head)
{
struct list_head *next = head->next;
struct hfs_cat_entry *entry;
for (;;) {
struct list_head * tmp = next;
next = next->next;
if (tmp == head) {
break;
}
entry = list_entry(tmp, struct hfs_cat_entry, list);
HFS_DELETE(entry);
}
}
/*
* hfs_cat_invalidate()
*
* Called by hfs_mdb_put() to remove all the entries
* in the cache that are associated with a given MDB.
*/
void hfs_cat_invalidate(struct hfs_mdb *mdb)
{
LIST_HEAD(throw_away);
spin_lock(&entry_lock);
invalidate_list(&entry_in_use, mdb, &throw_away);
invalidate_list(&mdb->entry_dirty, mdb, &throw_away);
spin_unlock(&entry_lock);
delete_list(&throw_away);
#if defined(DEBUG_CATALOG) || defined(DEBUG_ALL)
hfs_warn("hfs_cat_invalidate: free=%d total=%d\n",
entries_stat.nr_free_entries,
entries_stat.nr_entries);
#endif
}
/*
* hfs_cat_commit()
*
* Called by hfs_mdb_commit() to write dirty entries to the disk buffers.
*/
void hfs_cat_commit(struct hfs_mdb *mdb)
{
struct list_head *tmp, *head = &mdb->entry_dirty;
struct hfs_cat_entry *entry;
spin_lock(&entry_lock);
while ((tmp = head->prev) != head) {
entry = list_entry(tmp, struct hfs_cat_entry, list);
if ((entry->state & HFS_LOCK)) {
spin_unlock(&entry_lock);
wait_on_entry(entry);
spin_lock(&entry_lock);
} else {
struct list_head *insert = &entry_in_use;
if (!entry->count)
insert = entry_in_use.prev;
/* add to in_use list */
list_del(&entry->list);
list_add(&entry->list, insert);
/* reset DIRTY, set LOCK */
entry->state ^= HFS_DIRTY | HFS_LOCK;
spin_unlock(&entry_lock);
write_entry(entry);
spin_lock(&entry_lock);
entry->state &= ~HFS_LOCK;
hfs_wake_up(&entry->wait);
}
}
spin_unlock(&entry_lock);
}
/*
* hfs_cat_free()
*
* Releases all the memory allocated in grow_entries().
* Must call hfs_cat_invalidate() on all MDBs before calling this.
* This only gets rid of the unused pool of entries. all the other
* entry references should have either been freed by cat_invalidate
* or moved onto the unused list.
*/
void hfs_cat_free(void)
{
delete_list(&entry_unused);
}
/*
* hfs_cat_compare()
*
* Description:
* This is the comparison function used for the catalog B-tree. In
* comparing catalog B-tree entries, the parent id is the most
* significant field (compared as unsigned ints). The name field is
* the least significant (compared in "Macintosh lexical order",
* see hfs_strcmp() in string.c)
* Input Variable(s):
* struct hfs_cat_key *key1: pointer to the first key to compare
* struct hfs_cat_key *key2: pointer to the second key to compare
* Output Variable(s):
* NONE
* Returns:
* int: negative if key1<key2, positive if key1>key2, and 0 if key1==key2
* Preconditions:
* key1 and key2 point to "valid" (struct hfs_cat_key)s.
* Postconditions:
* This function has no side-effects
*/
int hfs_cat_compare(const struct hfs_cat_key *key1,
const struct hfs_cat_key *key2)
{
unsigned int parents;
int retval;
parents = hfs_get_hl(key1->ParID) - hfs_get_hl(key2->ParID);
if (parents != 0) {
retval = (int)parents;
} else {
retval = hfs_strcmp(key1->CName.Name, key1->CName.Len,
key2->CName.Name, key2->CName.Len);
}
return retval;
}
/*
* hfs_cat_build_key()
*
* Given the ID of the parent and the name build a search key.
*/
void hfs_cat_build_key(hfs_u32 parent, const struct hfs_name *cname,
struct hfs_cat_key *key)
{
hfs_put_nl(parent, key->ParID);
if (cname) {
key->KeyLen = 6 + cname->Len;
memcpy(&key->CName, cname, sizeof(*cname));
} else {
key->KeyLen = 6;
memset(&key->CName, 0, sizeof(*cname));
}
}
/*
* hfs_cat_open()
*
* Given a directory on an HFS filesystem get its thread and
* lock the directory against insertions and deletions.
* Return 0 on success or an error code on failure.
*/
int hfs_cat_open(struct hfs_cat_entry *dir, struct hfs_brec *brec)
{
struct hfs_cat_key key;
int error;
if (dir->type != HFS_CDR_DIR) {
return -EINVAL;
}
/* Block writers */
start_read(dir);
/* Find the directory */
hfs_cat_build_key(dir->cnid, NULL, &key);
error = hfs_bfind(brec, dir->mdb->cat_tree,
HFS_BKEY(&key), HFS_BFIND_READ_EQ);
if (error) {
end_read(dir);
}
return error;
}
/*
* hfs_cat_next()
*
* Given a catalog brec structure, replace it with the count'th next brec
* in the same directory.
* Return an error code if there is a problem, 0 if OK.
* Note that an error code of -ENOENT means there are no more entries
* in this directory.
* The directory is "closed" on an error.
*/
int hfs_cat_next(struct hfs_cat_entry *dir, struct hfs_brec *brec,
hfs_u16 count, hfs_u32 *cnid, hfs_u8 *type)
{
int error;
if (!dir || !brec) {
return -EINVAL;
}
/* Get the count'th next catalog tree entry */
error = hfs_bsucc(brec, count);
if (!error) {
struct hfs_cat_key *key = (struct hfs_cat_key *)brec->key;
if (hfs_get_nl(key->ParID) != dir->cnid) {
hfs_brec_relse(brec, NULL);
error = -ENOENT;
}
}
if (!error) {
*type = ((struct hfs_cat_rec *)brec->data)->cdrType;
*cnid = brec_to_id(brec);
} else {
end_read(dir);
}
return error;
}
/*
* hfs_cat_close()
*
* Given a catalog brec structure, replace it with the count'th next brec
* in the same directory.
* Return an error code if there is a problem, 0 if OK.
* Note that an error code of -ENOENT means there are no more entries
* in this directory.
*/
void hfs_cat_close(struct hfs_cat_entry *dir, struct hfs_brec *brec)
{
if (dir && brec) {
hfs_brec_relse(brec, NULL);
end_read(dir);
}
}
/*
* hfs_cat_parent()
*
* Given a catalog entry, return the entry for its parent.
* Uses catalog key for the entry to get its parent's ID
* and then uses the parent's thread record to locate the
* parent's actual catalog entry.
*/
struct hfs_cat_entry *hfs_cat_parent(struct hfs_cat_entry *entry)
{
struct hfs_cat_entry *retval = NULL;
struct hfs_mdb *mdb = entry->mdb;
struct hfs_brec brec;
struct hfs_cat_key key;
int error;
lock_entry(entry);
if (!(entry->state & HFS_DELETED)) {
hfs_cat_build_key(hfs_get_nl(entry->key.ParID), NULL, &key);
error = hfs_bfind(&brec, mdb->cat_tree,
HFS_BKEY(&key), HFS_BFIND_READ_EQ);
if (!error) {
/* convert thread record to key */
struct hfs_cat_rec *rec = brec.data;
key.KeyLen = 6 + rec->u.thd.CName.Len;
memcpy(&key.ParID, &rec->u.thd.ParID,
sizeof(hfs_u32) + sizeof(struct hfs_name));
hfs_brec_relse(&brec, NULL);
retval = hfs_cat_get(mdb, &key);
}
}
unlock_entry(entry);
return retval;
}
/*
* hfs_cat_create()
*
* Create a new file with the indicated name in the indicated directory.
* The file will have the indicated flags, type and creator.
* If successful an (struct hfs_cat_entry) is returned in '*result'.
*/
int hfs_cat_create(struct hfs_cat_entry *parent, struct hfs_cat_key *key,
hfs_u8 flags, hfs_u32 type, hfs_u32 creator,
struct hfs_cat_entry **result)
{
struct hfs_cat_rec record;
hfs_u32 id = new_cnid(parent->mdb);
hfs_u32 mtime = hfs_time();
#if defined(DEBUG_CATALOG) || defined(DEBUG_ALL)
hfs_warn("hfs_cat_create: %p/%s flags=%d res=%p\n",
parent, key->CName.Name, flags, result);
#endif
/* init some fields for the file record */
memset(&record, 0, sizeof(record));
record.cdrType = HFS_CDR_FIL;
record.u.fil.Flags = flags | HFS_FIL_USED;
hfs_put_nl(id, record.u.fil.FlNum);
hfs_put_nl(mtime, record.u.fil.CrDat);
hfs_put_nl(mtime, record.u.fil.MdDat);
hfs_put_nl(0, record.u.fil.BkDat);
hfs_put_nl(type, record.u.fil.UsrWds.fdType);
hfs_put_nl(creator, record.u.fil.UsrWds.fdCreator);
return create_entry(parent, key, &record, 0, id, result);
}
/*
* hfs_cat_mkdir()
*
* Create a new directory with the indicated name in the indicated directory.
* If successful an (struct hfs_cat_entry) is returned in '*result'.
*/
int hfs_cat_mkdir(struct hfs_cat_entry *parent, struct hfs_cat_key *key,
struct hfs_cat_entry **result)
{
struct hfs_cat_rec record;
hfs_u32 id = new_cnid(parent->mdb);
hfs_u32 mtime = hfs_time();
#if defined(DEBUG_CATALOG) || defined(DEBUG_ALL)
hfs_warn("hfs_cat_mkdir: %p/%s res=%p\n", parent, key->CName.Name,
result);
#endif
/* init some fields for the directory record */
memset(&record, 0, sizeof(record));
record.cdrType = HFS_CDR_DIR;
hfs_put_nl(id, record.u.dir.DirID);
hfs_put_nl(mtime, record.u.dir.CrDat);
hfs_put_nl(mtime, record.u.dir.MdDat);
hfs_put_nl(0, record.u.dir.BkDat);
hfs_put_hs(0xff, record.u.dir.UsrInfo.frView);
return create_entry(parent, key, &record, 1, id, result);
}
/*
* hfs_cat_delete()
*
* Delete the indicated file or directory.
* The associated thread is also removed unless ('with_thread'==0).
*/
int hfs_cat_delete(struct hfs_cat_entry *parent, struct hfs_cat_entry *entry,
int with_thread)
{
struct hfs_cat_key key;
struct hfs_mdb *mdb = parent->mdb;
int is_dir, error = 0;
#if defined(DEBUG_CATALOG) || defined(DEBUG_ALL)
hfs_warn("hfs_cat_delete: %p/%p type=%d state=%lu, thread=%d\n",
parent, entry, entry->type, entry->state, with_thread);
#endif
if (parent->mdb != entry->mdb) {
return -EINVAL;
}
if (entry->type == HFS_CDR_FIL) {
with_thread = (entry->u.file.flags&HFS_FIL_THD) && with_thread;
is_dir = 0;
} else {
is_dir = 1;
}
/* keep readers from getting confused by changing dir size */
start_write(parent);
/* don't delete a busy directory */
if (entry->type == HFS_CDR_DIR) {
start_read(entry);
error = -ENOTEMPTY;
if (entry->u.dir.files || entry->u.dir.dirs)
goto hfs_delete_end;
}
/* try to delete the file or directory */
lock_entry(entry);
error = -ENOENT;
if ((entry->state & HFS_DELETED)) {
/* somebody beat us to it. */
goto hfs_delete_unlock;
}
/* delete the catalog record */
if ((error = hfs_bdelete(mdb->cat_tree, HFS_BKEY(&entry->key)))) {
goto hfs_delete_unlock;
}
/* Mark the entry deleted and remove it from the cache */
delete_entry(entry);
/* try to delete the thread entry if it exists */
if (with_thread) {
hfs_cat_build_key(entry->cnid, NULL, &key);
(void)hfs_bdelete(mdb->cat_tree, HFS_BKEY(&key));
}
update_dir(mdb, parent, is_dir, -1);
hfs_delete_unlock:
unlock_entry(entry);
hfs_delete_end:
if (entry->type == HFS_CDR_DIR) {
end_read(entry);
}
end_write(parent);
return error;
}
/*
* hfs_cat_move()
*
* Rename a file or directory, possibly to a new directory.
* If the destination exists it is removed and a
* (struct hfs_cat_entry) for it is returned in '*result'.
*/
int hfs_cat_move(struct hfs_cat_entry *old_dir, struct hfs_cat_entry *new_dir,
struct hfs_cat_entry *entry, struct hfs_cat_key *new_key,
struct hfs_cat_entry **removed)
{
struct hfs_cat_entry *dest;
struct hfs_mdb *mdb;
int error = 0;
int is_dir, has_thread;
if (removed) {
*removed = NULL;
}
/* sanity checks */
if (!old_dir || !new_dir) {
return -EINVAL;
}
mdb = old_dir->mdb;
if (mdb != new_dir->mdb) {
return -EXDEV;
}
/* precompute a few things */
if (entry->type == HFS_CDR_DIR) {
is_dir = 1;
has_thread = 1;
} else if (entry->type == HFS_CDR_FIL) {
is_dir = 0;
has_thread = entry->u.file.flags & HFS_FIL_THD;
} else {
return -EINVAL;
}
while (mdb->rename_lock) {
hfs_sleep_on(&mdb->rename_wait);
}
spin_lock(&entry_lock);
mdb->rename_lock = 1; /* XXX: should be atomic_inc */
spin_unlock(&entry_lock);
/* keep readers from getting confused by changing dir size */
start_write(new_dir);
if (old_dir != new_dir) {
start_write(old_dir);
}
/* Don't move a directory inside itself */
if (is_dir) {
struct hfs_cat_key thd_key;
struct hfs_brec brec;
hfs_u32 id = new_dir->cnid;
while (id != htonl(HFS_ROOT_CNID)) {
if (id == entry->cnid) {
error = -EINVAL;
} else {
hfs_cat_build_key(id, NULL, &thd_key);
error = hfs_bfind(&brec, mdb->cat_tree,
HFS_BKEY(&thd_key),
HFS_BFIND_READ_EQ);
}
if (error) {
goto done;
} else {
struct hfs_cat_rec *rec = brec.data;
id = hfs_get_nl(rec->u.thd.ParID);
hfs_brec_relse(&brec, NULL);
}
}
}
restart:
/* see if the destination exists, getting it if it does */
dest = hfs_cat_get(mdb, new_key);
if (!dest) {
/* destination doesn't exist, so create it */
struct hfs_cat_rec new_record;
/* create a locked entry in the cache */
dest = get_entry(mdb, new_key, 0);
if (!dest) {
error = -EIO;
goto done;
}
if (dest->cnid) {
/* The (unlocked) entry exists in the cache */
goto have_distinct;
}
/* limit directory valence to signed 16-bit integer */
if ((new_dir->u.dir.dirs + new_dir->u.dir.files) >=
HFS_MAX_VALENCE) {
error = -ENOSPC;
goto bail3;
}
/* build the new record. make sure to zero out the
record. */
memset(&new_record, 0, sizeof(new_record));
new_record.cdrType = entry->type;
__write_entry(entry, &new_record);
/* insert the new record */
error = hfs_binsert(mdb->cat_tree, HFS_BKEY(new_key),
&new_record, is_dir ? 2 + sizeof(DIR_REC) :
2 + sizeof(FIL_REC));
if (error == -EEXIST) {
delete_entry(dest);
unlock_entry(dest);
hfs_cat_put(dest);
goto restart;
} else if (error) {
goto bail3;
}
/* update the destination directory */
update_dir(mdb, new_dir, is_dir, 1);
} else if (entry != dest) {
have_distinct:
/* The destination exists and is not same as source */
lock_entry(dest);
if ((dest->state & HFS_DELETED)) {
unlock_entry(dest);
hfs_cat_put(dest);
goto restart;
}
if (dest->type != entry->type) {
/* can't move a file on top
of a dir nor vice versa. */
error = is_dir ? -ENOTDIR : -EISDIR;
} else if (is_dir && (dest->u.dir.dirs || dest->u.dir.files)) {
/* directory to replace is not empty */
error = -ENOTEMPTY;
}
if (error) {
goto bail2;
}
} else {
/* The destination exists but is same as source */
--entry->count;
dest = NULL;
}
/* lock the entry */
lock_entry(entry);
if ((entry->state & HFS_DELETED)) {
error = -ENOENT;
goto bail1;
}
if (dest) {
/* remove the old entry */
error = hfs_bdelete(mdb->cat_tree, HFS_BKEY(&entry->key));
if (error) {
/* We couldn't remove the entry for the
original file, so nothing has changed. */
goto bail1;
}
update_dir(mdb, old_dir, is_dir, -1);
}
/* update the thread of the dir/file we're moving */
if (has_thread) {
struct hfs_cat_key thd_key;
struct hfs_brec brec;
hfs_cat_build_key(entry->cnid, NULL, &thd_key);
error = hfs_bfind(&brec, mdb->cat_tree,
HFS_BKEY(&thd_key), HFS_BFIND_WRITE);
if (error == -ENOENT) {
if (is_dir) {
/* directory w/o a thread! */
error = -EIO;
} else {
/* We were lied to! */
entry->u.file.flags &= ~HFS_FIL_THD;
hfs_cat_mark_dirty(entry);
}
}
if (!error) {
struct hfs_cat_rec *rec = brec.data;
memcpy(&rec->u.thd.ParID, &new_key->ParID,
sizeof(hfs_u32) + sizeof(struct hfs_name));
hfs_brec_relse(&brec, NULL);
} else if (error == -ENOENT) {
error = 0;
} else if (!dest) {
/* Nothing was changed */
unlock_entry(entry);
goto done;
} else {
/* Something went seriously wrong.
The dir/file has been deleted. */
/* XXX try some recovery? */
delete_entry(entry);
goto bail1;
}
}
/* TRY to remove the thread for the pre-existing entry */
if (dest && dest->cnid &&
(is_dir || (dest->u.file.flags & HFS_FIL_THD))) {
struct hfs_cat_key thd_key;
hfs_cat_build_key(dest->cnid, NULL, &thd_key);
(void)hfs_bdelete(mdb->cat_tree, HFS_BKEY(&thd_key));
}
/* update directories */
new_dir->modify_date = hfs_time();
hfs_cat_mark_dirty(new_dir);
/* update key */
remove_hash(entry);
memcpy(&entry->key, new_key, sizeof(*new_key));
/* KEYDIRTY as case might differ */
entry->state |= HFS_KEYDIRTY;
insert_hash(entry);
hfs_cat_mark_dirty(entry);
unlock_entry(entry);
/* delete any pre-existing or place-holder entry */
if (dest) {
delete_entry(dest);
unlock_entry(dest);
if (removed && dest->cnid) {
*removed = dest;
} else {
hfs_cat_put(dest);
}
}
goto done;
bail1:
unlock_entry(entry);
bail2:
if (dest) {
if (!dest->cnid) {
/* TRY to remove the new entry */
(void)hfs_bdelete(mdb->cat_tree, HFS_BKEY(new_key));
update_dir(mdb, new_dir, is_dir, -1);
bail3:
delete_entry(dest);
}
unlock_entry(dest);
hfs_cat_put(dest);
}
done:
if (new_dir != old_dir) {
end_write(old_dir);
}
end_write(new_dir);
spin_lock(&entry_lock);
mdb->rename_lock = 0; /* XXX: should use atomic_dec */
hfs_wake_up(&mdb->rename_wait);
spin_unlock(&entry_lock);
return error;
}
/*
* Initialize the hash tables
*/
void hfs_cat_init(void)
{
int i;
struct list_head *head = hash_table;
i = C_HASHSIZE;
do {
INIT_LIST_HEAD(head);
head++;
i--;
} while (i);
}
|