The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/fs/hfs/catalog.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    1 /*
    2  * linux/fs/hfs/catalog.c
    3  *
    4  * Copyright (C) 1995-1997  Paul H. Hargrove
    5  * This file may be distributed under the terms of the GNU General Public License.
    6  *
    7  * This file contains the functions related to the catalog B-tree.
    8  *
    9  * "XXX" in a comment is a note to myself to consider changing something.
   10  *
   11  * Cache code shamelessly stolen from 
   12  *     linux/fs/inode.c Copyright (C) 1991, 1992  Linus Torvalds
   13  *     re-shamelessly stolen Copyright (C) 1997 Linus Torvalds
   14  *
   15  * In function preconditions the term "valid" applied to a pointer to
   16  * a structure means that the pointer is non-NULL and the structure it
   17  * points to has all fields initialized to consistent values.
   18  *
   19  * The code in this file initializes some structures by calling
   20  * memset(&foo, 0, sizeof(foo)).  This produces the desired behavior
   21  * only due to the non-ANSI assumption that the machine representation
   22  */
   23 
   24 #include "hfs.h"
   25 
   26 /*================ Variable-like macros ================*/
   27 
   28 /* Number of hash table slots */
   29 #define C_HASHBITS  10
   30 #define C_HASHSIZE  (1UL << C_HASHBITS)
   31 #define C_HASHMASK  (C_HASHSIZE - 1)
   32 
   33 /* Number of entries to fit in a single page on an i386.
   34  * Actually, now it's used to increment the free entry pool. */
   35 #define CCACHE_INC (PAGE_SIZE/sizeof(struct hfs_cat_entry))
   36 #define CCACHE_MAX (CCACHE_INC * 8)
   37 
   38 /*================ File-local data types ================*/
   39 
   40 /* The catalog record for a file */
   41 typedef struct {
   42         hfs_byte_t      Flags;          /* Flags such as read-only */
   43         hfs_byte_t      Typ;            /* file version number = 0 */
   44         hfs_finfo_t     UsrWds;         /* data used by the Finder */
   45         hfs_lword_t     FlNum;          /* The CNID */
   46         hfs_word_t      StBlk;          /* obsolete */
   47         hfs_lword_t     LgLen;          /* The logical EOF of the data fork*/
   48         hfs_lword_t     PyLen;          /* The physical EOF of the data fork */
   49         hfs_word_t      RStBlk;         /* obsolete */
   50         hfs_lword_t     RLgLen;         /* The logical EOF of the rsrc fork */
   51         hfs_lword_t     RPyLen;         /* The physical EOF of the rsrc fork */
   52         hfs_lword_t     CrDat;          /* The creation date */
   53         hfs_lword_t     MdDat;          /* The modified date */
   54         hfs_lword_t     BkDat;          /* The last backup date */
   55         hfs_fxinfo_t    FndrInfo;       /* more data for the Finder */
   56         hfs_word_t      ClpSize;        /* number of bytes to allocate
   57                                            when extending files */
   58         hfs_byte_t      ExtRec[12];     /* first extent record
   59                                            for the data fork */
   60         hfs_byte_t      RExtRec[12];    /* first extent record
   61                                            for the resource fork */
   62         hfs_lword_t     Resrv;          /* reserved by Apple */
   63 } __attribute__((packed)) FIL_REC;
   64 
   65 /* the catalog record for a directory */
   66 typedef struct {
   67         hfs_word_t      Flags;          /* flags */
   68         hfs_word_t      Val;            /* Valence: number of files and
   69                                            dirs in the directory */
   70         hfs_lword_t     DirID;          /* The CNID */
   71         hfs_lword_t     CrDat;          /* The creation date */
   72         hfs_lword_t     MdDat;          /* The modification date */
   73         hfs_lword_t     BkDat;          /* The last backup date */
   74         hfs_dinfo_t     UsrInfo;        /* data used by the Finder */
   75         hfs_dxinfo_t    FndrInfo;       /* more data used by Finder */
   76         hfs_byte_t      Resrv[16];      /* reserved by Apple */
   77 } __attribute__((packed)) DIR_REC;
   78 
   79 /* the catalog record for a thread */
   80 typedef struct {
   81         hfs_byte_t              Reserv[8];      /* reserved by Apple */
   82         hfs_lword_t             ParID;          /* CNID of parent directory */
   83         struct hfs_name         CName;          /* The name of this entry */
   84 }  __attribute__((packed)) THD_REC;
   85 
   86 /* A catalog tree record */
   87 struct hfs_cat_rec {
   88         hfs_byte_t              cdrType;        /* The type of entry */
   89         hfs_byte_t              cdrResrv2;      /* padding */
   90         union {
   91                 FIL_REC fil;
   92                 DIR_REC dir;
   93                 THD_REC thd;
   94         } u;
   95 } __attribute__((packed));
   96 
   97 /*================ File-local variables ================*/
   98  
   99 static LIST_HEAD(entry_in_use);
  100 static LIST_HEAD(entry_unused);
  101 static struct list_head hash_table[C_HASHSIZE];
  102 
  103 static spinlock_t entry_lock = SPIN_LOCK_UNLOCKED;
  104 
  105 static struct {
  106         int nr_entries;
  107         int nr_free_entries;
  108 } entries_stat;
  109 
  110 /*================ File-local functions ================*/
  111 
  112 /*
  113  * brec_to_id
  114  *
  115  * Get the CNID from a brec
  116  */
  117 static inline hfs_u32 brec_to_id(struct hfs_brec *brec)
  118 {
  119         struct hfs_cat_rec *rec = brec->data;
  120 
  121         return hfs_get_nl((rec->cdrType==HFS_CDR_FIL) ?
  122                                 rec->u.fil.FlNum : rec->u.dir.DirID);
  123 }
  124 
  125 /*
  126  * hashfn()
  127  *
  128  * hash an (struct mdb *) and a (struct hfs_cat_key *) to an integer.
  129  */
  130 static inline unsigned int hashfn(const struct hfs_mdb *mdb,
  131                                   const struct hfs_cat_key *key)
  132 {
  133         unsigned int hash;
  134         
  135         hash = (unsigned long) mdb | (unsigned long) key->ParID[3] | 
  136                 hfs_strhash(key->CName.Name, key->CName.Len);
  137         hash = hash ^ (hash >> C_HASHBITS) ^ (hash >> C_HASHBITS*2);
  138         return hash & C_HASHMASK;
  139 }
  140 
  141 /*
  142  * hash()
  143  *
  144  * hash an (struct mdb *) and a (struct hfs_cat_key *)
  145  * to a pointer to a slot in the hash table.
  146  */
  147 static inline struct list_head *hash(struct hfs_mdb *mdb,
  148                                      const struct hfs_cat_key *key)
  149 {
  150         return hash_table + hashfn(mdb, key);
  151 }
  152 
  153 static inline void insert_hash(struct hfs_cat_entry *entry)
  154 {
  155         struct list_head *head = hash(entry->mdb, &entry->key);
  156         list_add(&entry->hash, head);
  157 }
  158 
  159 static inline void remove_hash(struct hfs_cat_entry *entry)
  160 {
  161         list_del(&entry->hash);
  162         INIT_LIST_HEAD(&entry->hash);
  163 }
  164 
  165 /*
  166  * wait_on_entry()
  167  *
  168  * Sleep until a locked entry is unlocked.
  169  */
  170 static inline void wait_on_entry(struct hfs_cat_entry * entry)
  171 {
  172         while ((entry->state & HFS_LOCK)) {
  173                 hfs_sleep_on(&entry->wait);
  174         }
  175 }
  176 
  177 /*
  178  * lock_entry()
  179  *
  180  * Obtain an exclusive lock on an entry.
  181  */
  182 static void lock_entry(struct hfs_cat_entry * entry)
  183 {
  184         wait_on_entry(entry);
  185         spin_lock(&entry_lock);
  186         entry->state |= HFS_LOCK;
  187         spin_unlock(&entry_lock);
  188 }
  189 
  190 /*
  191  * lock_entry()
  192  *
  193  * Relinquish an exclusive lock on an entry.
  194  */
  195 static void unlock_entry(struct hfs_cat_entry * entry)
  196 {
  197         spin_lock(&entry_lock);
  198         entry->state &= ~HFS_LOCK;
  199         spin_unlock(&entry_lock);
  200         hfs_wake_up(&entry->wait);
  201 }
  202 
  203 /* put entry on mdb dirty list. */
  204 void hfs_cat_mark_dirty(struct hfs_cat_entry *entry)
  205 {
  206         struct hfs_mdb *mdb = entry->mdb;
  207 
  208         spin_lock(&entry_lock);
  209         if (!(entry->state & HFS_DIRTY)) {
  210                 entry->state |= HFS_DIRTY;
  211 
  212                 /* Only add valid (ie hashed) entries to the dirty list. */
  213                 if (!list_empty(&entry->hash)) {
  214                         list_del(&entry->list);
  215                         list_add(&entry->list, &mdb->entry_dirty);
  216                 }
  217         }
  218         spin_unlock(&entry_lock);
  219 }
  220 
  221 /* delete an entry and remove it from the hash table. */
  222 static void delete_entry(struct hfs_cat_entry *entry)
  223 {
  224         if (!(entry->state & HFS_DELETED)) {
  225                 entry->state |= HFS_DELETED;
  226                 list_del(&entry->hash);
  227                 INIT_LIST_HEAD(&entry->hash);
  228 
  229                 if (entry->type == HFS_CDR_FIL) {
  230                   /* free all extents */
  231                   entry->u.file.data_fork.lsize = 0;
  232                   hfs_extent_adj(&entry->u.file.data_fork);
  233                   entry->u.file.rsrc_fork.lsize = 0;
  234                   hfs_extent_adj(&entry->u.file.rsrc_fork);
  235                 }
  236         }
  237 }
  238 
  239 
  240 static inline void init_entry(struct hfs_cat_entry *entry)
  241 {
  242         memset(entry, 0, sizeof(*entry));
  243         hfs_init_waitqueue(&entry->wait);
  244         INIT_LIST_HEAD(&entry->hash);
  245         INIT_LIST_HEAD(&entry->list);
  246 }
  247 
  248 /*
  249  * hfs_cat_alloc()
  250  *
  251  * Try to allocate another entry. 
  252  */
  253 static inline struct hfs_cat_entry *hfs_cat_alloc(void)
  254 {
  255         struct hfs_cat_entry *entry;
  256 
  257         if (!HFS_NEW(entry))
  258                 return NULL;
  259 
  260         init_entry(entry);
  261         return entry;
  262 }
  263 
  264 /* this gets called with the spinlock held. */
  265 static int grow_entries(void)
  266 {
  267         struct hfs_cat_entry *entry;
  268         int i;
  269         
  270         for (i = 0; i < CCACHE_INC; i++) {
  271                 if (!(entry = hfs_cat_alloc()))
  272                         break;
  273                 list_add(&entry->list, &entry_unused);
  274         }
  275 
  276         entries_stat.nr_entries += i;
  277         entries_stat.nr_free_entries += i;
  278                 
  279         return i;
  280 }
  281 
  282 /*
  283  * __read_entry()
  284  *
  285  * Convert a (struct hfs_cat_rec) to a (struct hfs_cat_entry).
  286  */
  287 static void __read_entry(struct hfs_cat_entry *entry,
  288                          const struct hfs_cat_rec *cat)
  289 {
  290         entry->type = cat->cdrType;
  291 
  292         if (cat->cdrType == HFS_CDR_DIR) {
  293                 struct hfs_dir *dir = &entry->u.dir;
  294 
  295                 entry->cnid = hfs_get_nl(cat->u.dir.DirID);
  296 
  297                 dir->magic = HFS_DIR_MAGIC;
  298                 dir->flags = hfs_get_ns(cat->u.dir.Flags);
  299                 memcpy(&entry->info.dir.dinfo, &cat->u.dir.UsrInfo, 16);
  300                 memcpy(&entry->info.dir.dxinfo, &cat->u.dir.FndrInfo, 16);
  301                 entry->create_date = hfs_get_nl(cat->u.dir.CrDat);
  302                 entry->modify_date = hfs_get_nl(cat->u.dir.MdDat);
  303                 entry->backup_date = hfs_get_nl(cat->u.dir.BkDat);
  304                 dir->dirs = dir->files = 0;
  305                 hfs_init_waitqueue(&dir->read_wait);
  306                 hfs_init_waitqueue(&dir->write_wait);
  307         } else if (cat->cdrType == HFS_CDR_FIL) {
  308                 struct hfs_file *fil = &entry->u.file;
  309 
  310                 entry->cnid = hfs_get_nl(cat->u.fil.FlNum);
  311 
  312                 fil->magic = HFS_FILE_MAGIC;
  313 
  314                 fil->data_fork.fork = HFS_FK_DATA;
  315                 fil->data_fork.entry = entry;
  316                 fil->data_fork.lsize = hfs_get_hl(cat->u.fil.LgLen);
  317                 fil->data_fork.psize = hfs_get_hl(cat->u.fil.PyLen) >>
  318                                                      HFS_SECTOR_SIZE_BITS;
  319                 hfs_extent_in(&fil->data_fork, cat->u.fil.ExtRec);
  320 
  321                 fil->rsrc_fork.fork = HFS_FK_RSRC;
  322                 fil->rsrc_fork.entry = entry;
  323                 fil->rsrc_fork.lsize = hfs_get_hl(cat->u.fil.RLgLen);
  324                 fil->rsrc_fork.psize = hfs_get_hl(cat->u.fil.RPyLen) >>
  325                                                      HFS_SECTOR_SIZE_BITS;
  326                 hfs_extent_in(&fil->rsrc_fork, cat->u.fil.RExtRec);
  327 
  328                 memcpy(&entry->info.file.finfo, &cat->u.fil.UsrWds, 16);
  329                 memcpy(&entry->info.file.fxinfo, &cat->u.fil.FndrInfo, 16);
  330 
  331                 entry->create_date = hfs_get_nl(cat->u.fil.CrDat);
  332                 entry->modify_date = hfs_get_nl(cat->u.fil.MdDat);
  333                 entry->backup_date = hfs_get_nl(cat->u.fil.BkDat);
  334                 fil->clumpablks = (hfs_get_hs(cat->u.fil.ClpSize)
  335                                         / entry->mdb->alloc_blksz)
  336                                                 >> HFS_SECTOR_SIZE_BITS;
  337                 fil->flags = cat->u.fil.Flags;
  338         } else {
  339                 hfs_warn("hfs_fs: entry is neither file nor directory!\n");
  340         }
  341 }
  342 
  343 /*
  344  * count_dir_entries()
  345  *
  346  * Count the number of files and directories in a given directory.
  347  */
  348 static inline void count_dir_entries(struct hfs_cat_entry *entry,
  349                                      struct hfs_brec *brec)
  350 {
  351         int error = 0;
  352         hfs_u32 cnid;
  353         hfs_u8 type;
  354 
  355         if (!hfs_cat_open(entry, brec)) {
  356                 while (!(error = hfs_cat_next(entry, brec, 1, &cnid, &type))) {
  357                         if (type == HFS_CDR_FIL) {
  358                                 ++entry->u.dir.files;
  359                         } else if (type == HFS_CDR_DIR) {
  360                                 ++entry->u.dir.dirs;
  361                         }
  362                 } /* -ENOENT is normal termination */
  363         }
  364         if (error != -ENOENT) {
  365                 entry->cnid = 0;
  366         }
  367 }
  368 
  369 /*
  370  * read_entry()
  371  *
  372  * Convert a (struct hfs_brec) to a (struct hfs_cat_entry).
  373  */
  374 static inline void read_entry(struct hfs_cat_entry *entry,
  375                               struct hfs_brec *brec)
  376 {
  377         int need_count;
  378         struct hfs_cat_rec *rec = brec->data;
  379 
  380         __read_entry(entry, rec);
  381 
  382         need_count = (rec->cdrType == HFS_CDR_DIR) && rec->u.dir.Val;
  383 
  384         hfs_brec_relse(brec, NULL);
  385 
  386         if (need_count) {
  387                 count_dir_entries(entry, brec);
  388         }
  389 }
  390 
  391 /*
  392  * __write_entry()
  393  *
  394  * Convert a (struct hfs_cat_entry) to a (struct hfs_cat_rec).
  395  */
  396 static void __write_entry(const struct hfs_cat_entry *entry,
  397                           struct hfs_cat_rec *cat)
  398 {
  399         if (entry->type == HFS_CDR_DIR) {
  400                 const struct hfs_dir *dir = &entry->u.dir;
  401 
  402                 hfs_put_ns(dir->flags,             cat->u.dir.Flags);
  403                 hfs_put_hs(dir->dirs + dir->files, cat->u.dir.Val);
  404                 hfs_put_nl(entry->cnid,            cat->u.dir.DirID);
  405                 hfs_put_nl(entry->create_date,     cat->u.dir.CrDat);
  406                 hfs_put_nl(entry->modify_date,     cat->u.dir.MdDat);
  407                 hfs_put_nl(entry->backup_date,     cat->u.dir.BkDat);
  408                 memcpy(&cat->u.dir.UsrInfo, &entry->info.dir.dinfo, 16);
  409                 memcpy(&cat->u.dir.FndrInfo, &entry->info.dir.dxinfo, 16);
  410         } else if (entry->type == HFS_CDR_FIL) {
  411                 const struct hfs_file *fil = &entry->u.file;
  412 
  413                 cat->u.fil.Flags = fil->flags;
  414                 hfs_put_nl(entry->cnid,            cat->u.fil.FlNum);
  415                 memcpy(&cat->u.fil.UsrWds, &entry->info.file.finfo, 16);
  416                 hfs_put_hl(fil->data_fork.lsize, cat->u.fil.LgLen);
  417                 hfs_put_hl(fil->data_fork.psize << HFS_SECTOR_SIZE_BITS,
  418                                                         cat->u.fil.PyLen);
  419                 hfs_put_hl(fil->rsrc_fork.lsize, cat->u.fil.RLgLen);
  420                 hfs_put_hl(fil->rsrc_fork.psize << HFS_SECTOR_SIZE_BITS,
  421                                                         cat->u.fil.RPyLen);
  422                 hfs_put_nl(entry->create_date,     cat->u.fil.CrDat);
  423                 hfs_put_nl(entry->modify_date,     cat->u.fil.MdDat);
  424                 hfs_put_nl(entry->backup_date,     cat->u.fil.BkDat);
  425                 memcpy(&cat->u.fil.FndrInfo, &entry->info.file.fxinfo, 16);
  426                 hfs_put_hs((fil->clumpablks * entry->mdb->alloc_blksz)
  427                                 << HFS_SECTOR_SIZE_BITS, cat->u.fil.ClpSize);
  428                 hfs_extent_out(&fil->data_fork, cat->u.fil.ExtRec);
  429                 hfs_extent_out(&fil->rsrc_fork, cat->u.fil.RExtRec);
  430         } else {
  431                 hfs_warn("__write_entry: invalid entry\n");
  432         }
  433 }
  434 
  435 /*
  436  * write_entry()
  437  *
  438  * Write a modified entry back to the catalog B-tree. this gets called
  439  * with the entry locked.
  440  */
  441 static void write_entry(struct hfs_cat_entry * entry)
  442 {
  443         struct hfs_brec brec;
  444         int error;
  445 
  446         if (!(entry->state & HFS_DELETED)) {
  447                 error = hfs_bfind(&brec, entry->mdb->cat_tree,
  448                                   HFS_BKEY(&entry->key), HFS_BFIND_WRITE);
  449                 if (!error) {
  450                         if ((entry->state & HFS_KEYDIRTY)) {
  451                                 /* key may have changed case due to a rename */
  452                                 entry->state &= ~HFS_KEYDIRTY;
  453                                 if (brec.key->KeyLen != entry->key.KeyLen) {
  454                                         hfs_warn("hfs_write_entry: key length "
  455                                                  "changed!\n");
  456                                         error = 1;
  457                                 } else {
  458                                         memcpy(brec.key, &entry->key,
  459                                                entry->key.KeyLen);
  460                                 }
  461                         } else if (entry->cnid != brec_to_id(&brec)) {
  462                                 hfs_warn("hfs_write_entry: CNID "
  463                                          "changed unexpectedly!\n");
  464                                 error = 1;
  465                         }
  466                         if (!error) {
  467                                 __write_entry(entry, brec.data);
  468                         }
  469                         hfs_brec_relse(&brec, NULL);
  470                 }
  471                 if (error) {
  472                         hfs_warn("hfs_write_entry: unable to write "
  473                                  "entry %08x\n", entry->cnid);
  474                 }
  475         }
  476 }
  477 
  478 
  479 /* this gets called with the spinlock held. */
  480 static struct hfs_cat_entry *find_entry(struct hfs_mdb *mdb,
  481                                         const struct hfs_cat_key *key)
  482 {
  483         struct list_head *tmp, *head = hash(mdb, key);
  484         struct hfs_cat_entry * entry;
  485 
  486         tmp = head;
  487         for (;;) {
  488                 tmp = tmp->next;
  489                 entry = NULL;
  490                 if (tmp == head)
  491                         break;
  492                 entry = list_entry(tmp, struct hfs_cat_entry, hash);
  493                 if (entry->mdb != mdb)
  494                         continue;
  495                 if (hfs_cat_compare(&entry->key, key)) {
  496                         continue;
  497                 }
  498                 entry->count++;
  499                 break;
  500         }
  501 
  502         return entry;
  503 }
  504 
  505 
  506 /* be careful. this gets called with the spinlock held. */
  507 static struct hfs_cat_entry *get_new_entry(struct hfs_mdb *mdb,
  508                                            const struct hfs_cat_key *key,
  509                                            const int read)
  510 {
  511         struct hfs_cat_entry *entry;
  512         struct list_head *head = hash(mdb, key);
  513         struct list_head *tmp;
  514 
  515 add_new_entry:
  516         tmp = entry_unused.next;
  517         if ((tmp != &entry_unused) ) {
  518                 list_del(tmp);
  519                 entries_stat.nr_free_entries--;
  520                 entry = list_entry(tmp, struct hfs_cat_entry, list);
  521                 list_add(&entry->list, &entry_in_use);
  522                 list_add(&entry->hash, head);
  523                 entry->mdb = mdb;
  524                 entry->count = 1;
  525                 memcpy(&entry->key, key, sizeof(*key));
  526                 entry->state = HFS_LOCK;
  527                 spin_unlock(&entry_lock);
  528 
  529                 if (read) {
  530                    struct hfs_brec brec;
  531 
  532                    if (hfs_bfind(&brec, mdb->cat_tree,
  533                                  HFS_BKEY(key), HFS_BFIND_READ_EQ)) {
  534                         /* uh oh. we failed to read the record.
  535                          * the entry doesn't actually exist. */
  536                         goto read_fail;
  537                    }
  538 
  539                    read_entry(entry, &brec);
  540                    
  541                    /* error */
  542                    if (!entry->cnid) {
  543                         goto read_fail;
  544                    }
  545 
  546                    /* we don't have to acquire a spinlock here or
  547                     * below for the unlocking bits as we're the first
  548                     * user of this entry. */
  549                    entry->state &= ~HFS_LOCK;
  550                    hfs_wake_up(&entry->wait);
  551                 }
  552 
  553                 return entry;
  554         }
  555 
  556 
  557         /* try to allocate more entries. grow_entries() doesn't release
  558          * the spinlock. */
  559         if (grow_entries())
  560                 goto add_new_entry;
  561 
  562         spin_unlock(&entry_lock);
  563         return NULL;
  564 
  565 read_fail: 
  566         /* short-cut hfs_cat_put by doing everything here. */
  567         spin_lock(&entry_lock);
  568         list_del(&entry->hash);
  569         list_del(&entry->list);
  570         init_entry(entry);
  571         list_add(&entry->list, &entry_unused);
  572         entries_stat.nr_free_entries++;
  573         spin_unlock(&entry_lock);
  574         return NULL;
  575 }
  576 
  577 /*
  578  * get_entry()
  579  *
  580  * Try to return an entry for the indicated file or directory.
  581  * If ('read' == 0) then no attempt will be made to read it from disk
  582  * and a locked, but uninitialized, entry is returned.
  583  */
  584 static struct hfs_cat_entry *get_entry(struct hfs_mdb *mdb,
  585                                        const struct hfs_cat_key *key,
  586                                        const int read)
  587 {
  588         struct hfs_cat_entry * entry;
  589 
  590 #if defined(DEBUG_CATALOG) || defined(DEBUG_ALL)
  591         hfs_warn("hfs_get_entry: mdb=%p key=%s read=%d\n",
  592                  mdb, key->CName.Name, read);
  593 #endif
  594 
  595         spin_lock(&entry_lock);
  596         entry = find_entry(mdb, key);
  597         if (!entry) {
  598                 return get_new_entry(mdb, key, read);
  599         }
  600         spin_unlock(&entry_lock);
  601         wait_on_entry(entry);
  602         return entry;
  603 }
  604 
  605 /* 
  606  * new_cnid()
  607  *
  608  * Allocate a CNID to use for a new file or directory.
  609  */
  610 static inline hfs_u32 new_cnid(struct hfs_mdb *mdb)
  611 {
  612         /* If the create succeeds then the mdb will get dirtied */
  613         return htonl(mdb->next_id++);
  614 }
  615 
  616 /*
  617  * update_dir()
  618  *
  619  * Update counts, times and dirt on a changed directory
  620  */
  621 static void update_dir(struct hfs_mdb *mdb, struct hfs_cat_entry *dir,
  622                        int is_dir, int count)
  623 {
  624         /* update counts */
  625         if (is_dir) {
  626                 mdb->dir_count += count;
  627                 dir->u.dir.dirs += count;
  628                 if (dir->cnid == htonl(HFS_ROOT_CNID)) {
  629                         mdb->root_dirs += count;
  630                 }
  631         } else {
  632                 mdb->file_count += count;
  633                 dir->u.dir.files += count;
  634                 if (dir->cnid == htonl(HFS_ROOT_CNID)) {
  635                         mdb->root_files += count;
  636                 }
  637         }
  638         
  639         /* update times and dirt */
  640         dir->modify_date = hfs_time();
  641         hfs_cat_mark_dirty(dir);
  642 }
  643 
  644 /*
  645  * Add a writer to dir, excluding readers.
  646  *
  647  * XXX: this is wrong. it allows a move to occur when a directory
  648  *      is being written to. 
  649  */
  650 static inline void start_write(struct hfs_cat_entry *dir)
  651 {
  652         if (dir->u.dir.readers || waitqueue_active(&dir->u.dir.read_wait)) {
  653                 hfs_sleep_on(&dir->u.dir.write_wait);
  654         }
  655         ++dir->u.dir.writers;
  656 }
  657 
  658 /*
  659  * Add a reader to dir, excluding writers.
  660  */
  661 static inline void start_read(struct hfs_cat_entry *dir)
  662 {
  663         if (dir->u.dir.writers || waitqueue_active(&dir->u.dir.write_wait)) {
  664                 hfs_sleep_on(&dir->u.dir.read_wait);
  665         }
  666         ++dir->u.dir.readers;
  667 }
  668 
  669 /*
  670  * Remove a writer from dir, possibly admitting readers.
  671  */
  672 static inline void end_write(struct hfs_cat_entry *dir)
  673 {
  674         if (!(--dir->u.dir.writers)) {
  675                 hfs_wake_up(&dir->u.dir.read_wait);
  676         }
  677 }
  678 
  679 /*
  680  * Remove a reader from dir, possibly admitting writers.
  681  */
  682 static inline void end_read(struct hfs_cat_entry *dir)
  683 {
  684         if (!(--dir->u.dir.readers)) {
  685                 hfs_wake_up(&dir->u.dir.write_wait);
  686         }
  687 }
  688 
  689 /*
  690  * create_entry()
  691  *
  692  * Add a new file or directory to the catalog B-tree and
  693  * return a (struct hfs_cat_entry) for it in '*result'.
  694  */
  695 static int create_entry(struct hfs_cat_entry *parent, struct hfs_cat_key *key,
  696                         const struct hfs_cat_rec *record, int is_dir,
  697                         hfs_u32 cnid, struct hfs_cat_entry **result)
  698 {
  699         struct hfs_mdb *mdb = parent->mdb;
  700         struct hfs_cat_entry *entry;
  701         struct hfs_cat_key thd_key;
  702         struct hfs_cat_rec thd_rec;
  703         int error, has_thread;
  704 
  705         if (result) {
  706                 *result = NULL;
  707         }
  708 
  709         /* keep readers from getting confused by changing dir size */
  710         start_write(parent);
  711 
  712         /* create a locked entry in the cache */
  713         entry = get_entry(mdb, key, 0);
  714         if (!entry) {
  715                 /* The entry exists but can't be read */
  716                 error = -EIO;
  717                 goto done;
  718         }
  719 
  720         if (entry->cnid) {
  721                 /* The (unlocked) entry exists in the cache */
  722                 error = -EEXIST;
  723                 goto bail2;
  724         }
  725 
  726         /* limit directory valence to signed 16-bit integer */
  727         if ((parent->u.dir.dirs + parent->u.dir.files) >= HFS_MAX_VALENCE) {
  728                 error = -ENOSPC;
  729                 goto bail1;
  730         }
  731 
  732         has_thread = is_dir || (record->u.fil.Flags & HFS_FIL_THD);
  733 
  734         if (has_thread) {
  735                 /* init some fields for the thread record */
  736                 memset(&thd_rec, 0, sizeof(thd_rec));
  737                 thd_rec.cdrType = is_dir ? HFS_CDR_THD : HFS_CDR_FTH;
  738                 memcpy(&thd_rec.u.thd.ParID, &key->ParID,
  739                        sizeof(hfs_u32) + sizeof(struct hfs_name));
  740 
  741                 /* insert the thread record */
  742                 hfs_cat_build_key(cnid, NULL, &thd_key);
  743                 error = hfs_binsert(mdb->cat_tree, HFS_BKEY(&thd_key),
  744                                     &thd_rec, 2 + sizeof(THD_REC));
  745                 if (error) {
  746                         goto bail1;
  747                 }
  748         }
  749 
  750         /* insert the record */
  751         error = hfs_binsert(mdb->cat_tree, HFS_BKEY(key), record,
  752                                 is_dir ?  2 + sizeof(DIR_REC) :
  753                                           2 + sizeof(FIL_REC));
  754         if (error) {
  755                 if (has_thread && (error != -EIO)) {
  756                         /* at least TRY to remove the thread record */
  757                         (void)hfs_bdelete(mdb->cat_tree, HFS_BKEY(&thd_key));
  758                 }
  759                 goto bail1;
  760         }
  761 
  762         /* update the parent directory */
  763         update_dir(mdb, parent, is_dir, 1);
  764 
  765         /* complete the cache entry and return success */
  766         __read_entry(entry, record);
  767         unlock_entry(entry);
  768 
  769         if (result) {
  770                 *result = entry;
  771         } else {
  772                 hfs_cat_put(entry);
  773         }
  774         goto done;
  775 
  776 bail1:
  777         /* entry really didn't exist, so we don't need to really delete it.
  778          * we do need to remove it from the hash, though. */
  779         entry->state |= HFS_DELETED;
  780         remove_hash(entry);
  781         unlock_entry(entry);
  782 bail2:
  783         hfs_cat_put(entry);
  784 done:
  785         end_write(parent);
  786         return error;
  787 }
  788 
  789 /*================ Global functions ================*/
  790 
  791 /* 
  792  * hfs_cat_put()
  793  *
  794  * Release an entry we aren't using anymore.
  795  *
  796  * nothing in hfs_cat_put goes to sleep now except on the initial entry.  
  797  */
  798 void hfs_cat_put(struct hfs_cat_entry * entry)
  799 {
  800         if (entry) {
  801                 wait_on_entry(entry);
  802 
  803                 /* just in case. this should never happen. */
  804                 if (!entry->count) { 
  805                   hfs_warn("hfs_cat_put: trying to free free entry: %p\n",
  806                            entry);
  807                   return;
  808                 }
  809 
  810 #if defined(DEBUG_CATALOG) || defined(DEBUG_ALL)
  811                 hfs_warn("hfs_cat_put: %p(%u) type=%d state=%lu\n", 
  812                          entry, entry->count, entry->type, entry->state);
  813 #endif
  814                 spin_lock(&entry_lock);
  815                 if (!--entry->count) {
  816                         if ((entry->state & HFS_DELETED))
  817                                 goto entry_deleted;
  818 
  819                         if ((entry->type == HFS_CDR_FIL)) {
  820                                 /* clear out any cached extents */
  821                                 if (entry->u.file.data_fork.first.next) {
  822                                   hfs_extent_free(&entry->u.file.data_fork);
  823                                 }
  824                                 if (entry->u.file.rsrc_fork.first.next) {
  825                                   hfs_extent_free(&entry->u.file.rsrc_fork);
  826                                 }
  827                         }
  828 
  829                         /* if we put a dirty entry, write it out. */
  830                         if ((entry->state & HFS_DIRTY)) {
  831                                 entry->state ^= HFS_DIRTY | HFS_LOCK;
  832                                 write_entry(entry);
  833                                 entry->state &= ~HFS_LOCK;
  834                         }
  835 
  836                         list_del(&entry->hash);
  837 entry_deleted:          /* deleted entries have already been removed
  838                          * from the hash list. */
  839                         list_del(&entry->list);
  840                         if (entries_stat.nr_free_entries > CCACHE_MAX) {
  841                                 HFS_DELETE(entry);
  842                                 entries_stat.nr_entries--;
  843                         } else {
  844                                 init_entry(entry);
  845                                 list_add(&entry->list, &entry_unused);
  846                                 entries_stat.nr_free_entries++;
  847                         }
  848                 }
  849                 spin_unlock(&entry_lock);
  850         }
  851 }
  852 
  853 /* 
  854  * hfs_cat_get()
  855  *
  856  * Wrapper for get_entry() which always calls with ('read'==1).
  857  * Used for access to get_entry() from outside this file.
  858  */
  859 struct hfs_cat_entry *hfs_cat_get(struct hfs_mdb *mdb,
  860                                   const struct hfs_cat_key *key)
  861 {
  862         return get_entry(mdb, key, 1);
  863 }
  864 
  865 /* invalidate all entries for a device */
  866 static void invalidate_list(struct list_head *head, struct hfs_mdb *mdb,
  867                             struct list_head *dispose)
  868 {
  869         struct list_head *next;
  870 
  871         next = head->next;
  872         for (;;) {
  873                 struct list_head *tmp = next;
  874                 struct hfs_cat_entry * entry;
  875                 
  876                 next = next->next;
  877                 if (tmp == head)
  878                         break;
  879                 entry = list_entry(tmp, struct hfs_cat_entry, list);
  880                 if (entry->mdb != mdb) {
  881                         continue;
  882                 }
  883 
  884                 if (!entry->count) {
  885                         list_del(&entry->hash);
  886                         INIT_LIST_HEAD(&entry->hash);
  887                         list_del(&entry->list);
  888                         list_add(&entry->list, dispose);
  889                         continue;
  890                 }
  891                 
  892                 hfs_warn("hfs_fs: entry %p(%u) busy on removed device %s.\n",
  893                          entry, entry->count, 
  894                          hfs_mdb_name(entry->mdb->sys_mdb));
  895         }
  896 }
  897 
  898 /* delete entries from a list */
  899 static void delete_list(struct list_head *head) 
  900 {
  901         struct list_head *next = head->next;
  902         struct hfs_cat_entry *entry;
  903         
  904         for (;;) {
  905                 struct list_head * tmp = next;
  906 
  907                 next = next->next;
  908                 if (tmp == head) {
  909                         break;
  910                 }
  911                 entry = list_entry(tmp, struct hfs_cat_entry, list);
  912                 HFS_DELETE(entry);
  913         }
  914 }
  915 
  916 /* 
  917  * hfs_cat_invalidate()
  918  *
  919  * Called by hfs_mdb_put() to remove all the entries
  920  * in the cache that are associated with a given MDB.
  921  */
  922 void hfs_cat_invalidate(struct hfs_mdb *mdb)
  923 {
  924         LIST_HEAD(throw_away);
  925 
  926         spin_lock(&entry_lock);
  927         invalidate_list(&entry_in_use, mdb, &throw_away);
  928         invalidate_list(&mdb->entry_dirty, mdb, &throw_away);
  929         spin_unlock(&entry_lock);
  930 
  931         delete_list(&throw_away);
  932 #if defined(DEBUG_CATALOG) || defined(DEBUG_ALL)
  933         hfs_warn("hfs_cat_invalidate: free=%d total=%d\n",
  934                  entries_stat.nr_free_entries,
  935                  entries_stat.nr_entries);
  936 #endif
  937 }
  938 
  939 /*
  940  * hfs_cat_commit()
  941  *
  942  * Called by hfs_mdb_commit() to write dirty entries to the disk buffers.
  943  */
  944 void hfs_cat_commit(struct hfs_mdb *mdb)
  945 {
  946         struct list_head *tmp, *head = &mdb->entry_dirty;
  947         struct hfs_cat_entry *entry;
  948 
  949         spin_lock(&entry_lock);
  950         while ((tmp = head->prev) != head) {
  951                 entry = list_entry(tmp, struct hfs_cat_entry, list);
  952                   
  953                 if ((entry->state & HFS_LOCK)) {
  954                         spin_unlock(&entry_lock);
  955                         wait_on_entry(entry);
  956                         spin_lock(&entry_lock);
  957                 } else {
  958                        struct list_head *insert = &entry_in_use;
  959 
  960                        if (!entry->count)
  961                                 insert = entry_in_use.prev;
  962 
  963                        /* add to in_use list */
  964                        list_del(&entry->list);
  965                        list_add(&entry->list, insert);
  966 
  967                        /* reset DIRTY, set LOCK */
  968                        entry->state ^= HFS_DIRTY | HFS_LOCK;
  969                        spin_unlock(&entry_lock);
  970                        write_entry(entry);
  971                        spin_lock(&entry_lock);
  972                        entry->state &= ~HFS_LOCK;
  973                        hfs_wake_up(&entry->wait);
  974                 }
  975         }
  976         spin_unlock(&entry_lock);
  977 }
  978 
  979 /*
  980  * hfs_cat_free()
  981  *
  982  * Releases all the memory allocated in grow_entries().
  983  * Must call hfs_cat_invalidate() on all MDBs before calling this.
  984  * This only gets rid of the unused pool of entries. all the other
  985  * entry references should have either been freed by cat_invalidate
  986  * or moved onto the unused list.
  987  */
  988 void hfs_cat_free(void)
  989 {
  990         delete_list(&entry_unused);
  991 }
  992 
  993 /*
  994  * hfs_cat_compare()
  995  *
  996  * Description:
  997  *   This is the comparison function used for the catalog B-tree.  In
  998  *   comparing catalog B-tree entries, the parent id is the most
  999  *   significant field (compared as unsigned ints).  The name field is
 1000  *   the least significant (compared in "Macintosh lexical order",
 1001  *   see hfs_strcmp() in string.c)
 1002  * Input Variable(s):
 1003  *   struct hfs_cat_key *key1: pointer to the first key to compare
 1004  *   struct hfs_cat_key *key2: pointer to the second key to compare
 1005  * Output Variable(s):
 1006  *   NONE
 1007  * Returns:
 1008  *   int: negative if key1<key2, positive if key1>key2, and 0 if key1==key2
 1009  * Preconditions:
 1010  *   key1 and key2 point to "valid" (struct hfs_cat_key)s.
 1011  * Postconditions:
 1012  *   This function has no side-effects
 1013  */
 1014 int hfs_cat_compare(const struct hfs_cat_key *key1,
 1015                     const struct hfs_cat_key *key2)
 1016 {
 1017         unsigned int parents;
 1018         int retval;
 1019 
 1020         parents = hfs_get_hl(key1->ParID) - hfs_get_hl(key2->ParID);
 1021         if (parents != 0) {
 1022                 retval = (int)parents;
 1023         } else {
 1024                 retval = hfs_strcmp(key1->CName.Name, key1->CName.Len,
 1025                                     key2->CName.Name, key2->CName.Len);
 1026         }
 1027         return retval;
 1028 }
 1029 
 1030 /*
 1031  * hfs_cat_build_key()
 1032  *
 1033  * Given the ID of the parent and the name build a search key.
 1034  */
 1035 void hfs_cat_build_key(hfs_u32 parent, const struct hfs_name *cname,
 1036                        struct hfs_cat_key *key)
 1037 {
 1038         hfs_put_nl(parent, key->ParID);
 1039 
 1040         if (cname) {
 1041                 key->KeyLen = 6 + cname->Len;
 1042                 memcpy(&key->CName, cname, sizeof(*cname));
 1043         } else {
 1044                 key->KeyLen = 6;
 1045                 memset(&key->CName, 0, sizeof(*cname));
 1046         }
 1047 }
 1048 
 1049 /*
 1050  * hfs_cat_open()
 1051  *
 1052  * Given a directory on an HFS filesystem get its thread and
 1053  * lock the directory against insertions and deletions.
 1054  * Return 0 on success or an error code on failure.
 1055  */
 1056 int hfs_cat_open(struct hfs_cat_entry *dir, struct hfs_brec *brec)
 1057 {
 1058         struct hfs_cat_key key;
 1059         int error;
 1060 
 1061         if (dir->type != HFS_CDR_DIR) {
 1062                 return -EINVAL;
 1063         }
 1064         
 1065         /* Block writers */
 1066         start_read(dir);
 1067 
 1068         /* Find the directory */
 1069         hfs_cat_build_key(dir->cnid, NULL, &key);
 1070         error = hfs_bfind(brec, dir->mdb->cat_tree,
 1071                           HFS_BKEY(&key), HFS_BFIND_READ_EQ);
 1072 
 1073         if (error) {
 1074                 end_read(dir);
 1075         }
 1076 
 1077         return error;
 1078 }
 1079 
 1080 /*
 1081  * hfs_cat_next()
 1082  *
 1083  * Given a catalog brec structure, replace it with the count'th next brec
 1084  * in the same directory.
 1085  * Return an error code if there is a problem, 0 if OK.
 1086  * Note that an error code of -ENOENT means there are no more entries
 1087  * in this directory.
 1088  * The directory is "closed" on an error.
 1089  */
 1090 int hfs_cat_next(struct hfs_cat_entry *dir, struct hfs_brec *brec,
 1091                  hfs_u16 count, hfs_u32 *cnid, hfs_u8 *type)
 1092 {
 1093         int error;
 1094 
 1095         if (!dir || !brec) {
 1096                 return -EINVAL;
 1097         }
 1098 
 1099         /* Get the count'th next catalog tree entry */
 1100         error = hfs_bsucc(brec, count);
 1101         if (!error) {
 1102                 struct hfs_cat_key *key = (struct hfs_cat_key *)brec->key;
 1103                 if (hfs_get_nl(key->ParID) != dir->cnid) {
 1104                         hfs_brec_relse(brec, NULL);
 1105                         error = -ENOENT;
 1106                 }
 1107         }
 1108         if (!error) {
 1109                 *type = ((struct hfs_cat_rec *)brec->data)->cdrType;
 1110                 *cnid = brec_to_id(brec);
 1111         } else {
 1112                 end_read(dir);
 1113         }
 1114         return error;
 1115 }
 1116 
 1117 /*
 1118  * hfs_cat_close()
 1119  *
 1120  * Given a catalog brec structure, replace it with the count'th next brec
 1121  * in the same directory.
 1122  * Return an error code if there is a problem, 0 if OK.
 1123  * Note that an error code of -ENOENT means there are no more entries
 1124  * in this directory.
 1125  */
 1126 void hfs_cat_close(struct hfs_cat_entry *dir, struct hfs_brec *brec)
 1127 {
 1128         if (dir && brec) {
 1129                 hfs_brec_relse(brec, NULL);
 1130                 end_read(dir);
 1131         }
 1132 }
 1133 
 1134 /*
 1135  * hfs_cat_parent()
 1136  *
 1137  * Given a catalog entry, return the entry for its parent.
 1138  * Uses catalog key for the entry to get its parent's ID
 1139  * and then uses the parent's thread record to locate the
 1140  * parent's actual catalog entry.
 1141  */
 1142 struct hfs_cat_entry *hfs_cat_parent(struct hfs_cat_entry *entry)
 1143 {
 1144         struct hfs_cat_entry *retval = NULL;
 1145         struct hfs_mdb *mdb = entry->mdb;
 1146         struct hfs_brec brec;
 1147         struct hfs_cat_key key;
 1148         int error;
 1149 
 1150         lock_entry(entry);
 1151         if (!(entry->state & HFS_DELETED)) {
 1152                 hfs_cat_build_key(hfs_get_nl(entry->key.ParID), NULL, &key);
 1153                 error = hfs_bfind(&brec, mdb->cat_tree,
 1154                                   HFS_BKEY(&key), HFS_BFIND_READ_EQ);
 1155                 if (!error) {
 1156                         /* convert thread record to key */
 1157                         struct hfs_cat_rec *rec = brec.data;
 1158                         key.KeyLen = 6 + rec->u.thd.CName.Len;
 1159                         memcpy(&key.ParID, &rec->u.thd.ParID,
 1160                                sizeof(hfs_u32) + sizeof(struct hfs_name));
 1161 
 1162                         hfs_brec_relse(&brec, NULL);
 1163 
 1164                         retval = hfs_cat_get(mdb, &key);
 1165                 }
 1166         }
 1167         unlock_entry(entry);
 1168         return retval;
 1169 }
 1170         
 1171 /*
 1172  * hfs_cat_create()
 1173  *
 1174  * Create a new file with the indicated name in the indicated directory.
 1175  * The file will have the indicated flags, type and creator.
 1176  * If successful an (struct hfs_cat_entry) is returned in '*result'.
 1177  */
 1178 int hfs_cat_create(struct hfs_cat_entry *parent, struct hfs_cat_key *key,
 1179                    hfs_u8 flags, hfs_u32 type, hfs_u32 creator,
 1180                    struct hfs_cat_entry **result)
 1181 {
 1182         struct hfs_cat_rec record;
 1183         hfs_u32 id = new_cnid(parent->mdb);
 1184         hfs_u32 mtime = hfs_time();
 1185 
 1186 #if defined(DEBUG_CATALOG) || defined(DEBUG_ALL)
 1187         hfs_warn("hfs_cat_create: %p/%s flags=%d res=%p\n",
 1188                  parent, key->CName.Name, flags, result);
 1189 #endif
 1190         /* init some fields for the file record */
 1191         memset(&record, 0, sizeof(record));
 1192         record.cdrType = HFS_CDR_FIL;
 1193         record.u.fil.Flags = flags | HFS_FIL_USED;
 1194         hfs_put_nl(id,      record.u.fil.FlNum);
 1195         hfs_put_nl(mtime,   record.u.fil.CrDat);
 1196         hfs_put_nl(mtime,   record.u.fil.MdDat);
 1197         hfs_put_nl(0,       record.u.fil.BkDat);
 1198         hfs_put_nl(type,    record.u.fil.UsrWds.fdType);
 1199         hfs_put_nl(creator, record.u.fil.UsrWds.fdCreator);
 1200 
 1201         return create_entry(parent, key, &record, 0, id, result);
 1202 }
 1203 
 1204 /*
 1205  * hfs_cat_mkdir()
 1206  *
 1207  * Create a new directory with the indicated name in the indicated directory.
 1208  * If successful an (struct hfs_cat_entry) is returned in '*result'.
 1209  */
 1210 int hfs_cat_mkdir(struct hfs_cat_entry *parent, struct hfs_cat_key *key,
 1211                   struct hfs_cat_entry **result)
 1212 {
 1213         struct hfs_cat_rec record;
 1214         hfs_u32 id = new_cnid(parent->mdb);
 1215         hfs_u32 mtime = hfs_time();
 1216 
 1217 #if defined(DEBUG_CATALOG) || defined(DEBUG_ALL)
 1218         hfs_warn("hfs_cat_mkdir: %p/%s res=%p\n", parent, key->CName.Name,
 1219                  result);
 1220 #endif
 1221 
 1222         /* init some fields for the directory record */
 1223         memset(&record, 0, sizeof(record));
 1224         record.cdrType = HFS_CDR_DIR;
 1225         hfs_put_nl(id,     record.u.dir.DirID);
 1226         hfs_put_nl(mtime, record.u.dir.CrDat);
 1227         hfs_put_nl(mtime, record.u.dir.MdDat);
 1228         hfs_put_nl(0,     record.u.dir.BkDat);
 1229         hfs_put_hs(0xff,  record.u.dir.UsrInfo.frView);
 1230 
 1231         return create_entry(parent, key, &record, 1, id, result);
 1232 }
 1233 
 1234 /*
 1235  * hfs_cat_delete()
 1236  *
 1237  * Delete the indicated file or directory.
 1238  * The associated thread is also removed unless ('with_thread'==0).
 1239  */
 1240 int hfs_cat_delete(struct hfs_cat_entry *parent, struct hfs_cat_entry *entry,
 1241                    int with_thread)
 1242 {
 1243         struct hfs_cat_key key;
 1244         struct hfs_mdb *mdb = parent->mdb;
 1245         int is_dir, error = 0;
 1246 
 1247 #if defined(DEBUG_CATALOG) || defined(DEBUG_ALL)
 1248         hfs_warn("hfs_cat_delete: %p/%p type=%d state=%lu, thread=%d\n",
 1249                  parent, entry, entry->type, entry->state, with_thread);
 1250 #endif
 1251         if (parent->mdb != entry->mdb) {
 1252                 return -EINVAL;
 1253         }
 1254 
 1255         if (entry->type == HFS_CDR_FIL) {
 1256                 with_thread = (entry->u.file.flags&HFS_FIL_THD) && with_thread;
 1257                 is_dir = 0;
 1258         } else {
 1259                 is_dir = 1;
 1260         }
 1261 
 1262         /* keep readers from getting confused by changing dir size */
 1263         start_write(parent);
 1264 
 1265         /* don't delete a busy directory */
 1266         if (entry->type == HFS_CDR_DIR) {
 1267                 start_read(entry);
 1268 
 1269                 error = -ENOTEMPTY;
 1270                 if (entry->u.dir.files || entry->u.dir.dirs) 
 1271                         goto hfs_delete_end;
 1272         }
 1273 
 1274         /* try to delete the file or directory */
 1275         lock_entry(entry);
 1276         error = -ENOENT;
 1277         if ((entry->state & HFS_DELETED)) {
 1278                 /* somebody beat us to it. */
 1279                 goto hfs_delete_unlock;
 1280         }
 1281                 
 1282         /* delete the catalog record */
 1283         if ((error = hfs_bdelete(mdb->cat_tree, HFS_BKEY(&entry->key)))) {
 1284                 goto hfs_delete_unlock;
 1285         }
 1286 
 1287         /* Mark the entry deleted and remove it from the cache */
 1288         delete_entry(entry);
 1289 
 1290         /* try to delete the thread entry if it exists */
 1291         if (with_thread) {
 1292                 hfs_cat_build_key(entry->cnid, NULL, &key);
 1293                 (void)hfs_bdelete(mdb->cat_tree, HFS_BKEY(&key));
 1294         }
 1295         
 1296         update_dir(mdb, parent, is_dir, -1);
 1297 
 1298 hfs_delete_unlock:
 1299         unlock_entry(entry);
 1300 
 1301 hfs_delete_end:
 1302         if (entry->type == HFS_CDR_DIR) {
 1303                 end_read(entry);
 1304         }
 1305         end_write(parent);
 1306         return error;
 1307 }
 1308 
 1309 /*
 1310  * hfs_cat_move()
 1311  *
 1312  * Rename a file or directory, possibly to a new directory.
 1313  * If the destination exists it is removed and a
 1314  * (struct hfs_cat_entry) for it is returned in '*result'.
 1315  */
 1316 int hfs_cat_move(struct hfs_cat_entry *old_dir, struct hfs_cat_entry *new_dir,
 1317                  struct hfs_cat_entry *entry, struct hfs_cat_key *new_key,
 1318                  struct hfs_cat_entry **removed)
 1319 {
 1320         struct hfs_cat_entry *dest;
 1321         struct hfs_mdb *mdb;
 1322         int error = 0;
 1323         int is_dir, has_thread;
 1324 
 1325         if (removed) {
 1326                 *removed = NULL;
 1327         }
 1328 
 1329         /* sanity checks */
 1330         if (!old_dir || !new_dir) {
 1331                 return -EINVAL;
 1332         }
 1333         mdb = old_dir->mdb;
 1334         if (mdb != new_dir->mdb) {
 1335                 return -EXDEV;
 1336         }
 1337 
 1338         /* precompute a few things */
 1339         if (entry->type == HFS_CDR_DIR) {
 1340                 is_dir = 1;
 1341                 has_thread = 1;
 1342         } else if (entry->type == HFS_CDR_FIL) {
 1343                 is_dir = 0;
 1344                 has_thread = entry->u.file.flags & HFS_FIL_THD;
 1345         } else {
 1346                 return -EINVAL;
 1347         }
 1348 
 1349         while (mdb->rename_lock) {
 1350                 hfs_sleep_on(&mdb->rename_wait);
 1351         }
 1352         spin_lock(&entry_lock);
 1353         mdb->rename_lock = 1; /* XXX: should be atomic_inc */
 1354         spin_unlock(&entry_lock);
 1355 
 1356         /* keep readers from getting confused by changing dir size */
 1357         start_write(new_dir);
 1358         if (old_dir != new_dir) {
 1359                 start_write(old_dir);
 1360         }
 1361 
 1362         /* Don't move a directory inside itself */
 1363         if (is_dir) {
 1364                 struct hfs_cat_key thd_key;
 1365                 struct hfs_brec brec;
 1366 
 1367                 hfs_u32 id = new_dir->cnid;
 1368                 while (id != htonl(HFS_ROOT_CNID)) {
 1369                         if (id == entry->cnid) {
 1370                                 error = -EINVAL;
 1371                         } else {
 1372                                 hfs_cat_build_key(id, NULL, &thd_key);
 1373                                 error = hfs_bfind(&brec, mdb->cat_tree,
 1374                                                   HFS_BKEY(&thd_key),
 1375                                                   HFS_BFIND_READ_EQ);
 1376                         }
 1377                         if (error) {
 1378                                 goto done;
 1379                         } else {
 1380                                 struct hfs_cat_rec *rec = brec.data;
 1381                                 id = hfs_get_nl(rec->u.thd.ParID);
 1382                                 hfs_brec_relse(&brec, NULL);
 1383                         }
 1384                 }
 1385         }
 1386 
 1387 restart:
 1388         /* see if the destination exists, getting it if it does */
 1389         dest = hfs_cat_get(mdb, new_key);
 1390         if (!dest) {
 1391                 /* destination doesn't exist, so create it */
 1392                 struct hfs_cat_rec new_record;
 1393 
 1394                 /* create a locked entry in the cache */
 1395                 dest = get_entry(mdb, new_key, 0);
 1396                 if (!dest) {
 1397                         error = -EIO;
 1398                         goto done;
 1399                 }
 1400                 if (dest->cnid) {
 1401                         /* The (unlocked) entry exists in the cache */
 1402                         goto have_distinct;
 1403                 }
 1404 
 1405                 /* limit directory valence to signed 16-bit integer */
 1406                 if ((new_dir->u.dir.dirs + new_dir->u.dir.files) >=
 1407                                                         HFS_MAX_VALENCE) {
 1408                         error = -ENOSPC;
 1409                         goto bail3;
 1410                 }
 1411 
 1412                 /* build the new record. make sure to zero out the
 1413                    record. */
 1414                 memset(&new_record, 0, sizeof(new_record));
 1415                 new_record.cdrType = entry->type;
 1416                 __write_entry(entry, &new_record);
 1417 
 1418                 /* insert the new record */
 1419                 error = hfs_binsert(mdb->cat_tree, HFS_BKEY(new_key),
 1420                                     &new_record, is_dir ? 2 + sizeof(DIR_REC) :
 1421                                     2 + sizeof(FIL_REC));
 1422                 if (error == -EEXIST) {
 1423                         delete_entry(dest);
 1424                         unlock_entry(dest);
 1425                         hfs_cat_put(dest);
 1426                         goto restart;
 1427                 } else if (error) {
 1428                         goto bail3;
 1429                 }
 1430 
 1431                 /* update the destination directory */
 1432                 update_dir(mdb, new_dir, is_dir, 1);
 1433         } else if (entry != dest) {
 1434 have_distinct:
 1435                 /* The destination exists and is not same as source */
 1436                 lock_entry(dest);
 1437                 if ((dest->state & HFS_DELETED)) {
 1438                         unlock_entry(dest);
 1439                         hfs_cat_put(dest);
 1440                         goto restart;
 1441                 }
 1442                 if (dest->type != entry->type) {
 1443                         /* can't move a file on top
 1444                            of a dir nor vice versa. */
 1445                         error = is_dir ? -ENOTDIR : -EISDIR;
 1446                 } else if (is_dir && (dest->u.dir.dirs || dest->u.dir.files)) {
 1447                         /* directory to replace is not empty */
 1448                         error = -ENOTEMPTY;
 1449                 }
 1450 
 1451                 if (error) {
 1452                         goto bail2;
 1453                 }
 1454         } else {
 1455                 /* The destination exists but is same as source */
 1456                 --entry->count;
 1457                 dest = NULL;
 1458         }
 1459 
 1460         /* lock the entry */
 1461         lock_entry(entry);
 1462         if ((entry->state & HFS_DELETED)) {
 1463                 error = -ENOENT;
 1464                 goto bail1;
 1465         }
 1466 
 1467         if (dest) {
 1468                 /* remove the old entry */
 1469                 error = hfs_bdelete(mdb->cat_tree, HFS_BKEY(&entry->key));
 1470 
 1471                 if (error) {
 1472                         /* We couldn't remove the entry for the
 1473                            original file, so nothing has changed. */
 1474                         goto bail1;
 1475                 }
 1476                 update_dir(mdb, old_dir, is_dir, -1);
 1477         }
 1478 
 1479         /* update the thread of the dir/file we're moving */
 1480         if (has_thread) {
 1481                 struct hfs_cat_key thd_key;
 1482                 struct hfs_brec brec;
 1483 
 1484                 hfs_cat_build_key(entry->cnid, NULL, &thd_key);
 1485                 error = hfs_bfind(&brec, mdb->cat_tree,
 1486                                   HFS_BKEY(&thd_key), HFS_BFIND_WRITE);
 1487                 if (error == -ENOENT) {
 1488                         if (is_dir) {
 1489                                 /* directory w/o a thread! */
 1490                                 error = -EIO;
 1491                         } else {
 1492                                 /* We were lied to! */
 1493                                 entry->u.file.flags &= ~HFS_FIL_THD;
 1494                                 hfs_cat_mark_dirty(entry);
 1495                         }
 1496                 }
 1497                 if (!error) {
 1498                         struct hfs_cat_rec *rec = brec.data;
 1499                         memcpy(&rec->u.thd.ParID, &new_key->ParID,
 1500                                sizeof(hfs_u32) + sizeof(struct hfs_name));
 1501                         hfs_brec_relse(&brec, NULL);
 1502                 } else if (error == -ENOENT) {
 1503                         error = 0;
 1504                 } else if (!dest) {
 1505                         /* Nothing was changed */
 1506                         unlock_entry(entry);
 1507                         goto done;
 1508                 } else {
 1509                         /* Something went seriously wrong.
 1510                            The dir/file has been deleted. */
 1511                         /* XXX try some recovery? */
 1512                         delete_entry(entry);
 1513                         goto bail1;
 1514                 }
 1515         }
 1516 
 1517         /* TRY to remove the thread for the pre-existing entry */
 1518         if (dest && dest->cnid &&
 1519             (is_dir || (dest->u.file.flags & HFS_FIL_THD))) {
 1520                 struct hfs_cat_key thd_key;
 1521 
 1522                 hfs_cat_build_key(dest->cnid, NULL, &thd_key);
 1523                 (void)hfs_bdelete(mdb->cat_tree, HFS_BKEY(&thd_key));
 1524         }
 1525 
 1526         /* update directories */
 1527         new_dir->modify_date = hfs_time();
 1528         hfs_cat_mark_dirty(new_dir);
 1529 
 1530         /* update key */
 1531         remove_hash(entry);
 1532         memcpy(&entry->key, new_key, sizeof(*new_key));
 1533         /* KEYDIRTY as case might differ */
 1534         entry->state |= HFS_KEYDIRTY;
 1535         insert_hash(entry);
 1536         hfs_cat_mark_dirty(entry);
 1537         unlock_entry(entry);
 1538 
 1539         /* delete any pre-existing or place-holder entry */
 1540         if (dest) {
 1541                 delete_entry(dest);
 1542                 unlock_entry(dest);
 1543                 if (removed && dest->cnid) {
 1544                         *removed = dest;
 1545                 } else {
 1546                         hfs_cat_put(dest);
 1547                 }
 1548         }
 1549         goto done;
 1550 
 1551 bail1:
 1552         unlock_entry(entry);
 1553 bail2:
 1554         if (dest) {
 1555                 if (!dest->cnid) {
 1556                         /* TRY to remove the new entry */
 1557                         (void)hfs_bdelete(mdb->cat_tree, HFS_BKEY(new_key));
 1558                         update_dir(mdb, new_dir, is_dir, -1);
 1559 bail3:
 1560                         delete_entry(dest);
 1561                 }
 1562                 unlock_entry(dest);
 1563                 hfs_cat_put(dest);
 1564         }
 1565 done:
 1566         if (new_dir != old_dir) {
 1567                 end_write(old_dir);
 1568         }
 1569         end_write(new_dir);
 1570         spin_lock(&entry_lock);
 1571         mdb->rename_lock = 0; /* XXX: should use atomic_dec */
 1572         hfs_wake_up(&mdb->rename_wait);
 1573         spin_unlock(&entry_lock);
 1574 
 1575         return error;
 1576 }
 1577 
 1578 /*
 1579  * Initialize the hash tables
 1580  */
 1581 void hfs_cat_init(void)
 1582 {
 1583         int i;
 1584         struct list_head *head = hash_table;
 1585 
 1586         i = C_HASHSIZE;
 1587         do {
 1588                 INIT_LIST_HEAD(head);
 1589                 head++;
 1590                 i--;
 1591         } while (i);
 1592 }

Cache object: 365421f6353a130aa520c8bff2a8ead2


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.