]> git.saurik.com Git - apple/xnu.git/blob - bsd/hfs/hfscommon/Misc/VolumeAllocation.c
projects / apple / xnu.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
xnu-1228.5.18.tar.gz
[apple/xnu.git] / bsd / hfs / hfscommon / Misc / VolumeAllocation.c
1 /*
2 * Copyright (c) 2000-2007 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28 /*
29 File: VolumeAllocation.c
30
31 Contains: Routines for accessing and modifying the volume bitmap.
32
33 Version: HFS Plus 1.0
34
35 Copyright: © 1996-2001 by Apple Computer, Inc., all rights reserved.
36
37 */
38
39 /*
40 Public routines:
41 BlockAllocate
42 Allocate space on a volume. Can allocate space contiguously.
43 If not contiguous, then allocation may be less than what was
44 asked for. Returns the starting block number, and number of
45 blocks. (Will only do a single extent???)
46 BlockDeallocate
47 Deallocate a contiguous run of allocation blocks.
48
49
50 Internal routines:
51 BlockMarkFree
52 Mark a contiguous range of blocks as free. The corresponding
53 bits in the volume bitmap will be cleared.
54 BlockMarkAllocated
55 Mark a contiguous range of blocks as allocated. The cor-
56 responding bits in the volume bitmap are set. Also tests to see
57 if any of the blocks were previously unallocated.
58 FindContiguous
59 Find a contiguous range of blocks of a given size. The caller
60 specifies where to begin the search (by block number). The
61 block number of the first block in the range is returned.
62 BlockAllocateAny
63 Find and allocate a contiguous range of blocks up to a given size. The
64 first range of contiguous free blocks found are allocated, even if there
65 are fewer blocks than requested (and even if a contiguous range of blocks
66 of the given size exists elsewhere).
67 BlockAllocateContig
68 Find and allocate a contiguous range of blocks of a given size. If
69 a contiguous range of free blocks of the given size isn't found, then
70 the allocation fails (i.e. it is "all or nothing").
71
72 BlockAllocateKnown
73 Try to allocate space from known free space in the volume's
74 free extent cache.
75
76 ReadBitmapBlock
77 Given an allocation block number, read the bitmap block that
78 contains that allocation block into a caller-supplied buffer.
79
80 ReleaseBitmapBlock
81 Release a bitmap block back into the buffer cache.
82 */
83
84 #include "../../hfs_macos_defs.h"
85
86 #include <sys/types.h>
87 #include <sys/buf.h>
88 #include <sys/systm.h>
89
90 #include "../../hfs.h"
91 #include "../../hfs_dbg.h"
92 #include "../../hfs_format.h"
93 #include "../../hfs_endian.h"
94
95 #include "../headers/FileMgrInternal.h"
96
97
98 enum {
99 kBytesPerWord = 4,
100 kBitsPerByte = 8,
101 kBitsPerWord = 32,
102
103 kBitsWithinWordMask = kBitsPerWord-1
104 };
105
106 #define kLowBitInWordMask 0x00000001ul
107 #define kHighBitInWordMask 0x80000000ul
108 #define kAllBitsSetInWord 0xFFFFFFFFul
109
110
111 static OSErr ReadBitmapBlock(
112 ExtendedVCB *vcb,
113 u_int32_t bit,
114 u_int32_t **buffer,
115 u_int32_t *blockRef);
116
117 static OSErr ReleaseBitmapBlock(
118 ExtendedVCB *vcb,
119 u_int32_t blockRef,
120 Boolean dirty);
121
122 static OSErr BlockAllocateAny(
123 ExtendedVCB *vcb,
124 u_int32_t startingBlock,
125 u_int32_t endingBlock,
126 u_int32_t maxBlocks,
127 Boolean useMetaZone,
128 u_int32_t *actualStartBlock,
129 u_int32_t *actualNumBlocks);
130
131 static OSErr BlockAllocateContig(
132 ExtendedVCB *vcb,
133 u_int32_t startingBlock,
134 u_int32_t minBlocks,
135 u_int32_t maxBlocks,
136 Boolean useMetaZone,
137 u_int32_t *actualStartBlock,
138 u_int32_t *actualNumBlocks);
139
140 static OSErr BlockFindContiguous(
141 ExtendedVCB *vcb,
142 u_int32_t startingBlock,
143 u_int32_t endingBlock,
144 u_int32_t minBlocks,
145 u_int32_t maxBlocks,
146 Boolean useMetaZone,
147 u_int32_t *actualStartBlock,
148 u_int32_t *actualNumBlocks);
149
150 static OSErr BlockAllocateKnown(
151 ExtendedVCB *vcb,
152 u_int32_t maxBlocks,
153 u_int32_t *actualStartBlock,
154 u_int32_t *actualNumBlocks);
155
156
157 /*
158 ;________________________________________________________________________________
159 ;
160 ; Routine: BlkAlloc
161 ;
162 ; Function: Allocate space on a volume. If contiguous allocation is requested,
163 ; at least the requested number of bytes will be allocated or an
164 ; error will be returned. If contiguous allocation is not forced,
165 ; the space will be allocated at the first free fragment following
166 ; the requested starting allocation block. If there is not enough
167 ; room there, a block of less than the requested size will be
168 ; allocated.
169 ;
170 ; If the requested starting block is 0 (for new file allocations),
171 ; the volume's allocation block pointer will be used as a starting
172 ; point.
173 ;
174 ; Input Arguments:
175 ; vcb - Pointer to ExtendedVCB for the volume to allocate space on
176 ; fcb - Pointer to FCB for the file for which storage is being allocated
177 ; startingBlock - Preferred starting allocation block, 0 = no preference
178 ; forceContiguous - Force contiguous flag - if bit 0 set (NE), allocation is contiguous
179 ; or an error is returned
180 ; useMetaZone -
181 ; minBlocks - Number of blocks requested. If the allocation is non-contiguous,
182 ; less than this may actually be allocated
183 ; maxBlocks - The maximum number of blocks to allocate. If there is additional free
184 ; space after bytesRequested, then up to maxBlocks bytes should really
185 ; be allocated. (Used by ExtendFileC to round up allocations to a multiple
186 ; of the file's clump size.)
187 ;
188 ; Output:
189 ; (result) - Error code, zero for successful allocation
190 ; *startBlock - Actual starting allocation block
191 ; *actualBlocks - Actual number of allocation blocks allocated
192 ;
193 ; Side effects:
194 ; The volume bitmap is read and updated; the volume bitmap cache may be changed.
195 ;________________________________________________________________________________
196 */
197
198 __private_extern__
199 OSErr BlockAllocate (
200 ExtendedVCB *vcb, /* which volume to allocate space on */
201 u_int32_t startingBlock, /* preferred starting block, or 0 for no preference */
202 u_int32_t minBlocks, /* desired number of blocks to allocate */
203 u_int32_t maxBlocks, /* maximum number of blocks to allocate */
204 Boolean forceContiguous, /* non-zero to force contiguous allocation and to force */
205 /* minBlocks bytes to actually be allocated */
206
207 Boolean useMetaZone,
208 u_int32_t *actualStartBlock, /* actual first block of allocation */
209 u_int32_t *actualNumBlocks) /* number of blocks actually allocated; if forceContiguous */
210 /* was zero, then this may represent fewer than minBlocks */
211 {
212 u_int32_t freeBlocks;
213 OSErr err;
214 Boolean updateAllocPtr = false; // true if nextAllocation needs to be updated
215
216 //
217 // Initialize outputs in case we get an error
218 //
219 *actualStartBlock = 0;
220 *actualNumBlocks = 0;
221 freeBlocks = hfs_freeblks(VCBTOHFS(vcb), 0);
222
223 //
224 // If the disk is already full, don't bother.
225 //
226 if (freeBlocks == 0) {
227 err = dskFulErr;
228 goto Exit;
229 }
230 if (forceContiguous && freeBlocks < minBlocks) {
231 err = dskFulErr;
232 goto Exit;
233 }
234 /*
235 * Clip if necessary so we don't over-subscribe the free blocks.
236 */
237 if (minBlocks > freeBlocks) {
238 minBlocks = freeBlocks;
239 }
240 if (maxBlocks > freeBlocks) {
241 maxBlocks = freeBlocks;
242 }
243
244 //
245 // If caller didn't specify a starting block number, then use the volume's
246 // next block to allocate from.
247 //
248 if (startingBlock == 0) {
249 HFS_MOUNT_LOCK(vcb, TRUE);
250 startingBlock = vcb->nextAllocation;
251 HFS_MOUNT_UNLOCK(vcb, TRUE);
252 updateAllocPtr = true;
253 }
254 if (startingBlock >= vcb->allocLimit) {
255 startingBlock = 0; /* overflow so start at beginning */
256 }
257
258 //
259 // If the request must be contiguous, then find a sequence of free blocks
260 // that is long enough. Otherwise, find the first free block.
261 //
262 if (forceContiguous) {
263 err = BlockAllocateContig(vcb, startingBlock, minBlocks, maxBlocks,
264 useMetaZone, actualStartBlock, actualNumBlocks);
265 /*
266 * If we allocated from a new position then
267 * also update the roving allocator.
268 */
269 if ((err == noErr) &&
270 (*actualStartBlock > startingBlock) &&
271 ((*actualStartBlock < VCBTOHFS(vcb)->hfs_metazone_start) ||
272 (*actualStartBlock > VCBTOHFS(vcb)->hfs_metazone_end))) {
273 HFS_MOUNT_LOCK(vcb, TRUE);
274 HFS_UPDATE_NEXT_ALLOCATION(vcb, *actualStartBlock);
275 HFS_MOUNT_UNLOCK(vcb, TRUE);
276 }
277 } else {
278 /*
279 * Scan the bitmap once, gather the N largest free extents, then
280 * allocate from these largest extents. Repeat as needed until
281 * we get all the space we needed. We could probably build up
282 * that list when the higher level caller tried (and failed) a
283 * contiguous allocation first.
284 */
285 err = BlockAllocateKnown(vcb, maxBlocks, actualStartBlock, actualNumBlocks);
286 if (err == dskFulErr)
287 err = BlockAllocateAny(vcb, startingBlock, vcb->allocLimit,
288 maxBlocks, useMetaZone, actualStartBlock,
289 actualNumBlocks);
290 if (err == dskFulErr)
291 err = BlockAllocateAny(vcb, 1, startingBlock, maxBlocks,
292 useMetaZone, actualStartBlock,
293 actualNumBlocks);
294 }
295
296 Exit:
297 // if we actually allocated something then go update the
298 // various bits of state that we maintain regardless of
299 // whether there was an error (i.e. partial allocations
300 // still need to update things like the free block count).
301 //
302 if (*actualNumBlocks != 0) {
303 //
304 // If we used the volume's roving allocation pointer, then we need to update it.
305 // Adding in the length of the current allocation might reduce the next allocate
306 // call by avoiding a re-scan of the already allocated space. However, the clump
307 // just allocated can quite conceivably end up being truncated or released when
308 // the file is closed or its EOF changed. Leaving the allocation pointer at the
309 // start of the last allocation will avoid unnecessary fragmentation in this case.
310 //
311 HFS_MOUNT_LOCK(vcb, TRUE);
312
313 if (updateAllocPtr &&
314 ((*actualStartBlock < VCBTOHFS(vcb)->hfs_metazone_start) ||
315 (*actualStartBlock > VCBTOHFS(vcb)->hfs_metazone_end))) {
316 HFS_UPDATE_NEXT_ALLOCATION(vcb, *actualStartBlock);
317 }
318 //
319 // Update the number of free blocks on the volume
320 //
321 vcb->freeBlocks -= *actualNumBlocks;
322 MarkVCBDirty(vcb);
323 HFS_MOUNT_UNLOCK(vcb, TRUE);
324
325 hfs_generate_volume_notifications(VCBTOHFS(vcb));
326 }
327
328 return err;
329 }
330
331
332 /*
333 ;________________________________________________________________________________
334 ;
335 ; Routine: BlkDealloc
336 ;
337 ; Function: Update the bitmap to deallocate a run of disk allocation blocks
338 ;
339 ; Input Arguments:
340 ; vcb - Pointer to ExtendedVCB for the volume to free space on
341 ; firstBlock - First allocation block to be freed
342 ; numBlocks - Number of allocation blocks to free up (must be > 0!)
343 ;
344 ; Output:
345 ; (result) - Result code
346 ;
347 ; Side effects:
348 ; The volume bitmap is read and updated; the volume bitmap cache may be changed.
349 ;________________________________________________________________________________
350 */
351
352 __private_extern__
353 OSErr BlockDeallocate (
354 ExtendedVCB *vcb, // Which volume to deallocate space on
355 u_int32_t firstBlock, // First block in range to deallocate
356 u_int32_t numBlocks) // Number of contiguous blocks to deallocate
357 {
358 OSErr err;
359
360 //
361 // If no blocks to deallocate, then exit early
362 //
363 if (numBlocks == 0) {
364 err = noErr;
365 goto Exit;
366 }
367
368 //
369 // Call internal routine to free the sequence of blocks
370 //
371 err = BlockMarkFree(vcb, firstBlock, numBlocks);
372 if (err)
373 goto Exit;
374
375 //
376 // Update the volume's free block count, and mark the VCB as dirty.
377 //
378 HFS_MOUNT_LOCK(vcb, TRUE);
379 vcb->freeBlocks += numBlocks;
380 if (vcb->nextAllocation == (firstBlock + numBlocks))
381 HFS_UPDATE_NEXT_ALLOCATION(vcb, (vcb->nextAllocation - numBlocks));
382 MarkVCBDirty(vcb);
383 HFS_MOUNT_UNLOCK(vcb, TRUE);
384
385 hfs_generate_volume_notifications(VCBTOHFS(vcb));
386 Exit:
387
388 return err;
389 }
390
391
392 u_int8_t freebitcount[16] = {
393 4, 3, 3, 2, 3, 2, 2, 1, /* 0 1 2 3 4 5 6 7 */
394 3, 2, 2, 1, 2, 1, 1, 0, /* 8 9 A B C D E F */
395 };
396
397 __private_extern__
398 u_int32_t
399 MetaZoneFreeBlocks(ExtendedVCB *vcb)
400 {
401 u_int32_t freeblocks;
402 u_int32_t *currCache;
403 u_int32_t blockRef;
404 u_int32_t bit;
405 u_int32_t lastbit;
406 int bytesleft;
407 int bytesperblock;
408 u_int8_t byte;
409 u_int8_t *buffer;
410
411 blockRef = 0;
412 bytesleft = freeblocks = 0;
413 buffer = NULL;
414 bit = VCBTOHFS(vcb)->hfs_metazone_start;
415 if (bit == 1)
416 bit = 0;
417
418 lastbit = VCBTOHFS(vcb)->hfs_metazone_end;
419 bytesperblock = vcb->vcbVBMIOSize;
420
421 /*
422 * Count all the bits from bit to lastbit.
423 */
424 while (bit < lastbit) {
425 /*
426 * Get next bitmap block.
427 */
428 if (bytesleft == 0) {
429 if (blockRef) {
430 (void) ReleaseBitmapBlock(vcb, blockRef, false);
431 blockRef = 0;
432 }
433 if (ReadBitmapBlock(vcb, bit, &currCache, &blockRef) != 0) {
434 return (0);
435 }
436 buffer = (u_int8_t *)currCache;
437 bytesleft = bytesperblock;
438 }
439 byte = *buffer++;
440 freeblocks += freebitcount[byte & 0x0F];
441 freeblocks += freebitcount[(byte >> 4) & 0x0F];
442 bit += kBitsPerByte;
443 --bytesleft;
444 }
445 if (blockRef)
446 (void) ReleaseBitmapBlock(vcb, blockRef, false);
447
448 return (freeblocks);
449 }
450
451
452 /*
453 * Obtain the next allocation block (bit) that's
454 * outside the metadata allocation zone.
455 */
456 static u_int32_t NextBitmapBlock(
457 ExtendedVCB *vcb,
458 u_int32_t bit)
459 {
460 struct hfsmount *hfsmp = VCBTOHFS(vcb);
461
462 if ((hfsmp->hfs_flags & HFS_METADATA_ZONE) == 0)
463 return (bit);
464 /*
465 * Skip over metadata allocation zone.
466 */
467 if ((bit >= hfsmp->hfs_metazone_start) &&
468 (bit <= hfsmp->hfs_metazone_end)) {
469 bit = hfsmp->hfs_metazone_end + 1;
470 }
471 return (bit);
472 }
473
474
475 /*
476 ;_______________________________________________________________________
477 ;
478 ; Routine: ReadBitmapBlock
479 ;
480 ; Function: Read in a bitmap block corresponding to a given allocation
481 ; block (bit). Return a pointer to the bitmap block.
482 ;
483 ; Inputs:
484 ; vcb -- Pointer to ExtendedVCB
485 ; bit -- Allocation block whose bitmap block is desired
486 ;
487 ; Outputs:
488 ; buffer -- Pointer to bitmap block corresonding to "block"
489 ; blockRef
490 ;_______________________________________________________________________
491 */
492 static OSErr ReadBitmapBlock(
493 ExtendedVCB *vcb,
494 u_int32_t bit,
495 u_int32_t **buffer,
496 u_int32_t *blockRef)
497 {
498 OSErr err;
499 struct buf *bp = NULL;
500 struct vnode *vp = NULL;
501 daddr64_t block;
502 u_int32_t blockSize;
503
504 /*
505 * volume bitmap blocks are protected by the allocation file lock
506 */
507 REQUIRE_FILE_LOCK(vcb->hfs_allocation_vp, false);
508
509 blockSize = (u_int32_t)vcb->vcbVBMIOSize;
510 block = (daddr64_t)(bit / (blockSize * kBitsPerByte));
511
512 if (vcb->vcbSigWord == kHFSPlusSigWord) {
513 vp = vcb->hfs_allocation_vp; /* use allocation file vnode */
514
515 } else /* hfs */ {
516 vp = VCBTOHFS(vcb)->hfs_devvp; /* use device I/O vnode */
517 block += vcb->vcbVBMSt; /* map to physical block */
518 }
519
520 err = (int)buf_meta_bread(vp, block, blockSize, NOCRED, &bp);
521
522 if (bp) {
523 if (err) {
524 buf_brelse(bp);
525 *blockRef = 0;
526 *buffer = NULL;
527 } else {
528 *blockRef = (u_int32_t)bp;
529 *buffer = (u_int32_t *)buf_dataptr(bp);
530 }
531 }
532
533 return err;
534 }
535
536
537 /*
538 ;_______________________________________________________________________
539 ;
540 ; Routine: ReleaseBitmapBlock
541 ;
542 ; Function: Relase a bitmap block.
543 ;
544 ; Inputs:
545 ; vcb
546 ; blockRef
547 ; dirty
548 ;_______________________________________________________________________
549 */
550 static OSErr ReleaseBitmapBlock(
551 ExtendedVCB *vcb,
552 u_int32_t blockRef,
553 Boolean dirty)
554 {
555 struct buf *bp = (struct buf *)blockRef;
556
557 if (blockRef == 0) {
558 if (dirty)
559 panic("ReleaseBitmapBlock: missing bp");
560 return (0);
561 }
562
563 if (bp) {
564 if (dirty) {
565 // XXXdbg
566 struct hfsmount *hfsmp = VCBTOHFS(vcb);
567
568 if (hfsmp->jnl) {
569 journal_modify_block_end(hfsmp->jnl, bp, NULL, NULL);
570 } else {
571 buf_bdwrite(bp);
572 }
573 } else {
574 buf_brelse(bp);
575 }
576 }
577
578 return (0);
579 }
580
581
582 /*
583 _______________________________________________________________________
584
585 Routine: BlockAllocateContig
586
587 Function: Allocate a contiguous group of allocation blocks. The
588 allocation is all-or-nothing. The caller guarantees that
589 there are enough free blocks (though they may not be
590 contiguous, in which case this call will fail).
591
592 Inputs:
593 vcb Pointer to volume where space is to be allocated
594 startingBlock Preferred first block for allocation
595 minBlocks Minimum number of contiguous blocks to allocate
596 maxBlocks Maximum number of contiguous blocks to allocate
597 useMetaZone
598
599 Outputs:
600 actualStartBlock First block of range allocated, or 0 if error
601 actualNumBlocks Number of blocks allocated, or 0 if error
602 _______________________________________________________________________
603 */
604 static OSErr BlockAllocateContig(
605 ExtendedVCB *vcb,
606 u_int32_t startingBlock,
607 u_int32_t minBlocks,
608 u_int32_t maxBlocks,
609 Boolean useMetaZone,
610 u_int32_t *actualStartBlock,
611 u_int32_t *actualNumBlocks)
612 {
613 OSErr err;
614
615 //
616 // Find a contiguous group of blocks at least minBlocks long.
617 // Determine the number of contiguous blocks available (up
618 // to maxBlocks).
619 //
620
621 /*
622 * NOTE: If the only contiguous free extent of at least minBlocks
623 * crosses startingBlock (i.e. starts before, ends after), then we
624 * won't find it. Earlier versions *did* find this case by letting
625 * the second search look past startingBlock by minBlocks. But
626 * with the free extent cache, this can lead to duplicate entries
627 * in the cache, causing the same blocks to be allocated twice.
628 */
629 err = BlockFindContiguous(vcb, startingBlock, vcb->allocLimit, minBlocks,
630 maxBlocks, useMetaZone, actualStartBlock, actualNumBlocks);
631 if (err == dskFulErr && startingBlock != 0) {
632 /*
633 * Constrain the endingBlock so we don't bother looking for ranges
634 * that would overlap those found in the previous call.
635 */
636 err = BlockFindContiguous(vcb, 1, startingBlock, minBlocks, maxBlocks,
637 useMetaZone, actualStartBlock, actualNumBlocks);
638 }
639 //
640 // Now mark those blocks allocated.
641 //
642 if (err == noErr)
643 err = BlockMarkAllocated(vcb, *actualStartBlock, *actualNumBlocks);
644
645 return err;
646 }
647
648 /*
649 _______________________________________________________________________
650
651 Routine: BlockAllocateAny
652
653 Function: Allocate one or more allocation blocks. If there are fewer
654 free blocks than requested, all free blocks will be
655 allocated. The caller guarantees that there is at least
656 one free block.
657
658 Inputs:
659 vcb Pointer to volume where space is to be allocated
660 startingBlock Preferred first block for allocation
661 endingBlock Last block to check + 1
662 maxBlocks Maximum number of contiguous blocks to allocate
663 useMetaZone
664
665 Outputs:
666 actualStartBlock First block of range allocated, or 0 if error
667 actualNumBlocks Number of blocks allocated, or 0 if error
668 _______________________________________________________________________
669 */
670 static OSErr BlockAllocateAny(
671 ExtendedVCB *vcb,
672 u_int32_t startingBlock,
673 register u_int32_t endingBlock,
674 u_int32_t maxBlocks,
675 Boolean useMetaZone,
676 u_int32_t *actualStartBlock,
677 u_int32_t *actualNumBlocks)
678 {
679 OSErr err;
680 register u_int32_t block; // current block number
681 register u_int32_t currentWord; // Pointer to current word within bitmap block
682 register u_int32_t bitMask; // Word with given bits already set (ready to OR in)
683 register u_int32_t wordsLeft; // Number of words left in this bitmap block
684 u_int32_t *buffer = NULL;
685 u_int32_t *currCache = NULL;
686 u_int32_t blockRef;
687 u_int32_t bitsPerBlock;
688 u_int32_t wordsPerBlock;
689 Boolean dirty = false;
690 struct hfsmount *hfsmp = VCBTOHFS(vcb);
691
692 /*
693 * When we're skipping the metadata zone and the start/end
694 * range overlaps with the metadata zone then adjust the
695 * start to be outside of the metadata zone. If the range
696 * is entirely inside the metadata zone then we can deny the
697 * request (dskFulErr).
698 */
699 if (!useMetaZone && (vcb->hfs_flags & HFS_METADATA_ZONE)) {
700 if (startingBlock <= vcb->hfs_metazone_end) {
701 if (endingBlock > (vcb->hfs_metazone_end + 2))
702 startingBlock = vcb->hfs_metazone_end + 1;
703 else {
704 err = dskFulErr;
705 goto Exit;
706 }
707 }
708 }
709
710 // Since this routine doesn't wrap around
711 if (maxBlocks > (endingBlock - startingBlock)) {
712 maxBlocks = endingBlock - startingBlock;
713 }
714
715 //
716 // Pre-read the first bitmap block
717 //
718 err = ReadBitmapBlock(vcb, startingBlock, &currCache, &blockRef);
719 if (err != noErr) goto Exit;
720 buffer = currCache;
721
722 //
723 // Set up the current position within the block
724 //
725 {
726 u_int32_t wordIndexInBlock;
727
728 bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte;
729 wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
730
731 wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
732 buffer += wordIndexInBlock;
733 wordsLeft = wordsPerBlock - wordIndexInBlock;
734 currentWord = SWAP_BE32 (*buffer);
735 bitMask = kHighBitInWordMask >> (startingBlock & kBitsWithinWordMask);
736 }
737
738 //
739 // Find the first unallocated block
740 //
741 block=startingBlock;
742 while (block < endingBlock) {
743 if ((currentWord & bitMask) == 0)
744 break;
745
746 // Next bit
747 ++block;
748 bitMask >>= 1;
749 if (bitMask == 0) {
750 // Next word
751 bitMask = kHighBitInWordMask;
752 ++buffer;
753
754 if (--wordsLeft == 0) {
755 // Next block
756 buffer = currCache = NULL;
757 err = ReleaseBitmapBlock(vcb, blockRef, false);
758 if (err != noErr) goto Exit;
759
760 /*
761 * Skip over metadata blocks.
762 */
763 if (!useMetaZone) {
764 block = NextBitmapBlock(vcb, block);
765 }
766 if (block >= endingBlock) {
767 err = dskFulErr;
768 goto Exit;
769 }
770
771 err = ReadBitmapBlock(vcb, block, &currCache, &blockRef);
772 if (err != noErr) goto Exit;
773 buffer = currCache;
774
775 wordsLeft = wordsPerBlock;
776 }
777 currentWord = SWAP_BE32 (*buffer);
778 }
779 }
780
781 // Did we get to the end of the bitmap before finding a free block?
782 // If so, then couldn't allocate anything.
783 if (block >= endingBlock) {
784 err = dskFulErr;
785 goto Exit;
786 }
787
788 // Return the first block in the allocated range
789 *actualStartBlock = block;
790 dirty = true;
791
792 // If we could get the desired number of blocks before hitting endingBlock,
793 // then adjust endingBlock so we won't keep looking. Ideally, the comparison
794 // would be (block + maxBlocks) < endingBlock, but that could overflow. The
795 // comparison below yields identical results, but without overflow.
796 if (block < (endingBlock-maxBlocks)) {
797 endingBlock = block + maxBlocks; // if we get this far, we've found enough
798 }
799
800 // XXXdbg
801 if (hfsmp->jnl) {
802 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
803 }
804
805 //
806 // Allocate all of the consecutive blocks
807 //
808 while ((currentWord & bitMask) == 0) {
809 // Allocate this block
810 currentWord |= bitMask;
811
812 // Move to the next block. If no more, then exit.
813 ++block;
814 if (block == endingBlock)
815 break;
816
817 // Next bit
818 bitMask >>= 1;
819 if (bitMask == 0) {
820 *buffer = SWAP_BE32 (currentWord); // update value in bitmap
821
822 // Next word
823 bitMask = kHighBitInWordMask;
824 ++buffer;
825
826 if (--wordsLeft == 0) {
827 // Next block
828 buffer = currCache = NULL;
829 err = ReleaseBitmapBlock(vcb, blockRef, true);
830 if (err != noErr) goto Exit;
831
832 /*
833 * Skip over metadata blocks.
834 */
835 if (!useMetaZone) {
836 u_int32_t nextBlock;
837
838 nextBlock = NextBitmapBlock(vcb, block);
839 if (nextBlock != block) {
840 goto Exit; /* allocation gap, so stop */
841 }
842 }
843
844 err = ReadBitmapBlock(vcb, block, &currCache, &blockRef);
845 if (err != noErr) goto Exit;
846 buffer = currCache;
847
848 // XXXdbg
849 if (hfsmp->jnl) {
850 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
851 }
852
853 wordsLeft = wordsPerBlock;
854 }
855
856 currentWord = SWAP_BE32 (*buffer);
857 }
858 }
859 *buffer = SWAP_BE32 (currentWord); // update the last change
860
861 Exit:
862 if (err == noErr) {
863 *actualNumBlocks = block - *actualStartBlock;
864
865 // sanity check
866 if ((*actualStartBlock + *actualNumBlocks) > vcb->allocLimit)
867 panic("BlockAllocateAny: allocation overflow on \"%s\"", vcb->vcbVN);
868 }
869 else {
870 *actualStartBlock = 0;
871 *actualNumBlocks = 0;
872 }
873
874 if (currCache)
875 (void) ReleaseBitmapBlock(vcb, blockRef, dirty);
876
877 return err;
878 }
879
880
881 /*
882 _______________________________________________________________________
883
884 Routine: BlockAllocateKnown
885
886 Function: Try to allocate space from known free space in the free
887 extent cache.
888
889 Inputs:
890 vcb Pointer to volume where space is to be allocated
891 maxBlocks Maximum number of contiguous blocks to allocate
892
893 Outputs:
894 actualStartBlock First block of range allocated, or 0 if error
895 actualNumBlocks Number of blocks allocated, or 0 if error
896
897 Returns:
898 dskFulErr Free extent cache is empty
899 _______________________________________________________________________
900 */
901 static OSErr BlockAllocateKnown(
902 ExtendedVCB *vcb,
903 u_int32_t maxBlocks,
904 u_int32_t *actualStartBlock,
905 u_int32_t *actualNumBlocks)
906 {
907 OSErr err;
908 u_int32_t i;
909 u_int32_t foundBlocks;
910 u_int32_t newStartBlock, newBlockCount;
911
912 if (vcb->vcbFreeExtCnt == 0)
913 return dskFulErr;
914
915 // Just grab up to maxBlocks of the first (largest) free exent.
916 *actualStartBlock = vcb->vcbFreeExt[0].startBlock;
917 foundBlocks = vcb->vcbFreeExt[0].blockCount;
918 if (foundBlocks > maxBlocks)
919 foundBlocks = maxBlocks;
920 *actualNumBlocks = foundBlocks;
921
922 // Adjust the start and length of that extent.
923 newStartBlock = vcb->vcbFreeExt[0].startBlock + foundBlocks;
924 newBlockCount = vcb->vcbFreeExt[0].blockCount - foundBlocks;
925
926 // The first extent might not be the largest anymore. Bubble up any
927 // (now larger) extents to the top of the list.
928 for (i=1; i<vcb->vcbFreeExtCnt; ++i)
929 {
930 if (vcb->vcbFreeExt[i].blockCount > newBlockCount)
931 {
932 vcb->vcbFreeExt[i-1].startBlock = vcb->vcbFreeExt[i].startBlock;
933 vcb->vcbFreeExt[i-1].blockCount = vcb->vcbFreeExt[i].blockCount;
934 }
935 else
936 {
937 break;
938 }
939 }
940
941 // If this is now the smallest known free extent, then it might be smaller than
942 // other extents we didn't keep track of. So, just forget about this extent.
943 // After the previous loop, (i-1) is the index of the extent we just allocated from.
944 if (i == vcb->vcbFreeExtCnt)
945 {
946 // It's now the smallest extent, so forget about it
947 --vcb->vcbFreeExtCnt;
948 }
949 else
950 {
951 // It's not the smallest, so store it in its proper place
952 vcb->vcbFreeExt[i-1].startBlock = newStartBlock;
953 vcb->vcbFreeExt[i-1].blockCount = newBlockCount;
954 }
955
956 // sanity check
957 if ((*actualStartBlock + *actualNumBlocks) > vcb->allocLimit)
958 {
959 printf ("hfs: BlockAllocateKnown() found allocation overflow on \"%s\"", vcb->vcbVN);
960 hfs_mark_volume_inconsistent(vcb);
961 *actualStartBlock = 0;
962 *actualNumBlocks = 0;
963 err = EIO;
964 }
965 else
966 {
967 //
968 // Now mark the found extent in the bitmap
969 //
970 err = BlockMarkAllocated(vcb, *actualStartBlock, *actualNumBlocks);
971 }
972
973 return err;
974 }
975
976
977
978 /*
979 _______________________________________________________________________
980
981 Routine: BlockMarkAllocated
982
983 Function: Mark a contiguous group of blocks as allocated (set in the
984 bitmap). It assumes those bits are currently marked
985 deallocated (clear in the bitmap).
986
987 Inputs:
988 vcb Pointer to volume where space is to be allocated
989 startingBlock First block number to mark as allocated
990 numBlocks Number of blocks to mark as allocated
991 _______________________________________________________________________
992 */
993 __private_extern__
994 OSErr BlockMarkAllocated(
995 ExtendedVCB *vcb,
996 u_int32_t startingBlock,
997 register u_int32_t numBlocks)
998 {
999 OSErr err;
1000 register u_int32_t *currentWord; // Pointer to current word within bitmap block
1001 register u_int32_t wordsLeft; // Number of words left in this bitmap block
1002 register u_int32_t bitMask; // Word with given bits already set (ready to OR in)
1003 u_int32_t firstBit; // Bit index within word of first bit to allocate
1004 u_int32_t numBits; // Number of bits in word to allocate
1005 u_int32_t *buffer = NULL;
1006 u_int32_t blockRef;
1007 u_int32_t bitsPerBlock;
1008 u_int32_t wordsPerBlock;
1009 // XXXdbg
1010 struct hfsmount *hfsmp = VCBTOHFS(vcb);
1011
1012
1013 //
1014 // Pre-read the bitmap block containing the first word of allocation
1015 //
1016
1017 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1018 if (err != noErr) goto Exit;
1019 //
1020 // Initialize currentWord, and wordsLeft.
1021 //
1022 {
1023 u_int32_t wordIndexInBlock;
1024
1025 bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte;
1026 wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
1027
1028 wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
1029 currentWord = buffer + wordIndexInBlock;
1030 wordsLeft = wordsPerBlock - wordIndexInBlock;
1031 }
1032
1033 // XXXdbg
1034 if (hfsmp->jnl) {
1035 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
1036 }
1037
1038 //
1039 // If the first block to allocate doesn't start on a word
1040 // boundary in the bitmap, then treat that first word
1041 // specially.
1042 //
1043
1044 firstBit = startingBlock % kBitsPerWord;
1045 if (firstBit != 0) {
1046 bitMask = kAllBitsSetInWord >> firstBit; // turn off all bits before firstBit
1047 numBits = kBitsPerWord - firstBit; // number of remaining bits in this word
1048 if (numBits > numBlocks) {
1049 numBits = numBlocks; // entire allocation is inside this one word
1050 bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); // turn off bits after last
1051 }
1052 #if DEBUG_BUILD
1053 if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
1054 panic("BlockMarkAllocated: blocks already allocated!");
1055 }
1056 #endif
1057 *currentWord |= SWAP_BE32 (bitMask); // set the bits in the bitmap
1058 numBlocks -= numBits; // adjust number of blocks left to allocate
1059
1060 ++currentWord; // move to next word
1061 --wordsLeft; // one less word left in this block
1062 }
1063
1064 //
1065 // Allocate whole words (32 blocks) at a time.
1066 //
1067
1068 bitMask = kAllBitsSetInWord; // put this in a register for 68K
1069 while (numBlocks >= kBitsPerWord) {
1070 if (wordsLeft == 0) {
1071 // Read in the next bitmap block
1072 startingBlock += bitsPerBlock; // generate a block number in the next bitmap block
1073
1074 buffer = NULL;
1075 err = ReleaseBitmapBlock(vcb, blockRef, true);
1076 if (err != noErr) goto Exit;
1077
1078 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1079 if (err != noErr) goto Exit;
1080
1081 // XXXdbg
1082 if (hfsmp->jnl) {
1083 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
1084 }
1085
1086 // Readjust currentWord and wordsLeft
1087 currentWord = buffer;
1088 wordsLeft = wordsPerBlock;
1089 }
1090 #if DEBUG_BUILD
1091 if (*currentWord != 0) {
1092 panic("BlockMarkAllocated: blocks already allocated!");
1093 }
1094 #endif
1095 *currentWord = SWAP_BE32 (bitMask);
1096 numBlocks -= kBitsPerWord;
1097
1098 ++currentWord; // move to next word
1099 --wordsLeft; // one less word left in this block
1100 }
1101
1102 //
1103 // Allocate any remaining blocks.
1104 //
1105
1106 if (numBlocks != 0) {
1107 bitMask = ~(kAllBitsSetInWord >> numBlocks); // set first numBlocks bits
1108 if (wordsLeft == 0) {
1109 // Read in the next bitmap block
1110 startingBlock += bitsPerBlock; // generate a block number in the next bitmap block
1111
1112 buffer = NULL;
1113 err = ReleaseBitmapBlock(vcb, blockRef, true);
1114 if (err != noErr) goto Exit;
1115
1116 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1117 if (err != noErr) goto Exit;
1118
1119 // XXXdbg
1120 if (hfsmp->jnl) {
1121 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
1122 }
1123
1124 // Readjust currentWord and wordsLeft
1125 currentWord = buffer;
1126 wordsLeft = wordsPerBlock;
1127 }
1128 #if DEBUG_BUILD
1129 if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
1130 panic("BlockMarkAllocated: blocks already allocated!");
1131 }
1132 #endif
1133 *currentWord |= SWAP_BE32 (bitMask); // set the bits in the bitmap
1134
1135 // No need to update currentWord or wordsLeft
1136 }
1137
1138 Exit:
1139
1140 if (buffer)
1141 (void)ReleaseBitmapBlock(vcb, blockRef, true);
1142
1143 return err;
1144 }
1145
1146
1147 /*
1148 _______________________________________________________________________
1149
1150 Routine: BlockMarkFree
1151
1152 Function: Mark a contiguous group of blocks as free (clear in the
1153 bitmap). It assumes those bits are currently marked
1154 allocated (set in the bitmap).
1155
1156 Inputs:
1157 vcb Pointer to volume where space is to be freed
1158 startingBlock First block number to mark as freed
1159 numBlocks Number of blocks to mark as freed
1160 _______________________________________________________________________
1161 */
1162 __private_extern__
1163 OSErr BlockMarkFree(
1164 ExtendedVCB *vcb,
1165 u_int32_t startingBlock,
1166 register u_int32_t numBlocks)
1167 {
1168 OSErr err;
1169 register u_int32_t *currentWord; // Pointer to current word within bitmap block
1170 register u_int32_t wordsLeft; // Number of words left in this bitmap block
1171 register u_int32_t bitMask; // Word with given bits already set (ready to OR in)
1172 u_int32_t firstBit; // Bit index within word of first bit to allocate
1173 u_int32_t numBits; // Number of bits in word to allocate
1174 u_int32_t *buffer = NULL;
1175 u_int32_t blockRef;
1176 u_int32_t bitsPerBlock;
1177 u_int32_t wordsPerBlock;
1178 // XXXdbg
1179 struct hfsmount *hfsmp = VCBTOHFS(vcb);
1180
1181 /*
1182 * NOTE: We use vcb->totalBlocks instead of vcb->allocLimit because we
1183 * need to be able to free blocks being relocated during hfs_truncatefs.
1184 */
1185 if (startingBlock + numBlocks > vcb->totalBlocks) {
1186 printf ("hfs: BlockMarkFree() trying to free non-existent blocks starting at %u (numBlock=%u) on volume %s\n", startingBlock, numBlocks, vcb->vcbVN);
1187 hfs_mark_volume_inconsistent(vcb);
1188 err = EIO;
1189 goto Exit;
1190 }
1191
1192
1193 //
1194 // Pre-read the bitmap block containing the first word of allocation
1195 //
1196
1197 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1198 if (err != noErr) goto Exit;
1199 // XXXdbg
1200 if (hfsmp->jnl) {
1201 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
1202 }
1203
1204 //
1205 // Initialize currentWord, and wordsLeft.
1206 //
1207 {
1208 u_int32_t wordIndexInBlock;
1209
1210 bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte;
1211 wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
1212
1213 wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
1214 currentWord = buffer + wordIndexInBlock;
1215 wordsLeft = wordsPerBlock - wordIndexInBlock;
1216 }
1217
1218 //
1219 // If the first block to free doesn't start on a word
1220 // boundary in the bitmap, then treat that first word
1221 // specially.
1222 //
1223
1224 firstBit = startingBlock % kBitsPerWord;
1225 if (firstBit != 0) {
1226 bitMask = kAllBitsSetInWord >> firstBit; // turn off all bits before firstBit
1227 numBits = kBitsPerWord - firstBit; // number of remaining bits in this word
1228 if (numBits > numBlocks) {
1229 numBits = numBlocks; // entire allocation is inside this one word
1230 bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); // turn off bits after last
1231 }
1232 if ((*currentWord & SWAP_BE32 (bitMask)) != SWAP_BE32 (bitMask)) {
1233 goto Corruption;
1234 }
1235 *currentWord &= SWAP_BE32 (~bitMask); // clear the bits in the bitmap
1236 numBlocks -= numBits; // adjust number of blocks left to free
1237
1238 ++currentWord; // move to next word
1239 --wordsLeft; // one less word left in this block
1240 }
1241
1242 //
1243 // Free whole words (32 blocks) at a time.
1244 //
1245
1246 while (numBlocks >= kBitsPerWord) {
1247 if (wordsLeft == 0) {
1248 // Read in the next bitmap block
1249 startingBlock += bitsPerBlock; // generate a block number in the next bitmap block
1250
1251 buffer = NULL;
1252 err = ReleaseBitmapBlock(vcb, blockRef, true);
1253 if (err != noErr) goto Exit;
1254
1255 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1256 if (err != noErr) goto Exit;
1257
1258 // XXXdbg
1259 if (hfsmp->jnl) {
1260 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
1261 }
1262
1263 // Readjust currentWord and wordsLeft
1264 currentWord = buffer;
1265 wordsLeft = wordsPerBlock;
1266 }
1267 if (*currentWord != SWAP_BE32 (kAllBitsSetInWord)) {
1268 goto Corruption;
1269 }
1270 *currentWord = 0; // clear the entire word
1271 numBlocks -= kBitsPerWord;
1272
1273 ++currentWord; // move to next word
1274 --wordsLeft; // one less word left in this block
1275 }
1276
1277 //
1278 // Free any remaining blocks.
1279 //
1280
1281 if (numBlocks != 0) {
1282 bitMask = ~(kAllBitsSetInWord >> numBlocks); // set first numBlocks bits
1283 if (wordsLeft == 0) {
1284 // Read in the next bitmap block
1285 startingBlock += bitsPerBlock; // generate a block number in the next bitmap block
1286
1287 buffer = NULL;
1288 err = ReleaseBitmapBlock(vcb, blockRef, true);
1289 if (err != noErr) goto Exit;
1290
1291 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1292 if (err != noErr) goto Exit;
1293
1294 // XXXdbg
1295 if (hfsmp->jnl) {
1296 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
1297 }
1298
1299 // Readjust currentWord and wordsLeft
1300 currentWord = buffer;
1301 wordsLeft = wordsPerBlock;
1302 }
1303 if ((*currentWord & SWAP_BE32 (bitMask)) != SWAP_BE32 (bitMask)) {
1304 goto Corruption;
1305 }
1306 *currentWord &= SWAP_BE32 (~bitMask); // clear the bits in the bitmap
1307
1308 // No need to update currentWord or wordsLeft
1309 }
1310
1311 Exit:
1312
1313 if (buffer)
1314 (void)ReleaseBitmapBlock(vcb, blockRef, true);
1315
1316 return err;
1317
1318 Corruption:
1319 #if DEBUG_BUILD
1320 panic("BlockMarkFree: blocks not allocated!");
1321 #else
1322 printf ("hfs: BlockMarkFree() trying to free unallocated blocks on volume %s\n", vcb->vcbVN);
1323 hfs_mark_volume_inconsistent(vcb);
1324 err = EIO;
1325 goto Exit;
1326 #endif
1327 }
1328
1329
1330 /*
1331 _______________________________________________________________________
1332
1333 Routine: BlockFindContiguous
1334
1335 Function: Find a contiguous range of blocks that are free (bits
1336 clear in the bitmap). If a contiguous range of the
1337 minimum size can't be found, an error will be returned.
1338
1339 Inputs:
1340 vcb Pointer to volume where space is to be allocated
1341 startingBlock Preferred first block of range
1342 endingBlock Last possible block in range + 1
1343 minBlocks Minimum number of blocks needed. Must be > 0.
1344 maxBlocks Maximum (ideal) number of blocks desired
1345 useMetaZone OK to dip into metadata allocation zone
1346
1347 Outputs:
1348 actualStartBlock First block of range found, or 0 if error
1349 actualNumBlocks Number of blocks found, or 0 if error
1350
1351 Returns:
1352 noErr Found at least minBlocks contiguous
1353 dskFulErr No contiguous space found, or all less than minBlocks
1354 _______________________________________________________________________
1355 */
1356
1357 static OSErr BlockFindContiguous(
1358 ExtendedVCB *vcb,
1359 u_int32_t startingBlock,
1360 u_int32_t endingBlock,
1361 u_int32_t minBlocks,
1362 u_int32_t maxBlocks,
1363 Boolean useMetaZone,
1364 u_int32_t *actualStartBlock,
1365 u_int32_t *actualNumBlocks)
1366 {
1367 OSErr err;
1368 register u_int32_t currentBlock; // Block we're currently looking at.
1369 u_int32_t firstBlock; // First free block in current extent.
1370 u_int32_t stopBlock; // If we get to this block, stop searching for first free block.
1371 u_int32_t foundBlocks; // Number of contiguous free blocks in current extent.
1372 u_int32_t *buffer = NULL;
1373 register u_int32_t *currentWord;
1374 register u_int32_t bitMask;
1375 register u_int32_t wordsLeft;
1376 register u_int32_t tempWord;
1377 u_int32_t blockRef;
1378 u_int32_t wordsPerBlock;
1379
1380 /*
1381 * When we're skipping the metadata zone and the start/end
1382 * range overlaps with the metadata zone then adjust the
1383 * start to be outside of the metadata zone. If the range
1384 * is entirely inside the metadata zone then we can deny the
1385 * request (dskFulErr).
1386 */
1387 if (!useMetaZone && (vcb->hfs_flags & HFS_METADATA_ZONE)) {
1388 if (startingBlock <= vcb->hfs_metazone_end) {
1389 if (endingBlock > (vcb->hfs_metazone_end + 2))
1390 startingBlock = vcb->hfs_metazone_end + 1;
1391 else
1392 goto DiskFull;
1393 }
1394 }
1395
1396 if ((endingBlock - startingBlock) < minBlocks)
1397 {
1398 // The set of blocks we're checking is smaller than the minimum number
1399 // of blocks, so we couldn't possibly find a good range.
1400 goto DiskFull;
1401 }
1402
1403 stopBlock = endingBlock - minBlocks + 1;
1404 currentBlock = startingBlock;
1405 firstBlock = 0;
1406
1407 /*
1408 * Skip over metadata blocks.
1409 */
1410 if (!useMetaZone)
1411 currentBlock = NextBitmapBlock(vcb, currentBlock);
1412
1413 //
1414 // Pre-read the first bitmap block.
1415 //
1416 err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef);
1417 if ( err != noErr ) goto ErrorExit;
1418
1419 //
1420 // Figure out where currentBlock is within the buffer.
1421 //
1422 wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
1423
1424 wordsLeft = (currentBlock / kBitsPerWord) & (wordsPerBlock-1); // Current index into buffer
1425 currentWord = buffer + wordsLeft;
1426 wordsLeft = wordsPerBlock - wordsLeft;
1427
1428 do
1429 {
1430 foundBlocks = 0;
1431
1432 //============================================================
1433 // Look for a free block, skipping over allocated blocks.
1434 //============================================================
1435
1436 //
1437 // Check an initial partial word (if any)
1438 //
1439 bitMask = currentBlock & kBitsWithinWordMask;
1440 if (bitMask)
1441 {
1442 tempWord = SWAP_BE32(*currentWord); // Fetch the current word only once
1443 bitMask = kHighBitInWordMask >> bitMask;
1444 while (tempWord & bitMask)
1445 {
1446 bitMask >>= 1;
1447 ++currentBlock;
1448 }
1449
1450 // Did we find an unused bit (bitMask != 0), or run out of bits (bitMask == 0)?
1451 if (bitMask)
1452 goto FoundUnused;
1453
1454 // Didn't find any unused bits, so we're done with this word.
1455 ++currentWord;
1456 --wordsLeft;
1457 }
1458
1459 //
1460 // Check whole words
1461 //
1462 while (currentBlock < stopBlock)
1463 {
1464 // See if it's time to read another block.
1465 if (wordsLeft == 0)
1466 {
1467 buffer = NULL;
1468 err = ReleaseBitmapBlock(vcb, blockRef, false);
1469 if (err != noErr) goto ErrorExit;
1470
1471 /*
1472 * Skip over metadata blocks.
1473 */
1474 if (!useMetaZone) {
1475 currentBlock = NextBitmapBlock(vcb, currentBlock);
1476 if (currentBlock >= stopBlock) {
1477 goto LoopExit;
1478 }
1479 }
1480
1481 err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef);
1482 if ( err != noErr ) goto ErrorExit;
1483
1484 currentWord = buffer;
1485 wordsLeft = wordsPerBlock;
1486 }
1487
1488 // See if any of the bits are clear
1489 if ((tempWord = SWAP_BE32(*currentWord)) + 1) // non-zero if any bits were clear
1490 {
1491 // Figure out which bit is clear
1492 bitMask = kHighBitInWordMask;
1493 while (tempWord & bitMask)
1494 {
1495 bitMask >>= 1;
1496 ++currentBlock;
1497 }
1498
1499 break; // Found the free bit; break out to FoundUnused.
1500 }
1501
1502 // Keep looking at the next word
1503 currentBlock += kBitsPerWord;
1504 ++currentWord;
1505 --wordsLeft;
1506 }
1507
1508 FoundUnused:
1509 // Make sure the unused bit is early enough to use
1510 if (currentBlock >= stopBlock)
1511 {
1512 break;
1513 }
1514
1515 // Remember the start of the extent
1516 firstBlock = currentBlock;
1517
1518 //============================================================
1519 // Count the number of contiguous free blocks.
1520 //============================================================
1521
1522 //
1523 // Check an initial partial word (if any)
1524 //
1525 bitMask = currentBlock & kBitsWithinWordMask;
1526 if (bitMask)
1527 {
1528 tempWord = SWAP_BE32(*currentWord); // Fetch the current word only once
1529 bitMask = kHighBitInWordMask >> bitMask;
1530 while (bitMask && !(tempWord & bitMask))
1531 {
1532 bitMask >>= 1;
1533 ++currentBlock;
1534 }
1535
1536 // Did we find a used bit (bitMask != 0), or run out of bits (bitMask == 0)?
1537 if (bitMask)
1538 goto FoundUsed;
1539
1540 // Didn't find any used bits, so we're done with this word.
1541 ++currentWord;
1542 --wordsLeft;
1543 }
1544
1545 //
1546 // Check whole words
1547 //
1548 while (currentBlock < endingBlock)
1549 {
1550 // See if it's time to read another block.
1551 if (wordsLeft == 0)
1552 {
1553 buffer = NULL;
1554 err = ReleaseBitmapBlock(vcb, blockRef, false);
1555 if (err != noErr) goto ErrorExit;
1556
1557 /*
1558 * Skip over metadata blocks.
1559 */
1560 if (!useMetaZone) {
1561 u_int32_t nextBlock;
1562
1563 nextBlock = NextBitmapBlock(vcb, currentBlock);
1564 if (nextBlock != currentBlock) {
1565 goto LoopExit; /* allocation gap, so stop */
1566 }
1567 }
1568
1569 err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef);
1570 if ( err != noErr ) goto ErrorExit;
1571
1572 currentWord = buffer;
1573 wordsLeft = wordsPerBlock;
1574 }
1575
1576 // See if any of the bits are set
1577 if ((tempWord = SWAP_BE32(*currentWord)) != 0)
1578 {
1579 // Figure out which bit is set
1580 bitMask = kHighBitInWordMask;
1581 while (!(tempWord & bitMask))
1582 {
1583 bitMask >>= 1;
1584 ++currentBlock;
1585 }
1586
1587 break; // Found the used bit; break out to FoundUsed.
1588 }
1589
1590 // Keep looking at the next word
1591 currentBlock += kBitsPerWord;
1592 ++currentWord;
1593 --wordsLeft;
1594
1595 // If we found at least maxBlocks, we can quit early.
1596 if ((currentBlock - firstBlock) >= maxBlocks)
1597 break;
1598 }
1599
1600 FoundUsed:
1601 // Make sure we didn't run out of bitmap looking for a used block.
1602 // If so, pin to the end of the bitmap.
1603 if (currentBlock > endingBlock)
1604 currentBlock = endingBlock;
1605
1606 // Figure out how many contiguous free blocks there were.
1607 // Pin the answer to maxBlocks.
1608 foundBlocks = currentBlock - firstBlock;
1609 if (foundBlocks > maxBlocks)
1610 foundBlocks = maxBlocks;
1611 if (foundBlocks >= minBlocks)
1612 break; // Found what we needed!
1613
1614 // This free chunk wasn't big enough. Try inserting it into the free extent cache in case
1615 // the allocation wasn't forced contiguous.
1616 tempWord = vcb->vcbFreeExtCnt;
1617 if (tempWord == kMaxFreeExtents && vcb->vcbFreeExt[kMaxFreeExtents-1].blockCount < foundBlocks)
1618 --tempWord;
1619 if (tempWord < kMaxFreeExtents)
1620 {
1621 // We're going to add this extent. Bubble any smaller extents down in the list.
1622 while (tempWord && vcb->vcbFreeExt[tempWord-1].blockCount < foundBlocks)
1623 {
1624 vcb->vcbFreeExt[tempWord] = vcb->vcbFreeExt[tempWord-1];
1625 --tempWord;
1626 }
1627 vcb->vcbFreeExt[tempWord].startBlock = firstBlock;
1628 vcb->vcbFreeExt[tempWord].blockCount = foundBlocks;
1629
1630 if (vcb->vcbFreeExtCnt < kMaxFreeExtents)
1631 ++vcb->vcbFreeExtCnt;
1632 }
1633 } while (currentBlock < stopBlock);
1634 LoopExit:
1635
1636 // Return the outputs.
1637 if (foundBlocks < minBlocks)
1638 {
1639 DiskFull:
1640 err = dskFulErr;
1641 ErrorExit:
1642 *actualStartBlock = 0;
1643 *actualNumBlocks = 0;
1644 }
1645 else
1646 {
1647 err = noErr;
1648 *actualStartBlock = firstBlock;
1649 *actualNumBlocks = foundBlocks;
1650 /*
1651 * Sanity check for overflow
1652 */
1653 if ((firstBlock + foundBlocks) > vcb->allocLimit) {
1654 panic("blk allocation overflow on \"%s\" sb:0x%08x eb:0x%08x cb:0x%08x fb:0x%08x stop:0x%08x min:0x%08x found:0x%08x",
1655 vcb->vcbVN, startingBlock, endingBlock, currentBlock,
1656 firstBlock, stopBlock, minBlocks, foundBlocks);
1657 }
1658 }
1659
1660 if (buffer)
1661 (void) ReleaseBitmapBlock(vcb, blockRef, false);
1662
1663 return err;
1664 }
1665
1666 /*
1667 * Test to see if any blocks in a range are allocated.
1668 *
1669 * The journal or allocation file lock must be held.
1670 */
1671 __private_extern__
1672 int
1673 hfs_isallocated(struct hfsmount *hfsmp, u_long startingBlock, u_long numBlocks)
1674 {
1675 u_int32_t *currentWord; // Pointer to current word within bitmap block
1676 u_int32_t wordsLeft; // Number of words left in this bitmap block
1677 u_int32_t bitMask; // Word with given bits already set (ready to test)
1678 u_int32_t firstBit; // Bit index within word of first bit to allocate
1679 u_int32_t numBits; // Number of bits in word to allocate
1680 u_int32_t *buffer = NULL;
1681 u_int32_t blockRef;
1682 u_int32_t bitsPerBlock;
1683 u_int32_t wordsPerBlock;
1684 int inuse = 0;
1685 int error;
1686
1687 /*
1688 * Pre-read the bitmap block containing the first word of allocation
1689 */
1690 error = ReadBitmapBlock(hfsmp, startingBlock, &buffer, &blockRef);
1691 if (error)
1692 return (error);
1693
1694 /*
1695 * Initialize currentWord, and wordsLeft.
1696 */
1697 {
1698 u_int32_t wordIndexInBlock;
1699
1700 bitsPerBlock = hfsmp->vcbVBMIOSize * kBitsPerByte;
1701 wordsPerBlock = hfsmp->vcbVBMIOSize / kBytesPerWord;
1702
1703 wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
1704 currentWord = buffer + wordIndexInBlock;
1705 wordsLeft = wordsPerBlock - wordIndexInBlock;
1706 }
1707
1708 /*
1709 * First test any non word aligned bits.
1710 */
1711 firstBit = startingBlock % kBitsPerWord;
1712 if (firstBit != 0) {
1713 bitMask = kAllBitsSetInWord >> firstBit;
1714 numBits = kBitsPerWord - firstBit;
1715 if (numBits > numBlocks) {
1716 numBits = numBlocks;
1717 bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits));
1718 }
1719 if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
1720 inuse = 1;
1721 goto Exit;
1722 }
1723 numBlocks -= numBits;
1724 ++currentWord;
1725 --wordsLeft;
1726 }
1727
1728 /*
1729 * Test whole words (32 blocks) at a time.
1730 */
1731 while (numBlocks >= kBitsPerWord) {
1732 if (wordsLeft == 0) {
1733 /* Read in the next bitmap block. */
1734 startingBlock += bitsPerBlock;
1735
1736 buffer = NULL;
1737 error = ReleaseBitmapBlock(hfsmp, blockRef, false);
1738 if (error) goto Exit;
1739
1740 error = ReadBitmapBlock(hfsmp, startingBlock, &buffer, &blockRef);
1741 if (error) goto Exit;
1742
1743 /* Readjust currentWord and wordsLeft. */
1744 currentWord = buffer;
1745 wordsLeft = wordsPerBlock;
1746 }
1747 if (*currentWord != 0) {
1748 inuse = 1;
1749 goto Exit;
1750 }
1751 numBlocks -= kBitsPerWord;
1752 ++currentWord;
1753 --wordsLeft;
1754 }
1755
1756 /*
1757 * Test any remaining blocks.
1758 */
1759 if (numBlocks != 0) {
1760 bitMask = ~(kAllBitsSetInWord >> numBlocks);
1761 if (wordsLeft == 0) {
1762 /* Read in the next bitmap block */
1763 startingBlock += bitsPerBlock;
1764
1765 buffer = NULL;
1766 error = ReleaseBitmapBlock(hfsmp, blockRef, false);
1767 if (error) goto Exit;
1768
1769 error = ReadBitmapBlock(hfsmp, startingBlock, &buffer, &blockRef);
1770 if (error) goto Exit;
1771
1772 currentWord = buffer;
1773 wordsLeft = wordsPerBlock;
1774 }
1775 if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
1776 inuse = 1;
1777 goto Exit;
1778 }
1779 }
1780 Exit:
1781 if (buffer) {
1782 (void)ReleaseBitmapBlock(hfsmp, blockRef, false);
1783 }
1784 return (inuse);
1785 }
1786
1787
mirror of XNU