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