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