File: /usr/src/linux/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 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 }
1593