]> git.saurik.com Git - apple/hfs.git/blob - core/BTreeMiscOps.c
projects / apple / hfs.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
hfs-407.30.1.tar.gz
[apple/hfs.git] / core / BTreeMiscOps.c
1 /*
2 * Copyright (c) 2000-2003, 2005-2015 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: BTreeMiscOps.c
30
31 Contains: Miscellaneous operations for the BTree Module.
32
33 Version: xxx put the technology version here xxx
34
35 Written by: Gordon Sheridan and Bill Bruffey
36
37 Copyright: (c) 1992-1999 by Apple Inc., all rights reserved.
38
39 File Ownership:
40
41 DRI: Don Brady
42
43 Other Contact: Mark Day
44
45 Technology: File Systems
46
47 Writers:
48
49 (DSH) Deric Horn
50 (msd) Mark Day
51 (djb) Don Brady
52
53 Change History (most recent first):
54
55 <MOSXS> 6/1/99 djb Sync up with Mac OS 8.6.
56 <CS2> 9/4/97 djb Optimize TrySimpleReplace for the case where record size is not
57 changing.
58 <CS1> 4/23/97 djb first checked in
59
60 <HFS7> 3/31/97 djb Move ClearMemory to Utilities.c.
61 <HFS6> 3/17/97 DSH Casting for DFA
62 <HFS5> 2/27/97 msd Remove temporary fix from last revision. BTree EOF's should be
63 correct now, so check for strict equality.
64 <HFS4> 2/26/97 msd Fix a casting problem in ClearMemory. TEMPORARY FIX: Made
65 VerifyHeader more lenient, allowing the EOF to be greater than
66 the amount actually used by nodes; this should really be fixed
67 in the formatting code (which needs to compute the real BTree
68 sizes before writing the volume header).
69 <HFS3> 2/19/97 djb Added ClearMemory. Changed CalcKeyLength to KeyLength.
70 <HFS2> 1/3/97 djb Added support for large keys.
71 <HFS1> 12/19/96 djb first checked in
72
73 History applicable to original Scarecrow Design:
74
75 <9> 10/25/96 ser Changing for new VFPI
76 <8> 10/18/96 ser Converting over VFPI changes
77 <7> 9/17/96 dkh More BTree statistics. Change IsItAHint to not always check to
78 see if the hint node is allocated.
79 <6> 9/16/96 dkh Revised BTree statistics.
80 <5> 6/20/96 dkh Radar #1358740. Change from using Pools to debug MemAllocators.
81 <4> 1/22/96 dkh Change Pools.i inclusion to PoolsPriv.i
82 <3> 1/10/96 msd Change 64-bit math to use real function names from Math64.i.
83 <2> 12/7/95 dkh D10E2 build. Changed usage of Ref data type to LogicalAddress.
84 <1> 10/18/95 rst Moved from Scarecrow project.
85
86 <19> 4/26/95 prp In UpdateHeader, clear the dirty flag after the BTree is updated.
87 <18> 1/12/95 wjk Adopt Model FileSystem changes in D5.
88 <17> 11/16/94 prp Add IsItAHint routine and use it whenever hint's node number was
89 used for testing.
90 <16> 10/5/94 bk add pools.h include file
91 <15> 9/30/94 prp Get in sync with D2 interface changes.
92 <14> 7/22/94 wjk Convert to the new set of header files.
93 <13> 12/2/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and
94 NRCmds environments.
95 <12> 11/30/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and
96 NRCmds environments.
97 <11> 11/23/93 wjk Changes required to compile on the RS6000.
98 <10> 8/31/93 prp Use U64SetU instead of S64Set.
99 <9> 6/2/93 gs Update for changes to FSErrors.h and add some comments.
100 <8> 5/21/93 gs Modify UpdateHeader to write out attributes. Remove
101 Get/UpdateNode from TrySimpleReplace.
102 <7> 5/10/93 gs Add TrySimpleReplace routine.
103 <6> 3/23/93 gs Change MoveData to take void * instead of Ptr. Add UpdateHeader
104 and ClearBytes routines.
105 <5> 2/8/93 gs Add FindIteratorPosition.
106 <4> 12/10/92 gs Implement CheckKeyDescriptor and the KeyDescriptor interpreter.
107 <3> 12/8/92 gs Add GetKeyDescriptor, VerifyHeader, and Alloc/Dealloc memory
108 routines.
109 <2> 12/2/92 gs Add CompareKeys routine.
110 <1> 11/15/92 gs first checked in
111
112 */
113
114 #include "BTreesPrivate.h"
115 #include "hfs_btreeio.h"
116
117
118 ////////////////////////////// Routine Definitions //////////////////////////////
119
120 /*-------------------------------------------------------------------------------
121 Routine: CalcKeyRecordSize - Return size of combined key/record structure.
122
123 Function: Rounds keySize and recSize so they will end on word boundaries.
124 Does NOT add size of offset.
125
126 Input: keySize - length of key (including length field)
127 recSize - length of record data
128
129 Output: none
130
131 Result: u_int16_t - size of combined key/record that will be inserted in btree
132 -------------------------------------------------------------------------------*/
133
134 u_int16_t CalcKeyRecordSize (u_int16_t keySize,
135 u_int16_t recSize )
136 {
137 if ( M_IsOdd (keySize) ) keySize += 1; // pad byte
138
139 if (M_IsOdd (recSize) ) recSize += 1; // pad byte
140
141 return (keySize + recSize);
142 }
143
144
145
146 /*-------------------------------------------------------------------------------
147 Routine: VerifyHeader - Validate fields of the BTree header record.
148
149 Function: Examines the fields of the BTree header record to determine if the
150 fork appears to contain a valid BTree.
151
152 Input: forkPtr - pointer to fork control block
153 header - pointer to BTree header
154
155
156 Result: noErr - success
157 != noErr - failure
158 -------------------------------------------------------------------------------*/
159
160 OSStatus VerifyHeader (FCB *filePtr,
161 BTHeaderRec *header )
162 {
163 u_int64_t forkSize;
164 u_int32_t totalNodes;
165
166
167 switch (header->nodeSize) // node size == 512*2^n
168 {
169 case 512:
170 case 1024:
171 case 2048:
172 case 4096:
173 case 8192:
174 case 16384:
175 case 32768: break;
176 default: return fsBTInvalidHeaderErr; //\80\80 E_BadNodeType
177 }
178
179 totalNodes = header->totalNodes;
180
181 forkSize = (u_int64_t)totalNodes * (u_int64_t)header->nodeSize;
182
183 if ( forkSize > (u_int64_t)filePtr->fcbEOF )
184 return fsBTInvalidHeaderErr;
185
186 if ( header->freeNodes >= totalNodes )
187 return fsBTInvalidHeaderErr;
188
189 if ( header->rootNode >= totalNodes )
190 return fsBTInvalidHeaderErr;
191
192 if ( header->firstLeafNode >= totalNodes )
193 return fsBTInvalidHeaderErr;
194
195 if ( header->lastLeafNode >= totalNodes )
196 return fsBTInvalidHeaderErr;
197
198 if ( header->treeDepth > kMaxTreeDepth )
199 return fsBTInvalidHeaderErr;
200
201
202 /////////////////////////// Check BTree Type ////////////////////////////////
203
204 switch (header->btreeType)
205 {
206 case 0: // HFS Type - no Key Descriptor
207 case kUserBTreeType: // with Key Descriptors etc.
208 case kReservedBTreeType: // Desktop Mgr BTree ?
209 break;
210
211 default: return fsBTUnknownVersionErr;
212 }
213
214 return noErr;
215 }
216
217
218
219 OSStatus TreeIsDirty(BTreeControlBlockPtr btreePtr)
220 {
221 return (btreePtr->flags & kBTHeaderDirty);
222 }
223
224
225
226 /*-------------------------------------------------------------------------------
227 Routine: UpdateHeader - Write BTreeInfoRec fields to Header node.
228
229 Function: Checks the kBTHeaderDirty flag in the BTreeInfoRec and updates the
230 header node if necessary.
231
232 Input: btreePtr - pointer to BTreeInfoRec
233
234
235 Result: noErr - success
236 != noErr - failure
237 -------------------------------------------------------------------------------*/
238
239 OSStatus UpdateHeader(BTreeControlBlockPtr btreePtr, Boolean forceWrite)
240 {
241 OSStatus err;
242 BlockDescriptor node;
243 BTHeaderRec *header;
244 u_int32_t options;
245
246 if ((btreePtr->flags & kBTHeaderDirty) == 0) // btree info already flushed
247 return noErr;
248
249 err = GetNode (btreePtr, kHeaderNodeNum, 0, &node );
250 if (err != noErr) {
251 return err;
252 }
253
254 // XXXdbg
255 ModifyBlockStart(btreePtr->fileRefNum, &node);
256
257 header = (BTHeaderRec*) ((char *)node.buffer + sizeof(BTNodeDescriptor));
258
259 header->treeDepth = btreePtr->treeDepth;
260 header->rootNode = btreePtr->rootNode;
261 header->leafRecords = btreePtr->leafRecords;
262 header->firstLeafNode = btreePtr->firstLeafNode;
263 header->lastLeafNode = btreePtr->lastLeafNode;
264 header->nodeSize = btreePtr->nodeSize; //\80\80 this shouldn't change
265 header->maxKeyLength = btreePtr->maxKeyLength; //\80\80 neither should this
266 header->totalNodes = btreePtr->totalNodes;
267 header->freeNodes = btreePtr->freeNodes;
268 header->btreeType = btreePtr->btreeType;
269
270 // ignore header->clumpSize; //\80\80 rename this field?
271
272 if (forceWrite)
273 options = kForceWriteBlock;
274 else
275 options = kLockTransaction;
276
277 err = UpdateNode (btreePtr, &node, 0, options);
278
279 btreePtr->flags &= (~kBTHeaderDirty);
280
281 return err;
282 }
283
284
285
286 /*-------------------------------------------------------------------------------
287 Routine: FindIteratorPosition - One_line_description.
288
289 Function: Brief_description_of_the_function_and_any_side_effects
290
291 Algorithm: see FSC.BT.BTIterateRecord.PICT
292
293 Note: //\80\80 document side-effects of bad node hints
294
295 Input: btreePtr - description
296 iterator - description
297
298
299 Output: iterator - description
300 left - description
301 middle - description
302 right - description
303 nodeNum - description
304 returnIndex - description
305 foundRecord - description
306
307
308 Result: noErr - success
309 != noErr - failure
310 -------------------------------------------------------------------------------*/
311
312 OSStatus FindIteratorPosition (BTreeControlBlockPtr btreePtr,
313 BTreeIteratorPtr iterator,
314 BlockDescriptor *left,
315 BlockDescriptor *middle,
316 BlockDescriptor *right,
317 u_int32_t *returnNodeNum,
318 u_int16_t *returnIndex,
319 Boolean *foundRecord )
320 {
321 OSStatus err;
322 Boolean foundIt;
323 u_int32_t nodeNum;
324 u_int16_t leftIndex, index, rightIndex;
325 Boolean validHint;
326
327 // assume btreePtr valid
328 // assume left, middle, right point to BlockDescriptors
329 // assume nodeNum points to u_int32_t
330 // assume index points to u_int16_t
331 // assume foundRecord points to Boolean
332
333 left->buffer = nil;
334 left->blockHeader = nil;
335 middle->buffer = nil;
336 middle->blockHeader = nil;
337 right->buffer = nil;
338 right->blockHeader = nil;
339
340 foundIt = false;
341
342 if (iterator == nil) // do we have an iterator?
343 {
344 err = fsBTInvalidIteratorErr;
345 goto ErrorExit;
346 }
347
348 err = IsItAHint (btreePtr, iterator, &validHint);
349 M_ExitOnError (err);
350
351 nodeNum = iterator->hint.nodeNum;
352 if (! validHint) // does the hint appear to be valid?
353 {
354 goto SearchTheTree;
355 }
356
357 err = GetNode (btreePtr, nodeNum, kGetNodeHint, middle);
358 if( err == fsBTInvalidNodeErr ) // returned if nodeNum is out of range
359 goto SearchTheTree;
360
361 M_ExitOnError (err);
362
363 if ( ((NodeDescPtr) middle->buffer)->kind != kBTLeafNode ||
364 ((NodeDescPtr) middle->buffer)->numRecords <= 0 )
365 {
366 goto SearchTheTree;
367 }
368
369 foundIt = SearchNode (btreePtr, middle->buffer, &iterator->key, &index);
370 if (foundIt == true)
371 {
372 ++btreePtr->numValidHints;
373 goto SuccessfulExit;
374 }
375 iterator->hint.nodeNum = 0;
376
377 if (index == 0)
378 {
379 if (((NodeDescPtr) middle->buffer)->bLink == 0) // before 1st btree record
380 {
381 goto SuccessfulExit;
382 }
383
384 nodeNum = ((NodeDescPtr) middle->buffer)->bLink;
385
386 // BTree nodes are always grabbed in left to right order.
387 // Therefore release the current node before looking up the
388 // left node.
389 err = ReleaseNode(btreePtr, middle);
390 M_ExitOnError(err);
391
392 // Look up the left node
393 err = GetNode (btreePtr, nodeNum, 0, left);
394 M_ExitOnError (err);
395
396 // Look up the current node again
397 err = GetRightSiblingNode (btreePtr, left->buffer, middle);
398 M_ExitOnError (err);
399
400 if ( ((NodeDescPtr) left->buffer)->kind != kBTLeafNode ||
401 ((NodeDescPtr) left->buffer)->numRecords <= 0 )
402 {
403 goto SearchTheTree;
404 }
405
406 foundIt = SearchNode (btreePtr, left->buffer, &iterator->key, &leftIndex);
407 if (foundIt == true)
408 {
409 *right = *middle;
410 *middle = *left;
411 left->buffer = nil;
412 index = leftIndex;
413
414 goto SuccessfulExit;
415 }
416
417 if (leftIndex == 0) // we're lost!
418 {
419 goto SearchTheTree;
420 }
421 else if (leftIndex >= ((NodeDescPtr) left->buffer)->numRecords)
422 {
423 nodeNum = ((NodeDescPtr) left->buffer)->fLink;
424
425 PanicIf (index != 0, "FindIteratorPosition: index != 0"); //\80\80 just checking...
426 goto SuccessfulExit;
427 }
428 else
429 {
430 *right = *middle;
431 *middle = *left;
432 left->buffer = nil;
433 index = leftIndex;
434
435 goto SuccessfulExit;
436 }
437 }
438 else if (index >= ((NodeDescPtr) middle->buffer)->numRecords)
439 {
440 if (((NodeDescPtr) middle->buffer)->fLink == 0) // beyond last record
441 {
442 goto SuccessfulExit;
443 }
444
445 nodeNum = ((NodeDescPtr) middle->buffer)->fLink;
446
447 err = GetRightSiblingNode (btreePtr, middle->buffer, right);
448 M_ExitOnError (err);
449
450 if ( ((NodeDescPtr) right->buffer)->kind != kBTLeafNode ||
451 ((NodeDescPtr) right->buffer)->numRecords <= 0 )
452 {
453 goto SearchTheTree;
454 }
455
456 foundIt = SearchNode (btreePtr, right->buffer, &iterator->key, &rightIndex);
457 if (rightIndex >= ((NodeDescPtr) right->buffer)->numRecords) // we're lost
458 {
459 goto SearchTheTree;
460 }
461 else // we found it, or rightIndex==0, or rightIndex<numRecs
462 {
463 *left = *middle;
464 *middle = *right;
465 right->buffer = nil;
466 index = rightIndex;
467
468 goto SuccessfulExit;
469 }
470 }
471
472
473 //////////////////////////// Search The Tree ////////////////////////////////
474
475 SearchTheTree:
476 {
477 TreePathTable treePathTable; // so we only use stack space if we need to
478
479 err = ReleaseNode (btreePtr, left); M_ExitOnError (err);
480 err = ReleaseNode (btreePtr, middle); M_ExitOnError (err);
481 err = ReleaseNode (btreePtr, right); M_ExitOnError (err);
482
483 err = SearchTree ( btreePtr, &iterator->key, treePathTable, &nodeNum, middle, &index);
484 switch (err) //\80\80 separate find condition from exceptions
485 {
486 case noErr: foundIt = true; break;
487 case fsBTRecordNotFoundErr: break;
488 default: goto ErrorExit;
489 }
490 }
491
492 /////////////////////////////// Success! ////////////////////////////////////
493
494 SuccessfulExit:
495
496 *returnNodeNum = nodeNum;
497 *returnIndex = index;
498 *foundRecord = foundIt;
499
500 return noErr;
501
502
503 ////////////////////////////// Error Exit ///////////////////////////////////
504
505 ErrorExit:
506
507 (void) ReleaseNode (btreePtr, left);
508 (void) ReleaseNode (btreePtr, middle);
509 (void) ReleaseNode (btreePtr, right);
510
511 *returnNodeNum = 0;
512 *returnIndex = 0;
513 *foundRecord = false;
514
515 return err;
516 }
517
518
519
520 /////////////////////////////// CheckInsertParams ///////////////////////////////
521
522 OSStatus CheckInsertParams (FCB *filePtr,
523 BTreeIterator *iterator,
524 FSBufferDescriptor *record,
525 u_int16_t recordLen )
526 {
527 BTreeControlBlockPtr btreePtr;
528
529 if (filePtr == nil) return paramErr;
530
531 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
532 if (btreePtr == nil) return fsBTInvalidFileErr;
533 if (iterator == nil) return paramErr;
534 if (record == nil) return paramErr;
535
536 // check total key/record size limit
537 if ( CalcKeyRecordSize (CalcKeySize(btreePtr, &iterator->key), recordLen) > (btreePtr->nodeSize >> 1))
538 return fsBTRecordTooLargeErr;
539
540 return noErr;
541 }
542
543
544
545 /*-------------------------------------------------------------------------------
546 Routine: TrySimpleReplace - Attempts a simple insert, set, or replace.
547
548 Function: If a hint exitst for the iterator, attempt to find the key in the hint
549 node. If the key is found, an insert operation fails. If the is not
550 found, a replace operation fails. If the key was not found, and the
551 insert position is greater than 0 and less than numRecords, the record
552 is inserted, provided there is enough freeSpace. If the key was found,
553 and there is more freeSpace than the difference between the new record
554 and the old record, the old record is deleted and the new record is
555 inserted.
556
557 Assumptions: iterator key has already been checked by CheckKey
558
559
560 Input: btreePtr - description
561 iterator - description
562 record - description
563 recordLen - description
564 operation - description
565
566
567 Output: recordInserted - description
568
569
570 Result: noErr - success
571 E_RecordExits - insert operation failure
572 != noErr - GetNode, ReleaseNode, UpdateNode returned an error
573 -------------------------------------------------------------------------------*/
574
575 OSStatus TrySimpleReplace (BTreeControlBlockPtr btreePtr,
576 NodeDescPtr nodePtr,
577 BTreeIterator *iterator,
578 FSBufferDescriptor *record,
579 u_int16_t recordLen,
580 Boolean *recordInserted )
581 {
582 u_int32_t oldSpace;
583 u_int32_t spaceNeeded;
584 u_int16_t index;
585 u_int16_t keySize;
586 Boolean foundIt;
587 Boolean didItFit;
588
589
590 *recordInserted = false; // we'll assume this won't work...
591
592 if ( nodePtr->kind != kBTLeafNode )
593 return noErr; // we're in the weeds!
594
595 foundIt = SearchNode (btreePtr, nodePtr, &iterator->key, &index);
596
597 if ( foundIt == false )
598 return noErr; // we might be lost...
599
600 keySize = CalcKeySize(btreePtr, &iterator->key); // includes length field
601
602 spaceNeeded = CalcKeyRecordSize (keySize, recordLen);
603
604 oldSpace = GetRecordSize (btreePtr, nodePtr, index);
605
606 if ( spaceNeeded == oldSpace )
607 {
608 u_int8_t * dst;
609
610 dst = GetRecordAddress (btreePtr, nodePtr, index);
611
612 if ( M_IsOdd (keySize) )
613 ++keySize; // add pad byte
614
615 dst += keySize; // skip over key to point at record
616
617 BlockMoveData(record->bufferAddress, dst, recordLen); // blast away...
618
619 *recordInserted = true;
620 }
621 else if ( (GetNodeFreeSize(btreePtr, nodePtr) + oldSpace) >= spaceNeeded)
622 {
623 DeleteRecord (btreePtr, nodePtr, index);
624
625 didItFit = InsertKeyRecord (btreePtr, nodePtr, index,
626 &iterator->key, KeyLength(btreePtr, &iterator->key),
627 record->bufferAddress, recordLen);
628 PanicIf (didItFit == false, "TrySimpleInsert: InsertKeyRecord returned false!");
629
630 *recordInserted = true;
631 }
632 // else not enough space...
633
634 return noErr;
635 }
636
637
638 /*-------------------------------------------------------------------------------
639 Routine: IsItAHint - checks the hint within a BTreeInterator.
640
641 Function: checks the hint within a BTreeInterator. If it is non-zero, it may
642 possibly be valid.
643
644 Input: btreePtr - pointer to control block for BTree file
645 iterator - pointer to BTreeIterator
646
647 Output: answer - true if the hint looks reasonable
648 - false if the hint is 0
649
650 Result: noErr - success
651 -------------------------------------------------------------------------------*/
652
653
654 OSStatus IsItAHint (BTreeControlBlockPtr btreePtr, BTreeIterator *iterator, Boolean *answer)
655 {
656 ++btreePtr->numHintChecks;
657
658 #if DEBUG
659 if (iterator->hint.nodeNum >= btreePtr->totalNodes)
660 {
661 *answer = false;
662 } else
663
664 #endif
665 if (iterator->hint.nodeNum == 0)
666 {
667 *answer = false;
668 }
669 else
670 {
671 *answer = true;
672 ++btreePtr->numPossibleHints;
673 }
674
675 return noErr;
676 }
mirror of hfs