| | 1 | /* |
| | 2 | * Copyright (c) 2000-2014 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 | |
| | 30 | #include "../../hfs.h" |
| | 31 | #include "../../hfs_format.h" |
| | 32 | #include "../../hfs_endian.h" |
| | 33 | |
| | 34 | #include "../headers/FileMgrInternal.h" |
| | 35 | #include "../headers/BTreesInternal.h" |
| | 36 | |
| | 37 | #include <sys/malloc.h> |
| | 38 | #include <sys/vnode_internal.h> |
| | 39 | |
| | 40 | /* |
| | 41 | ============================================================ |
| | 42 | Public (Exported) Routines: |
| | 43 | ============================================================ |
| | 44 | |
| | 45 | ExtendFileC Allocate more space to a given file. |
| | 46 | |
| | 47 | CompareExtentKeys |
| | 48 | Compare two extents file keys (a search key and a trial |
| | 49 | key). Used by the BTree manager when searching for, |
| | 50 | adding, or deleting keys in the extents file of an HFS |
| | 51 | volume. |
| | 52 | |
| | 53 | CompareExtentKeysPlus |
| | 54 | Compare two extents file keys (a search key and a trial |
| | 55 | key). Used by the BTree manager when searching for, |
| | 56 | adding, or deleting keys in the extents file of an HFS+ |
| | 57 | volume. |
| | 58 | |
| | 59 | MapFileBlockC Convert (map) an offset within a given file into a |
| | 60 | physical disk address. |
| | 61 | |
| | 62 | TruncateFileC Truncates the disk space allocated to a file. The file |
| | 63 | space is truncated to a specified new physical EOF, rounded |
| | 64 | up to the next allocation block boundry. There is an option |
| | 65 | to truncate to the end of the extent containing the new EOF. |
| | 66 | |
| | 67 | FlushExtentFile |
| | 68 | Flush the extents file for a given volume. |
| | 69 | |
| | 70 | SearchExtentFile |
| | 71 | Search the FCB and extents file for an extent record that |
| | 72 | contains a given file position (in bytes). |
| | 73 | |
| | 74 | |
| | 75 | ============================================================ |
| | 76 | Internal Routines: |
| | 77 | ============================================================ |
| | 78 | FindExtentRecord |
| | 79 | Search the extents BTree for a particular extent record. |
| | 80 | SearchExtentRecord |
| | 81 | Search a given extent record to see if it contains a given |
| | 82 | file position (in bytes). Used by SearchExtentFile. |
| | 83 | ReleaseExtents |
| | 84 | Deallocate all allocation blocks in all extents of an extent |
| | 85 | data record. |
| | 86 | TruncateExtents |
| | 87 | Deallocate blocks and delete extent records for all allocation |
| | 88 | blocks beyond a certain point in a file. The starting point |
| | 89 | must be the first file allocation block for some extent record |
| | 90 | for the file. |
| | 91 | DeallocateFork |
| | 92 | Deallocate all allocation blocks belonging to a given fork. |
| | 93 | UpdateExtentRecord |
| | 94 | If the extent record came from the extents file, write out |
| | 95 | the updated record; otherwise, copy the updated record into |
| | 96 | the FCB resident extent record. If the record has no extents, |
| | 97 | and was in the extents file, then delete the record instead. |
| | 98 | */ |
| | 99 | |
| | 100 | #if CONFIG_HFS_STD |
| | 101 | static const int64_t kTwoGigabytes = 0x80000000LL; |
| | 102 | #endif |
| | 103 | |
| | 104 | enum |
| | 105 | { |
| | 106 | kDataForkType = 0, |
| | 107 | kResourceForkType = 0xFF, |
| | 108 | |
| | 109 | kPreviousRecord = -1 |
| | 110 | }; |
| | 111 | |
| | 112 | |
| | 113 | #if CONFIG_HFS_STD |
| | 114 | static OSErr HFSPlusToHFSExtents( |
| | 115 | const HFSPlusExtentRecord oldExtents, |
| | 116 | HFSExtentRecord newExtents); |
| | 117 | #endif |
| | 118 | |
| | 119 | static OSErr FindExtentRecord( |
| | 120 | const ExtendedVCB *vcb, |
| | 121 | u_int8_t forkType, |
| | 122 | u_int32_t fileID, |
| | 123 | u_int32_t startBlock, |
| | 124 | Boolean allowPrevious, |
| | 125 | HFSPlusExtentKey *foundKey, |
| | 126 | HFSPlusExtentRecord foundData, |
| | 127 | u_int32_t *foundHint); |
| | 128 | |
| | 129 | static OSErr DeleteExtentRecord( |
| | 130 | const ExtendedVCB *vcb, |
| | 131 | u_int8_t forkType, |
| | 132 | u_int32_t fileID, |
| | 133 | u_int32_t startBlock); |
| | 134 | |
| | 135 | static OSErr CreateExtentRecord( |
| | 136 | ExtendedVCB *vcb, |
| | 137 | HFSPlusExtentKey *key, |
| | 138 | HFSPlusExtentRecord extents, |
| | 139 | u_int32_t *hint); |
| | 140 | |
| | 141 | |
| | 142 | static OSErr GetFCBExtentRecord( |
| | 143 | const FCB *fcb, |
| | 144 | HFSPlusExtentRecord extents); |
| | 145 | |
| | 146 | static OSErr SearchExtentRecord( |
| | 147 | ExtendedVCB *vcb, |
| | 148 | u_int32_t searchFABN, |
| | 149 | const HFSPlusExtentRecord extentData, |
| | 150 | u_int32_t extentDataStartFABN, |
| | 151 | u_int32_t *foundExtentDataOffset, |
| | 152 | u_int32_t *endingFABNPlusOne, |
| | 153 | Boolean *noMoreExtents); |
| | 154 | |
| | 155 | static OSErr ReleaseExtents( |
| | 156 | ExtendedVCB *vcb, |
| | 157 | const HFSPlusExtentRecord extentRecord, |
| | 158 | u_int32_t *numReleasedAllocationBlocks, |
| | 159 | Boolean *releasedLastExtent); |
| | 160 | |
| | 161 | static OSErr DeallocateFork( |
| | 162 | ExtendedVCB *vcb, |
| | 163 | HFSCatalogNodeID fileID, |
| | 164 | u_int8_t forkType, |
| | 165 | HFSPlusExtentRecord catalogExtents, |
| | 166 | Boolean * recordDeleted); |
| | 167 | |
| | 168 | static OSErr TruncateExtents( |
| | 169 | ExtendedVCB *vcb, |
| | 170 | u_int8_t forkType, |
| | 171 | u_int32_t fileID, |
| | 172 | u_int32_t startBlock, |
| | 173 | Boolean * recordDeleted); |
| | 174 | |
| | 175 | static OSErr UpdateExtentRecord ( |
| | 176 | ExtendedVCB *vcb, |
| | 177 | FCB *fcb, |
| | 178 | int deleted, |
| | 179 | const HFSPlusExtentKey *extentFileKey, |
| | 180 | const HFSPlusExtentRecord extentData, |
| | 181 | u_int32_t extentBTreeHint); |
| | 182 | |
| | 183 | static Boolean ExtentsAreIntegral( |
| | 184 | const HFSPlusExtentRecord extentRecord, |
| | 185 | u_int32_t mask, |
| | 186 | u_int32_t *blocksChecked, |
| | 187 | Boolean *checkedLastExtent); |
| | 188 | |
| | 189 | //_________________________________________________________________________________ |
| | 190 | // |
| | 191 | // Routine: FindExtentRecord |
| | 192 | // |
| | 193 | // Purpose: Search the extents BTree for an extent record matching the given |
| | 194 | // FileID, fork, and starting file allocation block number. |
| | 195 | // |
| | 196 | // Inputs: |
| | 197 | // vcb Volume to search |
| | 198 | // forkType 0 = data fork, -1 = resource fork |
| | 199 | // fileID File's FileID (CatalogNodeID) |
| | 200 | // startBlock Starting file allocation block number |
| | 201 | // allowPrevious If the desired record isn't found and this flag is set, |
| | 202 | // then see if the previous record belongs to the same fork. |
| | 203 | // If so, then return it. |
| | 204 | // |
| | 205 | // Outputs: |
| | 206 | // foundKey The key data for the record actually found |
| | 207 | // foundData The extent record actually found (NOTE: on an HFS volume, the |
| | 208 | // fourth entry will be zeroes. |
| | 209 | // foundHint The BTree hint to find the node again |
| | 210 | //_________________________________________________________________________________ |
| | 211 | static OSErr FindExtentRecord( |
| | 212 | const ExtendedVCB *vcb, |
| | 213 | u_int8_t forkType, |
| | 214 | u_int32_t fileID, |
| | 215 | u_int32_t startBlock, |
| | 216 | Boolean allowPrevious, |
| | 217 | HFSPlusExtentKey *foundKey, |
| | 218 | HFSPlusExtentRecord foundData, |
| | 219 | u_int32_t *foundHint) |
| | 220 | { |
| | 221 | FCB * fcb; |
| | 222 | struct BTreeIterator *btIterator = NULL; |
| | 223 | FSBufferDescriptor btRecord; |
| | 224 | OSErr err; |
| | 225 | u_int16_t btRecordSize; |
| | 226 | |
| | 227 | err = noErr; |
| | 228 | if (foundHint) |
| | 229 | *foundHint = 0; |
| | 230 | fcb = GetFileControlBlock(vcb->extentsRefNum); |
| | 231 | |
| | 232 | MALLOC (btIterator, struct BTreeIterator*, sizeof(struct BTreeIterator), M_TEMP, M_WAITOK); |
| | 233 | if (btIterator == NULL) { |
| | 234 | return memFullErr; // translates to ENOMEM |
| | 235 | } |
| | 236 | bzero(btIterator, sizeof(*btIterator)); |
| | 237 | |
| | 238 | /* HFS Plus / HFSX */ |
| | 239 | if (vcb->vcbSigWord != kHFSSigWord) { |
| | 240 | HFSPlusExtentKey * extentKeyPtr; |
| | 241 | HFSPlusExtentRecord extentData; |
| | 242 | |
| | 243 | extentKeyPtr = (HFSPlusExtentKey*) &btIterator->key; |
| | 244 | extentKeyPtr->keyLength = kHFSPlusExtentKeyMaximumLength; |
| | 245 | extentKeyPtr->forkType = forkType; |
| | 246 | extentKeyPtr->pad = 0; |
| | 247 | extentKeyPtr->fileID = fileID; |
| | 248 | extentKeyPtr->startBlock = startBlock; |
| | 249 | |
| | 250 | btRecord.bufferAddress = &extentData; |
| | 251 | btRecord.itemSize = sizeof(HFSPlusExtentRecord); |
| | 252 | btRecord.itemCount = 1; |
| | 253 | |
| | 254 | err = BTSearchRecord(fcb, btIterator, &btRecord, &btRecordSize, btIterator); |
| | 255 | |
| | 256 | if (err == btNotFound && allowPrevious) { |
| | 257 | err = BTIterateRecord(fcb, kBTreePrevRecord, btIterator, &btRecord, &btRecordSize); |
| | 258 | |
| | 259 | // A previous record may not exist, so just return btNotFound (like we would if |
| | 260 | // it was for the wrong file/fork). |
| | 261 |
projects / apple / xnu.git / blame_incremental