]> git.saurik.com Git - apple/xnu.git/blob - bsd/hfs/hfscommon/BTree/BTreeMiscOps.c
projects / apple / xnu.git / blob
? search:


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