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


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