fs/hfs/catalog.c

   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 }