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