2 * linux/fs/hfs/extent.c
4 * Copyright (C) 1995-1997 Paul H. Hargrove
5 * This file may be distributed under the terms of the GNU General Public License.
7 * This file contains the functions related to the extents B-tree.
9 * "XXX" in a comment is a note to myself to consider changing something.
11 * In function preconditions the term "valid" applied to a pointer to
12 * a structure means that the pointer is non-NULL and the structure it
13 * points to has all fields initialized to consistent values.
18 /*================ File-local data type ================*/
20 /* An extent record on disk*/
21 struct hfs_raw_extent {
30 /*================ File-local functions ================*/
35 static inline void build_key(struct hfs_ext_key *key,
36 const struct hfs_fork *fork, hfs_u16 block)
39 key->FkType = fork->fork;
40 hfs_put_nl(fork->entry->cnid, key->FNum);
41 hfs_put_hs(block, key->FABN);
48 * Get an exclusive lock on the B-tree bitmap.
50 static inline void lock_bitmap(struct hfs_mdb *mdb) {
51 while (mdb->bitmap_lock) {
52 hfs_sleep_on(&mdb->bitmap_wait);
60 * Relinquish an exclusive lock on the B-tree bitmap.
62 static inline void unlock_bitmap(struct hfs_mdb *mdb) {
64 hfs_wake_up(&mdb->bitmap_wait);
70 * prints the content of a extent for debugging purposes.
72 #if defined(DEBUG_EXTENTS) || defined(DEBUG_ALL)
73 static void dump_ext(const char *msg, const struct hfs_extent *e) {
75 hfs_warn("%s (%d-%d) (%d-%d) (%d-%d)\n", msg,
77 e->start + e->length[0] - 1,
78 e->start + e->length[0],
79 e->start + e->length[0] + e->length[1] - 1,
80 e->start + e->length[0] + e->length[1],
83 hfs_warn("%s NULL\n", msg);
87 #define dump_ext(A,B) {}
93 * Initializes a (struct hfs_extent) from a (struct hfs_raw_extent) and
94 * the number of the starting block for the extent.
96 * Note that the callers must check that to,from != NULL
98 static void read_extent(struct hfs_extent *to,
99 const struct hfs_raw_extent *from,
103 to->block[0] = hfs_get_hs(from->block1);
104 to->length[0] = hfs_get_hs(from->length1);
105 to->block[1] = hfs_get_hs(from->block2);
106 to->length[1] = hfs_get_hs(from->length2);
107 to->block[2] = hfs_get_hs(from->block3);
108 to->length[2] = hfs_get_hs(from->length3);
109 to->end = start + to->length[0] + to->length[1] + to->length[2] - 1;
110 to->next = to->prev = NULL;
117 * Initializes a (struct hfs_raw_extent) from a (struct hfs_extent).
119 * Note that the callers must check that to,from != NULL
121 static void write_extent(struct hfs_raw_extent *to,
122 const struct hfs_extent *from)
124 hfs_put_hs(from->block[0], to->block1);
125 hfs_put_hs(from->length[0], to->length1);
126 hfs_put_hs(from->block[1], to->block2);
127 hfs_put_hs(from->length[1], to->length2);
128 hfs_put_hs(from->block[2], to->block3);
129 hfs_put_hs(from->length[2], to->length3);
135 * Given an extent record and allocation block offset into the file,
136 * return the number of the corresponding allocation block on disk,
137 * or -1 if the desired block is not mapped by the given extent.
139 * Note that callers must check that extent != NULL
141 static int decode_extent(const struct hfs_extent * extent, int block)
143 if (!extent || (block < extent->start) || (block > extent->end) ||
144 (extent->end == (hfs_u16)(extent->start - 1))) {
147 block -= extent->start;
148 if (block < extent->length[0]) {
149 return block + extent->block[0];
151 block -= extent->length[0];
152 if (block < extent->length[1]) {
153 return block + extent->block[1];
155 return block + extent->block[2] - extent->length[1];
161 * Reduce the reference count of an in-core extent record by one,
162 * removing it from memory if the count falls to zero.
164 static void relse_ext(struct hfs_extent *ext)
166 if (--ext->count || !ext->start) {
169 ext->prev->next = ext->next;
171 ext->next->prev = ext->prev;
179 * Changes the 'cache' field of the fork.
181 static inline void set_cache(struct hfs_fork *fork, struct hfs_extent *ext)
183 struct hfs_extent *tmp = fork->cache;
193 * Given a pointer to a (struct hfs_file) and an allocation block
194 * number in the file, find the extent record containing that block.
195 * Returns a pointer to the extent record on success or NULL on failure.
196 * The 'cache' field of 'fil' also points to the extent so it has a
197 * reference count of at least 2.
199 * Callers must check that fil != NULL
201 static struct hfs_extent * find_ext(struct hfs_fork *fork, int alloc_block)
203 struct hfs_cat_entry *entry = fork->entry;
204 struct hfs_btree *tr= entry->mdb->ext_tree;
205 struct hfs_ext_key target, *key;
206 struct hfs_brec brec;
207 struct hfs_extent *ext, *ptr;
210 if (alloc_block < 0) {
216 if (!ext || (alloc_block < ext->start)) {
219 while (ext->next && (alloc_block > ext->end)) {
222 if ((alloc_block <= ext->end) && (alloc_block >= ext->start)) {
226 /* time to read more extents */
231 build_key(&target, fork, alloc_block);
233 tmp = hfs_bfind(&brec, tr, HFS_BKEY(&target), HFS_BFIND_READ_LE);
238 key = (struct hfs_ext_key *)brec.key;
239 if ((hfs_get_nl(key->FNum) != hfs_get_nl(target.FNum)) ||
240 (key->FkType != fork->fork)) {
244 read_extent(ext, brec.data, hfs_get_hs(key->FABN));
245 hfs_brec_relse(&brec, NULL);
247 if ((alloc_block > ext->end) && (alloc_block < ext->start)) {
248 /* something strange happened */
253 if (!ptr || (alloc_block < ptr->start)) {
256 while (ptr->next && (alloc_block > ptr->end)) {
259 if (ext->start == ptr->start) {
260 /* somebody beat us to it. */
263 } else if (ext->start < ptr->start) {
264 /* insert just before ptr */
265 ptr->prev->next = ext;
266 ext->prev = ptr->prev;
275 ++ext->count; /* for return value */
276 set_cache(fork, ext);
280 hfs_brec_relse(&brec, NULL);
291 * Deletes an extent record from a fork, reducing its physical length.
293 * struct hfs_fork *fork: the fork
294 * struct hfs_extent *ext: the current last extent for 'fork'
295 * Output Variable(s):
300 * 'fork' points to a valid (struct hfs_fork)
301 * 'ext' point to a valid (struct hfs_extent) which is the last in 'fork'
302 * and which is not also the first extent in 'fork'.
304 * The extent record has been removed if possible, and a warning has been
307 static void delete_extent(struct hfs_fork *fork, struct hfs_extent *ext)
309 struct hfs_mdb *mdb = fork->entry->mdb;
310 struct hfs_ext_key key;
313 if (fork->cache == ext) {
314 set_cache(fork, ext->prev);
316 ext->prev->next = NULL;
317 if (ext->count != 1) {
318 hfs_warn("hfs_truncate: extent has count %d.\n", ext->count);
322 error = hfs_clear_vbm_bits(mdb, ext->block[2], ext->length[2]);
324 hfs_warn("hfs_truncate: error %d freeing blocks.\n", error);
326 error = hfs_clear_vbm_bits(mdb, ext->block[1], ext->length[1]);
328 hfs_warn("hfs_truncate: error %d freeing blocks.\n", error);
330 error = hfs_clear_vbm_bits(mdb, ext->block[0], ext->length[0]);
332 hfs_warn("hfs_truncate: error %d freeing blocks.\n", error);
336 build_key(&key, fork, ext->start);
338 error = hfs_bdelete(mdb->ext_tree, HFS_BKEY(&key));
340 hfs_warn("hfs_truncate: error %d deleting an extent.\n", error);
350 * Adds a new extent record to a fork, extending its physical length.
352 * struct hfs_fork *fork: the fork to extend
353 * struct hfs_extent *ext: the current last extent for 'fork'
354 * hfs_u16 ablock: the number of allocation blocks in 'fork'.
355 * hfs_u16 start: first allocation block to add to 'fork'.
356 * hfs_u16 len: the number of allocation blocks to add to 'fork'.
357 * hfs_u32 ablksz: number of sectors in an allocation block.
358 * Output Variable(s):
361 * (struct hfs_extent *) the new extent or NULL
363 * 'fork' points to a valid (struct hfs_fork)
364 * 'ext' point to a valid (struct hfs_extent) which is the last in 'fork'
365 * 'ablock', 'start', 'len' and 'ablksz' are what they claim to be.
367 * If NULL is returned then no changes have been made to 'fork'.
368 * If the return value is non-NULL that it is the extent that has been
369 * added to 'fork' both in memory and on disk. The 'psize' field of
370 * 'fork' has been updated to reflect the new physical size.
372 static struct hfs_extent *new_extent(struct hfs_fork *fork,
373 struct hfs_extent *ext,
374 hfs_u16 ablock, hfs_u16 start,
375 hfs_u16 len, hfs_u16 ablksz)
377 struct hfs_raw_extent raw;
378 struct hfs_ext_key key;
381 if (fork->entry->cnid == htonl(HFS_EXT_CNID)) {
382 /* Limit extents tree to the record in the MDB */
386 if (!HFS_NEW(ext->next)) {
389 ext->next->prev = ext;
390 ext->next->next = NULL;
392 relse_ext(ext->prev);
395 ext->block[0] = start;
396 ext->length[0] = len;
401 ext->end = ablock + len - 1;
404 write_extent(&raw, ext);
406 build_key(&key, fork, ablock);
408 error = hfs_binsert(fork->entry->mdb->ext_tree,
409 HFS_BKEY(&key), &raw, sizeof(raw));
411 ext->prev->next = NULL;
415 set_cache(fork, ext);
422 * Given a (struct hfs_fork) write an extent record back to disk.
424 static void update_ext(struct hfs_fork *fork, struct hfs_extent *ext)
426 struct hfs_ext_key target;
427 struct hfs_brec brec;
430 build_key(&target, fork, ext->start);
432 if (!hfs_bfind(&brec, fork->entry->mdb->ext_tree,
433 HFS_BKEY(&target), HFS_BFIND_WRITE)) {
434 write_extent(brec.data, ext);
435 hfs_brec_relse(&brec, NULL);
443 * Zeros-out 'num' allocation blocks beginning with 'start'.
445 static int zero_blocks(struct hfs_mdb *mdb, int start, int num) {
450 start = mdb->fs_start + start * mdb->alloc_blksz;
451 end = start + num * mdb->alloc_blksz;
453 for (j=start; j<end; ++j) {
454 if (hfs_buffer_ok(buf = hfs_buffer_get(mdb->sys_mdb, j, 0))) {
455 memset(hfs_buffer_data(buf), 0, HFS_SECTOR_SIZE);
456 hfs_buffer_dirty(buf);
466 * Try to remove enough allocation blocks from 'fork'
467 * so that it is 'ablocks' allocation blocks long.
469 static void shrink_fork(struct hfs_fork *fork, int ablocks)
471 struct hfs_mdb *mdb = fork->entry->mdb;
472 struct hfs_extent *ext;
473 int i, error, next, count;
474 hfs_u32 ablksz = mdb->alloc_blksz;
476 next = (fork->psize / ablksz) - 1;
477 ext = find_ext(fork, next);
478 while (ext && ext->start && (ext->start >= ablocks)) {
479 next = ext->start - 1;
480 delete_extent(fork, ext);
481 ext = find_ext(fork, next);
484 fork->psize = (next + 1) * ablksz;
488 if ((count = next + 1 - ablocks) > 0) {
489 for (i=2; (i>=0) && !ext->length[i]; --i) {};
491 while (count && (ext->length[i] <= count)) {
492 ext->end -= ext->length[i];
493 count -= ext->length[i];
494 error = hfs_clear_vbm_bits(mdb, ext->block[i],
497 hfs_warn("hfs_truncate: error %d freeing "
500 ext->block[i] = ext->length[i] = 0;
505 ext->length[i] -= count;
506 error = hfs_clear_vbm_bits(mdb, ext->block[i] +
507 ext->length[i], count);
509 hfs_warn("hfs_truncate: error %d freeing "
514 update_ext(fork, ext);
517 fork->psize = ablocks * ablksz;
523 * Try to add enough allocation blocks to 'fork'
524 * so that it is 'ablock' allocation blocks long.
526 static int grow_fork(struct hfs_fork *fork, int ablocks)
528 struct hfs_cat_entry *entry = fork->entry;
529 struct hfs_mdb *mdb = entry->mdb;
530 struct hfs_extent *ext;
533 hfs_u32 ablksz = mdb->alloc_blksz;
534 hfs_u32 blocks, clumpablks;
536 blocks = fork->psize;
537 need = ablocks - blocks/ablksz;
538 if (need < 1) { /* no need to grow the fork */
542 /* round up to clumpsize */
543 if (entry->u.file.clumpablks) {
544 clumpablks = entry->u.file.clumpablks;
546 clumpablks = mdb->clumpablks;
548 need = ((need + clumpablks - 1) / clumpablks) * clumpablks;
550 /* find last extent record and try to extend it */
551 if (!(ext = find_ext(fork, blocks/ablksz - 1))) {
552 /* somehow we couldn't find the end of the file! */
556 /* determine which is the last used extent in the record */
557 /* then try to allocate the blocks immediately following it */
558 for (i=2; (i>=0) && !ext->length[i]; --i) {};
560 /* try to extend the last extent */
561 start = ext->block[i] + ext->length[i];
565 len = hfs_vbm_count_free(mdb, start);
573 err = hfs_set_vbm_bits(mdb, start, len);
580 zero_blocks(mdb, start, len);
582 ext->length[i] += len;
584 blocks = (fork->psize += len * ablksz);
586 update_ext(fork, ext);
590 /* add some more extents */
595 start = hfs_vbm_search_free(mdb, &len);
599 err = hfs_set_vbm_bits(mdb, start, len);
605 zero_blocks(mdb, start, len);
607 /* determine which is the first free extent in the record */
608 for (i=0; (i<3) && ext->length[i]; ++i) {};
610 ext->block[i] = start;
611 ext->length[i] = len;
613 update_ext(fork, ext);
615 if (!(ext = new_extent(fork, ext, blocks/ablksz,
616 start, len, ablksz))) {
618 hfs_clear_vbm_bits(mdb, start, len);
623 blocks = (fork->psize += len * ablksz);
626 set_cache(fork, ext);
631 /*================ Global functions ================*/
637 * This is the comparison function used for the extents B-tree. In
638 * comparing extent B-tree entries, the file id is the most
639 * significant field (compared as unsigned ints); the fork type is
640 * the second most significant field (compared as unsigned chars);
641 * and the allocation block number field is the least significant
642 * (compared as unsigned ints).
644 * struct hfs_ext_key *key1: pointer to the first key to compare
645 * struct hfs_ext_key *key2: pointer to the second key to compare
646 * Output Variable(s):
649 * int: negative if key1<key2, positive if key1>key2, and 0 if key1==key2
651 * key1 and key2 point to "valid" (struct hfs_ext_key)s.
653 * This function has no side-effects */
654 int hfs_ext_compare(const struct hfs_ext_key *key1,
655 const struct hfs_ext_key *key2)
660 tmp = hfs_get_hl(key1->FNum) - hfs_get_hl(key2->FNum);
664 tmp = (unsigned char)key1->FkType - (unsigned char)key2->FkType;
668 retval = (int)(hfs_get_hs(key1->FABN)
669 - hfs_get_hs(key2->FABN));
678 * Given an hfs_fork shrink or grow the fork to hold the
679 * forks logical size.
681 void hfs_extent_adj(struct hfs_fork *fork)
684 hfs_u32 blks, ablocks, ablksz;
686 if (fork->lsize > HFS_FORK_MAX) {
687 fork->lsize = HFS_FORK_MAX;
690 blks = (fork->lsize+HFS_SECTOR_SIZE-1) >> HFS_SECTOR_SIZE_BITS;
691 ablksz = fork->entry->mdb->alloc_blksz;
692 ablocks = (blks + ablksz - 1) / ablksz;
694 if (blks > fork->psize) {
695 grow_fork(fork, ablocks);
696 if (blks > fork->psize) {
698 fork->psize >> HFS_SECTOR_SIZE_BITS;
700 } else if (blks < fork->psize) {
701 shrink_fork(fork, ablocks);
709 * Given an hfs_fork and a block number within the fork, return the
710 * number of the corresponding physical block on disk, or zero on
713 int hfs_extent_map(struct hfs_fork *fork, int block, int create)
715 int ablksz, ablock, offset, tmp;
716 struct hfs_extent *ext;
718 if (!fork || !fork->entry || !fork->entry->mdb) {
722 #if defined(DEBUG_EXTENTS) || defined(DEBUG_ALL)
723 hfs_warn("hfs_extent_map: ablock %d of file %d, fork %d\n",
724 block, fork->entry->cnid, fork->fork);
728 hfs_warn("hfs_extent_map: block < 0\n");
731 if (block > (HFS_FORK_MAX >> HFS_SECTOR_SIZE_BITS)) {
732 hfs_warn("hfs_extent_map: block(0x%08x) > big; cnid=%d "
733 "fork=%d\n", block, fork->entry->cnid, fork->fork);
736 ablksz = fork->entry->mdb->alloc_blksz;
737 offset = fork->entry->mdb->fs_start + (block % ablksz);
738 ablock = block / ablksz;
740 if (block >= fork->psize) {
741 if (!create || (grow_fork(fork, ablock + 1) < 0))
745 #if defined(DEBUG_EXTENTS) || defined(DEBUG_ALL)
746 hfs_warn("(lblock %d offset %d)\n", ablock, offset);
749 if ((ext = find_ext(fork, ablock))) {
750 dump_ext("trying new: ", ext);
751 tmp = decode_extent(ext, ablock);
754 return tmp*ablksz + offset;
764 * Copy the first extent record from a (struct hfs_fork) to a (struct
765 * raw_extent), record (normally the one in the catalog entry).
767 void hfs_extent_out(const struct hfs_fork *fork, hfs_byte_t dummy[12])
769 struct hfs_raw_extent *ext = (struct hfs_raw_extent *)dummy;
772 write_extent(ext, &fork->first);
773 dump_ext("extent out: ", &fork->first);
780 * Copy an raw_extent to the 'first' and 'cache' fields of an hfs_fork.
782 void hfs_extent_in(struct hfs_fork *fork, const hfs_byte_t dummy[12])
784 const struct hfs_raw_extent *ext =
785 (const struct hfs_raw_extent *)dummy;
788 read_extent(&fork->first, ext, 0);
789 fork->cache = &fork->first;
790 fork->first.count = 2;
791 dump_ext("extent in: ", &fork->first);
798 * Removes from memory all extents associated with 'fil'.
800 void hfs_extent_free(struct hfs_fork *fork)
803 set_cache(fork, &fork->first);
805 if (fork->first.next) {
806 hfs_warn("hfs_extent_free: extents in use!\n");