]> 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-792.18.15.tar.gz
[apple/xnu.git] / bsd / hfs / hfscommon / BTree / BTreeMiscOps.c
1 /*
2 * Copyright (c) 2000-2003 Apple Computer, 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
116
117 ////////////////////////////// Routine Definitions //////////////////////////////
118
119 /*-------------------------------------------------------------------------------
120 Routine: CalcKeyRecordSize - Return size of combined key/record structure.
121
122 Function: Rounds keySize and recSize so they will end on word boundaries.
123 Does NOT add size of offset.
124
125 Input: keySize - length of key (including length field)
126 recSize - length of record data
127
128 Output: none
129
130 Result: UInt16 - size of combined key/record that will be inserted in btree
131 -------------------------------------------------------------------------------*/
132
133 UInt16 CalcKeyRecordSize (UInt16 keySize,
134 UInt16 recSize )
135 {
136 if ( M_IsOdd (keySize) ) keySize += 1; // pad byte
137
138 if (M_IsOdd (recSize) ) recSize += 1; // pad byte
139
140 return (keySize + recSize);
141 }
142
143
144
145 /*-------------------------------------------------------------------------------
146 Routine: VerifyHeader - Validate fields of the BTree header record.
147
148 Function: Examines the fields of the BTree header record to determine if the
149 fork appears to contain a valid BTree.
150
151 Input: forkPtr - pointer to fork control block
152 header - pointer to BTree header
153
154
155 Result: noErr - success
156 != noErr - failure
157 -------------------------------------------------------------------------------*/
158
159 OSStatus VerifyHeader (FCB *filePtr,
160 BTHeaderRec *header )
161 {
162 UInt64 forkSize;
163 UInt32 totalNodes;
164
165
166 switch (header->nodeSize) // node size == 512*2^n
167 {
168 case 512:
169 case 1024:
170 case 2048:
171 case 4096:
172 case 8192:
173 case 16384:
174 case 32768: break;
175 default: return fsBTInvalidHeaderErr; //\80\80 E_BadNodeType
176 }
177
178 totalNodes = header->totalNodes;
179
180 forkSize = (UInt64)totalNodes * (UInt64)header->nodeSize;
181
182 if ( forkSize > filePtr->fcbEOF )
183 return fsBTInvalidHeaderErr;
184
185 if ( header->freeNodes >= totalNodes )
186 return fsBTInvalidHeaderErr;
187
188 if ( header->rootNode >= totalNodes )
189 return fsBTInvalidHeaderErr;
190
191 if ( header->firstLeafNode >= totalNodes )
192 return fsBTInvalidHeaderErr;
193
194 if ( header->lastLeafNode >= totalNodes )
195 return fsBTInvalidHeaderErr;
196
197 if ( header->treeDepth > kMaxTreeDepth )
198 return fsBTInvalidHeaderErr;
199
200
201 /////////////////////////// Check BTree Type ////////////////////////////////
202
203 switch (header->btreeType)
204 {
205 case 0: // HFS Type - no Key Descriptor
206 case kUserBTreeType: // with Key Descriptors etc.
207 case kReservedBTreeType: // Desktop Mgr BTree ?
208 break;
209
210 default: return fsBTUnknownVersionErr;
211 }
212
213 return noErr;
214 }
215
216
217
218 __private_extern__
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 UInt32 options;
245
246 if ((btreePtr->flags & kBTHeaderDirty) == 0) // btree info already flushed
247 return noErr;
248
249
250 err = GetNode (btreePtr, kHeaderNodeNum, &node );
251 if (err != noErr) {
252 return err;
253 }
254
255 // XXXdbg
256 ModifyBlockStart(btreePtr->fileRefNum, &node);
257
258 header = (BTHeaderRec*) ((char *)node.buffer + sizeof(BTNodeDescriptor));
259
260 header->treeDepth = btreePtr->treeDepth;
261 header->rootNode = btreePtr->rootNode;
262 header->leafRecords = btreePtr->leafRecords;
263 header->firstLeafNode = btreePtr->firstLeafNode;
264 header->lastLeafNode = btreePtr->lastLeafNode;
265 header->nodeSize = btreePtr->nodeSize; //\80\80 this shouldn't change
266 header->maxKeyLength = btreePtr->maxKeyLength; //\80\80 neither should this
267 header->totalNodes = btreePtr->totalNodes;
268 header->freeNodes = btreePtr->freeNodes;
269 header->btreeType = btreePtr->btreeType;
270
271 // ignore header->clumpSize; //\80\80 rename this field?
272
273 if (forceWrite)
274 options = kForceWriteBlock;
275 else
276 options = kLockTransaction;
277
278 err = UpdateNode (btreePtr, &node, 0, options);
279
280 btreePtr->flags &= (~kBTHeaderDirty);
281
282 return err;
283 }
284
285
286
287 /*-------------------------------------------------------------------------------
288 Routine: FindIteratorPosition - One_line_description.
289
290 Function: Brief_description_of_the_function_and_any_side_effects
291
292 Algorithm: see FSC.BT.BTIterateRecord.PICT
293
294 Note: //\80\80 document side-effects of bad node hints
295
296 Input: btreePtr - description
297 iterator - description
298
299
300 Output: iterator - description
301 left - description
302 middle - description
303 right - description
304 nodeNum - description
305 returnIndex - description
306 foundRecord - description
307
308
309 Result: noErr - success
310 != noErr - failure
311 -------------------------------------------------------------------------------*/
312
313 OSStatus FindIteratorPosition (BTreeControlBlockPtr btreePtr,
314 BTreeIteratorPtr iterator,
315 BlockDescriptor *left,
316 BlockDescriptor *middle,
317 BlockDescriptor *right,
318 UInt32 *returnNodeNum,
319 UInt16 *returnIndex,
320 Boolean *foundRecord )
321 {
322 OSStatus err;
323 Boolean foundIt;
324 UInt32 nodeNum;
325 UInt16 leftIndex, index, rightIndex;
326 Boolean validHint;
327
328 // assume btreePtr valid
329 // assume left, middle, right point to BlockDescriptors
330 // assume nodeNum points to UInt32
331 // assume index points to UInt16
332 // assume foundRecord points to Boolean
333
334 left->buffer = nil;
335 left->blockHeader = nil;
336 middle->buffer = nil;
337 middle->blockHeader = nil;
338 right->buffer = nil;
339 right->blockHeader = nil;
340
341 foundIt = false;
342
343 if (iterator == nil) // do we have an iterator?
344 {
345 err = fsBTInvalidIteratorErr;
346 goto ErrorExit;
347 }
348
349 err = IsItAHint (btreePtr, iterator, &validHint);
350 M_ExitOnError (err);
351
352 nodeNum = iterator->hint.nodeNum;
353 if (! validHint) // does the hint appear to be valid?
354 {
355 goto SearchTheTree;
356 }
357
358 err = GetNode (btreePtr, nodeNum, middle);
359 if( err == fsBTInvalidNodeErr ) // returned if nodeNum is out of range
360 goto SearchTheTree;
361
362 M_ExitOnError (err);
363
364 if ( ((NodeDescPtr) middle->buffer)->kind != kBTLeafNode ||
365 ((NodeDescPtr) middle->buffer)->numRecords <= 0 )
366 {
367 goto SearchTheTree;
368 }
369
370 ++btreePtr->numValidHints;
371
372 foundIt = SearchNode (btreePtr, middle->buffer, &iterator->key, &index);
373 if (foundIt == true)
374 {
375 goto SuccessfulExit;
376 }
377
378 if (index == 0)
379 {
380 if (((NodeDescPtr) middle->buffer)->bLink == 0) // before 1st btree record
381 {
382 goto SuccessfulExit;
383 }
384
385 nodeNum = ((NodeDescPtr) middle->buffer)->bLink;
386
387 err = GetLeftSiblingNode (btreePtr, middle->buffer, left);
388 M_ExitOnError (err);
389
390 if ( ((NodeDescPtr) left->buffer)->kind != kBTLeafNode ||
391 ((NodeDescPtr) left->buffer)->numRecords <= 0 )
392 {
393 goto SearchTheTree;
394 }
395
396 foundIt = SearchNode (btreePtr, left->buffer, &iterator->key, &leftIndex);
397 if (foundIt == true)
398 {
399 *right = *middle;
400 *middle = *left;
401 left->buffer = nil;
402 index = leftIndex;
403
404 goto SuccessfulExit;
405 }
406
407 if (leftIndex == 0) // we're lost!
408 {
409 goto SearchTheTree;
410 }
411 else if (leftIndex >= ((NodeDescPtr) left->buffer)->numRecords)
412 {
413 nodeNum = ((NodeDescPtr) left->buffer)->fLink;
414
415 PanicIf (index != 0, "\pFindIteratorPosition: index != 0"); //\80\80 just checking...
416 goto SuccessfulExit;
417 }
418 else
419 {
420 *right = *middle;
421 *middle = *left;
422 left->buffer = nil;
423 index = leftIndex;
424
425 goto SuccessfulExit;
426 }
427 }
428 else if (index >= ((NodeDescPtr) middle->buffer)->numRecords)
429 {
430 if (((NodeDescPtr) middle->buffer)->fLink == 0) // beyond last record
431 {
432 goto SuccessfulExit;
433 }
434
435 nodeNum = ((NodeDescPtr) middle->buffer)->fLink;
436
437 err = GetRightSiblingNode (btreePtr, middle->buffer, right);
438 M_ExitOnError (err);
439
440 if ( ((NodeDescPtr) right->buffer)->kind != kBTLeafNode ||
441 ((NodeDescPtr) right->buffer)->numRecords <= 0 )
442 {
443 goto SearchTheTree;
444 }
445
446 foundIt = SearchNode (btreePtr, right->buffer, &iterator->key, &rightIndex);
447 if (rightIndex >= ((NodeDescPtr) right->buffer)->numRecords) // we're lost
448 {
449 goto SearchTheTree;
450 }
451 else // we found it, or rightIndex==0, or rightIndex<numRecs
452 {
453 *left = *middle;
454 *middle = *right;
455 right->buffer = nil;
456 index = rightIndex;
457
458 goto SuccessfulExit;
459 }
460 }
461
462
463 //////////////////////////// Search The Tree ////////////////////////////////
464
465 SearchTheTree:
466 {
467 TreePathTable treePathTable; // so we only use stack space if we need to
468
469 err = ReleaseNode (btreePtr, left); M_ExitOnError (err);
470 err = ReleaseNode (btreePtr, middle); M_ExitOnError (err);
471 err = ReleaseNode (btreePtr, right); M_ExitOnError (err);
472
473 err = SearchTree ( btreePtr, &iterator->key, treePathTable, &nodeNum, middle, &index);
474 switch (err) //\80\80 separate find condition from exceptions
475 {
476 case noErr: foundIt = true; break;
477 case fsBTRecordNotFoundErr: break;
478 default: goto ErrorExit;
479 }
480 }
481
482 /////////////////////////////// Success! ////////////////////////////////////
483
484 SuccessfulExit:
485
486 *returnNodeNum = nodeNum;
487 *returnIndex = index;
488 *foundRecord = foundIt;
489
490 return noErr;
491
492
493 ////////////////////////////// Error Exit ///////////////////////////////////
494
495 ErrorExit:
496
497 (void) ReleaseNode (btreePtr, left);
498 (void) ReleaseNode (btreePtr, middle);
499 (void) ReleaseNode (btreePtr, right);
500
501 *returnNodeNum = 0;
502 *returnIndex = 0;
503 *foundRecord = false;
504
505 return err;
506 }
507
508
509
510 /////////////////////////////// CheckInsertParams ///////////////////////////////
511
512 OSStatus CheckInsertParams (FCB *filePtr,
513 BTreeIterator *iterator,
514 FSBufferDescriptor *record,
515 UInt16 recordLen )
516 {
517 BTreeControlBlockPtr btreePtr;
518
519 if (filePtr == nil) return paramErr;
520
521 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
522 if (btreePtr == nil) return fsBTInvalidFileErr;
523 if (iterator == nil) return paramErr;
524 if (record == nil) return paramErr;
525
526 // check total key/record size limit
527 if ( CalcKeyRecordSize (CalcKeySize(btreePtr, &iterator->key), recordLen) > (btreePtr->nodeSize >> 1))
528 return fsBTRecordTooLargeErr;
529
530 return noErr;
531 }
532
533
534
535 /*-------------------------------------------------------------------------------
536 Routine: TrySimpleReplace - Attempts a simple insert, set, or replace.
537
538 Function: If a hint exitst for the iterator, attempt to find the key in the hint
539 node. If the key is found, an insert operation fails. If the is not
540 found, a replace operation fails. If the key was not found, and the
541 insert position is greater than 0 and less than numRecords, the record
542 is inserted, provided there is enough freeSpace. If the key was found,
543 and there is more freeSpace than the difference between the new record
544 and the old record, the old record is deleted and the new record is
545 inserted.
546
547 Assumptions: iterator key has already been checked by CheckKey
548
549
550 Input: btreePtr - description
551 iterator - description
552 record - description
553 recordLen - description
554 operation - description
555
556
557 Output: recordInserted - description
558
559
560 Result: noErr - success
561 E_RecordExits - insert operation failure
562 != noErr - GetNode, ReleaseNode, UpdateNode returned an error
563 -------------------------------------------------------------------------------*/
564
565 OSStatus TrySimpleReplace (BTreeControlBlockPtr btreePtr,
566 NodeDescPtr nodePtr,
567 BTreeIterator *iterator,
568 FSBufferDescriptor *record,
569 UInt16 recordLen,
570 Boolean *recordInserted )
571 {
572 UInt32 oldSpace;
573 UInt32 spaceNeeded;
574 UInt16 index;
575 UInt16 keySize;
576 Boolean foundIt;
577 Boolean didItFit;
578
579
580 *recordInserted = false; // we'll assume this won't work...
581
582 if ( nodePtr->kind != kBTLeafNode )
583 return noErr; // we're in the weeds!
584
585 foundIt = SearchNode (btreePtr, nodePtr, &iterator->key, &index);
586
587 if ( foundIt == false )
588 return noErr; // we might be lost...
589
590 keySize = CalcKeySize(btreePtr, &iterator->key); // includes length field
591
592 spaceNeeded = CalcKeyRecordSize (keySize, recordLen);
593
594 oldSpace = GetRecordSize (btreePtr, nodePtr, index);
595
596 if ( spaceNeeded == oldSpace )
597 {
598 UInt8 * dst;
599
600 dst = GetRecordAddress (btreePtr, nodePtr, index);
601
602 if ( M_IsOdd (keySize) )
603 ++keySize; // add pad byte
604
605 dst += keySize; // skip over key to point at record
606
607 BlockMoveData(record->bufferAddress, dst, recordLen); // blast away...
608
609 *recordInserted = true;
610 }
611 else if ( (GetNodeFreeSize(btreePtr, nodePtr) + oldSpace) >= spaceNeeded)
612 {
613 DeleteRecord (btreePtr, nodePtr, index);
614
615 didItFit = InsertKeyRecord (btreePtr, nodePtr, index,
616 &iterator->key, KeyLength(btreePtr, &iterator->key),
617 record->bufferAddress, recordLen);
618 PanicIf (didItFit == false, "\pTrySimpleInsert: InsertKeyRecord returned false!");
619
620 *recordInserted = true;
621 }
622 // else not enough space...
623
624 return noErr;
625 }
626
627
628 /*-------------------------------------------------------------------------------
629 Routine: IsItAHint - checks the hint within a BTreeInterator.
630
631 Function: checks the hint within a BTreeInterator. If it is non-zero, it may
632 possibly be valid.
633
634 Input: btreePtr - pointer to control block for BTree file
635 iterator - pointer to BTreeIterator
636
637 Output: answer - true if the hint looks reasonable
638 - false if the hint is 0
639
640 Result: noErr - success
641 -------------------------------------------------------------------------------*/
642
643
644 OSStatus IsItAHint (BTreeControlBlockPtr btreePtr, BTreeIterator *iterator, Boolean *answer)
645 {
646 ++btreePtr->numHintChecks;
647
648 #if DEBUG_BUILD
649 if (iterator->hint.nodeNum >= btreePtr->totalNodes)
650 {
651 *answer = false;
652 } else
653
654 #endif
655 if (iterator->hint.nodeNum == 0)
656 {
657 *answer = false;
658 }
659 else
660 {
661 *answer = true;
662 ++btreePtr->numPossibleHints;
663 }
664
665 return noErr;
666 }
mirror of XNU