]> git.saurik.com Git - apple/xnu.git/blob - bsd/hfs/hfscommon/BTree/BTreeMiscOps.c
projects / apple / xnu.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
xnu-1699.22.73.tar.gz
[apple/xnu.git] / bsd / hfs / hfscommon / BTree / BTreeMiscOps.c
1 /*
2 * Copyright (c) 2000-2003, 2005-2008 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: © 1992-1999 by Apple Computer, 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 "../headers/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 __private_extern__
220 OSStatus TreeIsDirty(BTreeControlBlockPtr btreePtr)
221 {
222 return (btreePtr->flags & kBTHeaderDirty);
223 }
224
225
226
227 /*-------------------------------------------------------------------------------
228 Routine: UpdateHeader - Write BTreeInfoRec fields to Header node.
229
230 Function: Checks the kBTHeaderDirty flag in the BTreeInfoRec and updates the
231 header node if necessary.
232
233 Input: btreePtr - pointer to BTreeInfoRec
234
235
236 Result: noErr - success
237 != noErr - failure
238 -------------------------------------------------------------------------------*/
239
240 OSStatus UpdateHeader(BTreeControlBlockPtr btreePtr, Boolean forceWrite)
241 {
242 OSStatus err;
243 BlockDescriptor node;
244 BTHeaderRec *header;
245 u_int32_t options;
246
247 if ((btreePtr->flags & kBTHeaderDirty) == 0) // btree info already flushed
248 return noErr;
249
250
251 err = GetNode (btreePtr, kHeaderNodeNum, 0, &node );
252 if (err != noErr) {
253 return err;
254 }
255
256 // XXXdbg
257 ModifyBlockStart(btreePtr->fileRefNum, &node);
258
259 header = (BTHeaderRec*) ((char *)node.buffer + sizeof(BTNodeDescriptor));
260
261 header->treeDepth = btreePtr->treeDepth;
262 header->rootNode = btreePtr->rootNode;
263 header->leafRecords = btreePtr->leafRecords;
264 header->firstLeafNode = btreePtr->firstLeafNode;
265 header->lastLeafNode = btreePtr->lastLeafNode;
266 header->nodeSize = btreePtr->nodeSize; //\80\80 this shouldn't change
267 header->maxKeyLength = btreePtr->maxKeyLength; //\80\80 neither should this
268 header->totalNodes = btreePtr->totalNodes;
269 header->freeNodes = btreePtr->freeNodes;
270 header->btreeType = btreePtr->btreeType;
271
272 // ignore header->clumpSize; //\80\80 rename this field?
273
274 if (forceWrite)
275 options = kForceWriteBlock;
276 else
277 options = kLockTransaction;
278
279 err = UpdateNode (btreePtr, &node, 0, options);
280
281 btreePtr->flags &= (~kBTHeaderDirty);
282
283 return err;
284 }
285
286
287
288 /*-------------------------------------------------------------------------------
289 Routine: FindIteratorPosition - One_line_description.
290
291 Function: Brief_description_of_the_function_and_any_side_effects
292
293 Algorithm: see FSC.BT.BTIterateRecord.PICT
294
295 Note: //\80\80 document side-effects of bad node hints
296
297 Input: btreePtr - description
298 iterator - description
299
300
301 Output: iterator - description
302 left - description
303 middle - description
304 right - description
305 nodeNum - description
306 returnIndex - description
307 foundRecord - description
308
309
310 Result: noErr - success
311 != noErr - failure
312 -------------------------------------------------------------------------------*/
313
314 OSStatus FindIteratorPosition (BTreeControlBlockPtr btreePtr,
315 BTreeIteratorPtr iterator,
316 BlockDescriptor *left,
317 BlockDescriptor *middle,
318 BlockDescriptor *right,
319 u_int32_t *returnNodeNum,
320 u_int16_t *returnIndex,
321 Boolean *foundRecord )
322 {
323 OSStatus err;
324 Boolean foundIt;
325 u_int32_t nodeNum;
326 u_int16_t leftIndex, index, rightIndex;
327 Boolean validHint;
328
329 // assume btreePtr valid
330 // assume left, middle, right point to BlockDescriptors
331 // assume nodeNum points to u_int32_t
332 // assume index points to u_int16_t
333 // assume foundRecord points to Boolean
334
335 left->buffer = nil;
336 left->blockHeader = nil;
337 middle->buffer = nil;
338 middle->blockHeader = nil;
339 right->buffer = nil;
340 right->blockHeader = nil;
341
342 foundIt = false;
343
344 if (iterator == nil) // do we have an iterator?
345 {
346 err = fsBTInvalidIteratorErr;
347 goto ErrorExit;
348 }
349
350 err = IsItAHint (btreePtr, iterator, &validHint);
351 M_ExitOnError (err);
352
353 nodeNum = iterator->hint.nodeNum;
354 if (! validHint) // does the hint appear to be valid?
355 {
356 goto SearchTheTree;
357 }
358
359 err = GetNode (btreePtr, nodeNum, kGetNodeHint, middle);
360 if( err == fsBTInvalidNodeErr ) // returned if nodeNum is out of range
361 goto SearchTheTree;
362
363 M_ExitOnError (err);
364
365 if ( ((NodeDescPtr) middle->buffer)->kind != kBTLeafNode ||
366 ((NodeDescPtr) middle->buffer)->numRecords <= 0 )
367 {
368 goto SearchTheTree;
369 }
370
371 foundIt = SearchNode (btreePtr, middle->buffer, &iterator->key, &index);
372 if (foundIt == true)
373 {
374 ++btreePtr->numValidHints;
375 goto SuccessfulExit;
376 }
377 iterator->hint.nodeNum = 0;
378
379 if (index == 0)
380 {
381 if (((NodeDescPtr) middle->buffer)->bLink == 0) // before 1st btree record
382 {
383 goto SuccessfulExit;
384 }
385
386 nodeNum = ((NodeDescPtr) middle->buffer)->bLink;
387
388 // BTree nodes are always grabbed in left to right order.
389 // Therefore release the current node before looking up the
390 // left node.
391 err = ReleaseNode(btreePtr, middle);
392 M_ExitOnError(err);
393
394 // Look up the left node
395 err = GetNode (btreePtr, nodeNum, 0, left);
396 M_ExitOnError (err);
397
398 // Look up the current node again
399 err = GetRightSiblingNode (btreePtr, left->buffer, middle);
400 M_ExitOnError (err);
401
402 if ( ((NodeDescPtr) left->buffer)->kind != kBTLeafNode ||
403 ((NodeDescPtr) left->buffer)->numRecords <= 0 )
404 {
405 goto SearchTheTree;
406 }
407
408 foundIt = SearchNode (btreePtr, left->buffer, &iterator->key, &leftIndex);
409 if (foundIt == true)
410 {
411 *right = *middle;
412 *middle = *left;
413 left->buffer = nil;
414 index = leftIndex;
415
416 goto SuccessfulExit;
417 }
418
419 if (leftIndex == 0) // we're lost!
420 {
421 goto SearchTheTree;
422 }
423 else if (leftIndex >= ((NodeDescPtr) left->buffer)->numRecords)
424 {
425 nodeNum = ((NodeDescPtr) left->buffer)->fLink;
426
427 PanicIf (index != 0, "FindIteratorPosition: index != 0"); //\80\80 just checking...
428 goto SuccessfulExit;
429 }
430 else
431 {
432 *right = *middle;
433 *middle = *left;
434 left->buffer = nil;
435 index = leftIndex;
436
437 goto SuccessfulExit;
438 }
439 }
440 else if (index >= ((NodeDescPtr) middle->buffer)->numRecords)
441 {
442 if (((NodeDescPtr) middle->buffer)->fLink == 0) // beyond last record
443 {
444 goto SuccessfulExit;
445 }
446
447 nodeNum = ((NodeDescPtr) middle->buffer)->fLink;
448
449 err = GetRightSiblingNode (btreePtr, middle->buffer, right);
450 M_ExitOnError (err);
451
452 if ( ((NodeDescPtr) right->buffer)->kind != kBTLeafNode ||
453 ((NodeDescPtr) right->buffer)->numRecords <= 0 )
454 {
455 goto SearchTheTree;
456 }
457
458 foundIt = SearchNode (btreePtr, right->buffer, &iterator->key, &rightIndex);
459 if (rightIndex >= ((NodeDescPtr) right->buffer)->numRecords) // we're lost
460 {
461 goto SearchTheTree;
462 }
463 else // we found it, or rightIndex==0, or rightIndex<numRecs
464 {
465 *left = *middle;
466 *middle = *right;
467 right->buffer = nil;
468 index = rightIndex;
469
470 goto SuccessfulExit;
471 }
472 }
473
474
475 //////////////////////////// Search The Tree ////////////////////////////////
476
477 SearchTheTree:
478 {
479 TreePathTable treePathTable; // so we only use stack space if we need to
480
481 err = ReleaseNode (btreePtr, left); M_ExitOnError (err);
482 err = ReleaseNode (btreePtr, middle); M_ExitOnError (err);
483 err = ReleaseNode (btreePtr, right); M_ExitOnError (err);
484
485 err = SearchTree ( btreePtr, &iterator->key, treePathTable, &nodeNum, middle, &index);
486 switch (err) //\80\80 separate find condition from exceptions
487 {
488 case noErr: foundIt = true; break;
489 case fsBTRecordNotFoundErr: break;
490 default: goto ErrorExit;
491 }
492 }
493
494 /////////////////////////////// Success! ////////////////////////////////////
495
496 SuccessfulExit:
497
498 *returnNodeNum = nodeNum;
499 *returnIndex = index;
500 *foundRecord = foundIt;
501
502 return noErr;
503
504
505 ////////////////////////////// Error Exit ///////////////////////////////////
506
507 ErrorExit:
508
509 (void) ReleaseNode (btreePtr, left);
510 (void) ReleaseNode (btreePtr, middle);
511 (void) ReleaseNode (btreePtr, right);
512
513 *returnNodeNum = 0;
514 *returnIndex = 0;
515 *foundRecord = false;
516
517 return err;
518 }
519
520
521
522 /////////////////////////////// CheckInsertParams ///////////////////////////////
523
524 OSStatus CheckInsertParams (FCB *filePtr,
525 BTreeIterator *iterator,
526 FSBufferDescriptor *record,
527 u_int16_t recordLen )
528 {
529 BTreeControlBlockPtr btreePtr;
530
531 if (filePtr == nil) return paramErr;
532
533 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
534 if (btreePtr == nil) return fsBTInvalidFileErr;
535 if (iterator == nil) return paramErr;
536 if (record == nil) return paramErr;
537
538 // check total key/record size limit
539 if ( CalcKeyRecordSize (CalcKeySize(btreePtr, &iterator->key), recordLen) > (btreePtr->nodeSize >> 1))
540 return fsBTRecordTooLargeErr;
541
542 return noErr;
543 }
544
545
546
547 /*-------------------------------------------------------------------------------
548 Routine: TrySimpleReplace - Attempts a simple insert, set, or replace.
549
550 Function: If a hint exitst for the iterator, attempt to find the key in the hint
551 node. If the key is found, an insert operation fails. If the is not
552 found, a replace operation fails. If the key was not found, and the
553 insert position is greater than 0 and less than numRecords, the record
554 is inserted, provided there is enough freeSpace. If the key was found,
555 and there is more freeSpace than the difference between the new record
556 and the old record, the old record is deleted and the new record is
557 inserted.
558
559 Assumptions: iterator key has already been checked by CheckKey
560
561
562 Input: btreePtr - description
563 iterator - description
564 record - description
565 recordLen - description
566 operation - description
567
568
569 Output: recordInserted - description
570
571
572 Result: noErr - success
573 E_RecordExits - insert operation failure
574 != noErr - GetNode, ReleaseNode, UpdateNode returned an error
575 -------------------------------------------------------------------------------*/
576
577 OSStatus TrySimpleReplace (BTreeControlBlockPtr btreePtr,
578 NodeDescPtr nodePtr,
579 BTreeIterator *iterator,
580 FSBufferDescriptor *record,
581 u_int16_t recordLen,
582 Boolean *recordInserted )
583 {
584 u_int32_t oldSpace;
585 u_int32_t spaceNeeded;
586 u_int16_t index;
587 u_int16_t keySize;
588 Boolean foundIt;
589 Boolean didItFit;
590
591
592 *recordInserted = false; // we'll assume this won't work...
593
594 if ( nodePtr->kind != kBTLeafNode )
595 return noErr; // we're in the weeds!
596
597 foundIt = SearchNode (btreePtr, nodePtr, &iterator->key, &index);
598
599 if ( foundIt == false )
600 return noErr; // we might be lost...
601
602 keySize = CalcKeySize(btreePtr, &iterator->key); // includes length field
603
604 spaceNeeded = CalcKeyRecordSize (keySize, recordLen);
605
606 oldSpace = GetRecordSize (btreePtr, nodePtr, index);
607
608 if ( spaceNeeded == oldSpace )
609 {
610 u_int8_t * dst;
611
612 dst = GetRecordAddress (btreePtr, nodePtr, index);
613
614 if ( M_IsOdd (keySize) )
615 ++keySize; // add pad byte
616
617 dst += keySize; // skip over key to point at record
618
619 BlockMoveData(record->bufferAddress, dst, recordLen); // blast away...
620
621 *recordInserted = true;
622 }
623 else if ( (GetNodeFreeSize(btreePtr, nodePtr) + oldSpace) >= spaceNeeded)
624 {
625 DeleteRecord (btreePtr, nodePtr, index);
626
627 didItFit = InsertKeyRecord (btreePtr, nodePtr, index,
628 &iterator->key, KeyLength(btreePtr, &iterator->key),
629 record->bufferAddress, recordLen);
630 PanicIf (didItFit == false, "TrySimpleInsert: InsertKeyRecord returned false!");
631
632 *recordInserted = true;
633 }
634 // else not enough space...
635
636 return noErr;
637 }
638
639
640 /*-------------------------------------------------------------------------------
641 Routine: IsItAHint - checks the hint within a BTreeInterator.
642
643 Function: checks the hint within a BTreeInterator. If it is non-zero, it may
644 possibly be valid.
645
646 Input: btreePtr - pointer to control block for BTree file
647 iterator - pointer to BTreeIterator
648
649 Output: answer - true if the hint looks reasonable
650 - false if the hint is 0
651
652 Result: noErr - success
653 -------------------------------------------------------------------------------*/
654
655
656 OSStatus IsItAHint (BTreeControlBlockPtr btreePtr, BTreeIterator *iterator, Boolean *answer)
657 {
658 ++btreePtr->numHintChecks;
659
660 #if DEBUG_BUILD
661 if (iterator->hint.nodeNum >= btreePtr->totalNodes)
662 {
663 *answer = false;
664 } else
665
666 #endif
667 if (iterator->hint.nodeNum == 0)
668 {
669 *answer = false;
670 }
671 else
672 {
673 *answer = true;
674 ++btreePtr->numPossibleHints;
675 }
676
677 return noErr;
678 }
mirror of XNU