]> git.saurik.com Git - apple/hfs.git/blob - fsck_hfs/dfalib/BTreeMiscOps.c
projects / apple / hfs.git / blob
? search:


5faa7414645b9473507639e5cc64017b5abdfd40
[apple/hfs.git] / fsck_hfs / dfalib / BTreeMiscOps.c
1 /*
2 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_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. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
11 * file.
12 *
13 * The Original Code and all software distributed under the License are
14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
20 *
21 * @APPLE_LICENSE_HEADER_END@
22 */
23 /*
24 File: BTreeMiscOps.c
25
26 Contains: Miscellaneous operations for the BTree Module.
27
28 Version: xxx put the technology version here xxx
29
30 Written by: Gordon Sheridan and Bill Bruffey
31
32 Copyright: © 1992-1999 by Apple Computer, Inc., all rights reserved.
33 */
34
35 #include "BTreePrivate.h"
36
37
38 ////////////////////////////// Routine Definitions //////////////////////////////
39
40 /*-------------------------------------------------------------------------------
41 Routine: CalcKeyRecordSize - Return size of combined key/record structure.
42
43 Function: Rounds keySize and recSize so they will end on word boundaries.
44 Does NOT add size of offset.
45
46 Input: keySize - length of key (including length field)
47 recSize - length of record data
48
49 Output: none
50
51 Result: UInt16 - size of combined key/record that will be inserted in btree
52 -------------------------------------------------------------------------------*/
53
54 UInt16 CalcKeyRecordSize (UInt16 keySize,
55 UInt16 recSize )
56 {
57 if ( M_IsOdd (keySize) ) keySize += 1; // pad byte
58
59 if (M_IsOdd (recSize) ) recSize += 1; // pad byte
60
61 return (keySize + recSize);
62 }
63
64
65
66 /*-------------------------------------------------------------------------------
67 Routine: VerifyHeader - Validate fields of the BTree header record.
68
69 Function: Examines the fields of the BTree header record to determine if the
70 fork appears to contain a valid BTree.
71
72 Input: forkPtr - pointer to fork control block
73 header - pointer to BTree header
74
75
76 Result: noErr - success
77 != noErr - failure
78 -------------------------------------------------------------------------------*/
79
80 OSStatus VerifyHeader (SFCB *filePtr,
81 BTHeaderRec *header )
82 {
83 UInt32 forkSize;
84 UInt32 totalNodes;
85
86
87 switch (header->nodeSize) // node size == 512*2^n
88 {
89 case 512:
90 case 1024:
91 case 2048:
92 case 4096:
93 case 8192:
94 case 16384:
95 case 32768: break;
96 default: return fsBTInvalidHeaderErr; //¥¥ E_BadNodeType
97 }
98
99 totalNodes = header->totalNodes;
100
101 forkSize = totalNodes * header->nodeSize;
102
103 if ( forkSize != filePtr->fcbLogicalSize )
104 return fsBTInvalidHeaderErr;
105
106 if ( header->freeNodes >= totalNodes )
107 return fsBTInvalidHeaderErr;
108
109 if ( header->rootNode >= totalNodes )
110 return fsBTInvalidHeaderErr;
111
112 if ( header->firstLeafNode >= totalNodes )
113 return fsBTInvalidHeaderErr;
114
115 if ( header->lastLeafNode >= totalNodes )
116 return fsBTInvalidHeaderErr;
117
118 if ( header->treeDepth > kMaxTreeDepth )
119 return fsBTInvalidHeaderErr;
120
121
122 /////////////////////////// Check BTree Type ////////////////////////////////
123
124 switch (header->btreeType)
125 {
126 case 0: // HFS Type - no Key Descriptor
127 case kUserBTreeType: // with Key Descriptors etc.
128 case kReservedBTreeType: // Desktop Mgr BTree ?
129 break;
130
131 default: return fsBTUnknownVersionErr;
132 }
133
134 return noErr;
135 }
136
137
138
139 /*-------------------------------------------------------------------------------
140 Routine: UpdateHeader - Write BTreeInfoRec fields to Header node.
141
142 Function: Checks the kBTHeaderDirty flag in the BTreeInfoRec and updates the
143 header node if necessary.
144
145 Input: btreePtr - pointer to BTreeInfoRec
146
147
148 Result: noErr - success
149 != noErr - failure
150 -------------------------------------------------------------------------------*/
151
152 OSStatus UpdateHeader (BTreeControlBlockPtr btreePtr)
153 {
154 OSStatus err;
155 BlockDescriptor node;
156 BTHeaderRec *header;
157
158
159 if ((btreePtr->flags & kBTHeaderDirty) == 0) // btree info already flushed
160 return noErr;
161
162
163 err = GetNode (btreePtr, kHeaderNodeNum, &node );
164 if (err != noErr)
165 return err;
166
167 header = (BTHeaderRec*) (node.buffer + sizeof(BTNodeDescriptor));
168
169 header->treeDepth = btreePtr->treeDepth;
170 header->rootNode = btreePtr->rootNode;
171 header->leafRecords = btreePtr->leafRecords;
172 header->firstLeafNode = btreePtr->firstLeafNode;
173 header->lastLeafNode = btreePtr->lastLeafNode;
174 header->nodeSize = btreePtr->nodeSize; //¥¥ this shouldn't change
175 header->maxKeyLength = btreePtr->maxKeyLength; //¥¥ neither should this
176 header->totalNodes = btreePtr->totalNodes;
177 header->freeNodes = btreePtr->freeNodes;
178 header->btreeType = btreePtr->btreeType;
179
180 // ignore header->clumpSize; //¥¥ rename this field?
181
182 err = UpdateNode (btreePtr, &node);
183
184 btreePtr->flags &= (~kBTHeaderDirty);
185
186 return err;
187 }
188
189
190
191 /*-------------------------------------------------------------------------------
192 Routine: FindIteratorPosition - One_line_description.
193
194 Function: Brief_description_of_the_function_and_any_side_effects
195
196 Algorithm: see FSC.BT.BTIterateRecord.PICT
197
198 Note: //¥¥ document side-effects of bad node hints
199
200 Input: btreePtr - description
201 iterator - description
202
203
204 Output: iterator - description
205 left - description
206 middle - description
207 right - description
208 nodeNum - description
209 returnIndex - description
210 foundRecord - description
211
212
213 Result: noErr - success
214 != noErr - failure
215 -------------------------------------------------------------------------------*/
216
217 OSStatus FindIteratorPosition (BTreeControlBlockPtr btreePtr,
218 BTreeIteratorPtr iterator,
219 BlockDescriptor *left,
220 BlockDescriptor *middle,
221 BlockDescriptor *right,
222 UInt32 *returnNodeNum,
223 UInt16 *returnIndex,
224 Boolean *foundRecord )
225 {
226 OSStatus err;
227 Boolean foundIt;
228 UInt32 nodeNum;
229 UInt16 leftIndex, index, rightIndex;
230 Boolean validHint;
231
232 // assume btreePtr valid
233 // assume left, middle, right point to BlockDescriptors
234 // assume nodeNum points to UInt32
235 // assume index points to UInt16
236 // assume foundRecord points to Boolean
237
238 left->buffer = nil;
239 middle->buffer = nil;
240 right->buffer = nil;
241
242 foundIt = false;
243
244 if (iterator == nil) // do we have an iterator?
245 {
246 err = fsBTInvalidIteratorErr;
247 goto ErrorExit;
248 }
249
250 #if SupportsKeyDescriptors
251 //¥¥ verify iterator key (change CheckKey to take btreePtr instead of keyDescPtr?)
252 if (btreePtr->keyDescPtr != nil)
253 {
254 err = CheckKey (&iterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength );
255 M_ExitOnError (err);
256 }
257 #endif
258
259 err = IsItAHint (btreePtr, iterator, &validHint);
260 M_ExitOnError (err);
261
262 nodeNum = iterator->hint.nodeNum;
263 if (! validHint) // does the hint appear to be valid?
264 {
265 goto SearchTheTree;
266 }
267
268 err = GetNode (btreePtr, nodeNum, middle);
269 if( err == fsBTInvalidNodeErr ) // returned if nodeNum is out of range
270 goto SearchTheTree;
271
272 M_ExitOnError (err);
273
274 if ( ((NodeDescPtr) middle->buffer)->kind != kBTLeafNode ||
275 ((NodeDescPtr) middle->buffer)->numRecords <= 0 )
276 {
277 goto SearchTheTree;
278 }
279
280 ++btreePtr->numValidHints;
281
282 foundIt = SearchNode (btreePtr, middle->buffer, &iterator->key, &index);
283 if (foundIt == true)
284 {
285 goto SuccessfulExit;
286 }
287
288 if (index == 0)
289 {
290 if (((NodeDescPtr) middle->buffer)->bLink == 0) // before 1st btree record
291 {
292 goto SuccessfulExit;
293 }
294
295 nodeNum = ((NodeDescPtr) middle->buffer)->bLink;
296
297 err = GetLeftSiblingNode (btreePtr, middle->buffer, left);
298 M_ExitOnError (err);
299
300 if ( ((NodeDescPtr) left->buffer)->kind != kBTLeafNode ||
301 ((NodeDescPtr) left->buffer)->numRecords <= 0 )
302 {
303 goto SearchTheTree;
304 }
305
306 foundIt = SearchNode (btreePtr, left->buffer, &iterator->key, &leftIndex);
307 if (foundIt == true)
308 {
309 *right = *middle;
310 *middle = *left;
311 left->buffer = nil;
312 index = leftIndex;
313
314 goto SuccessfulExit;
315 }
316
317 if (leftIndex == 0) // we're lost!
318 {
319 goto SearchTheTree;
320 }
321 else if (leftIndex >= ((NodeDescPtr) left->buffer)->numRecords)
322 {
323 nodeNum = ((NodeDescPtr) left->buffer)->fLink;
324
325 PanicIf (index != 0, "\pFindIteratorPosition: index != 0"); //¥¥ just checking...
326 goto SuccessfulExit;
327 }
328 else
329 {
330 *right = *middle;
331 *middle = *left;
332 left->buffer = nil;
333 index = leftIndex;
334
335 goto SuccessfulExit;
336 }
337 }
338 else if (index >= ((NodeDescPtr) middle->buffer)->numRecords)
339 {
340 if (((NodeDescPtr) middle->buffer)->fLink == 0) // beyond last record
341 {
342 goto SuccessfulExit;
343 }
344
345 nodeNum = ((NodeDescPtr) middle->buffer)->fLink;
346
347 err = GetRightSiblingNode (btreePtr, middle->buffer, right);
348 M_ExitOnError (err);
349
350 if ( ((NodeDescPtr) right->buffer)->kind != kBTLeafNode ||
351 ((NodeDescPtr) right->buffer)->numRecords <= 0 )
352 {
353 goto SearchTheTree;
354 }
355
356 foundIt = SearchNode (btreePtr, right->buffer, &iterator->key, &rightIndex);
357 if (rightIndex >= ((NodeDescPtr) right->buffer)->numRecords) // we're lost
358 {
359 goto SearchTheTree;
360 }
361 else // we found it, or rightIndex==0, or rightIndex<numRecs
362 {
363 *left = *middle;
364 *middle = *right;
365 right->buffer = nil;
366 index = rightIndex;
367
368 goto SuccessfulExit;
369 }
370 }
371
372
373 //////////////////////////// Search The Tree ////////////////////////////////
374
375 SearchTheTree:
376 {
377 TreePathTable treePathTable; // so we only use stack space if we need to
378
379 err = ReleaseNode (btreePtr, left); M_ExitOnError (err);
380 err = ReleaseNode (btreePtr, middle); M_ExitOnError (err);
381 err = ReleaseNode (btreePtr, right); M_ExitOnError (err);
382
383 err = SearchTree ( btreePtr, &iterator->key, treePathTable, &nodeNum, middle, &index);
384 switch (err) //¥¥ separate find condition from exceptions
385 {
386 case noErr: foundIt = true; break;
387 case fsBTRecordNotFoundErr: break;
388 default: goto ErrorExit;
389 }
390 }
391
392 /////////////////////////////// Success! ////////////////////////////////////
393
394 SuccessfulExit:
395
396 *returnNodeNum = nodeNum;
397 *returnIndex = index;
398 *foundRecord = foundIt;
399
400 return noErr;
401
402
403 ////////////////////////////// Error Exit ///////////////////////////////////
404
405 ErrorExit:
406
407 (void) ReleaseNode (btreePtr, left);
408 (void) ReleaseNode (btreePtr, middle);
409 (void) ReleaseNode (btreePtr, right);
410
411 *returnNodeNum = 0;
412 *returnIndex = 0;
413 *foundRecord = false;
414
415 return err;
416 }
417
418
419
420 /////////////////////////////// CheckInsertParams ///////////////////////////////
421
422 OSStatus CheckInsertParams (SFCB *filePtr,
423 BTreeIterator *iterator,
424 FSBufferDescriptor *record,
425 UInt16 recordLen )
426 {
427 BTreeControlBlockPtr btreePtr;
428
429 if (filePtr == nil) return paramErr;
430
431 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
432 if (btreePtr == nil) return fsBTInvalidFileErr;
433 if (iterator == nil) return paramErr;
434 if (record == nil) return paramErr;
435
436 #if SupportsKeyDescriptors
437 if (btreePtr->keyDescPtr != nil)
438 {
439 OSStatus err;
440
441 err = CheckKey (&iterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength);
442 if (err != noErr)
443 return err;
444 }
445 #endif
446
447 // check total key/record size limit
448 if ( CalcKeyRecordSize (CalcKeySize(btreePtr, &iterator->key), recordLen) > (btreePtr->nodeSize >> 1))
449 return fsBTRecordTooLargeErr;
450
451 return noErr;
452 }
453
454
455
456 /*-------------------------------------------------------------------------------
457 Routine: TrySimpleReplace - Attempts a simple insert, set, or replace.
458
459 Function: If a hint exitst for the iterator, attempt to find the key in the hint
460 node. If the key is found, an insert operation fails. If the is not
461 found, a replace operation fails. If the key was not found, and the
462 insert position is greater than 0 and less than numRecords, the record
463 is inserted, provided there is enough freeSpace. If the key was found,
464 and there is more freeSpace than the difference between the new record
465 and the old record, the old record is deleted and the new record is
466 inserted.
467
468 Assumptions: iterator key has already been checked by CheckKey
469
470
471 Input: btreePtr - description
472 iterator - description
473 record - description
474 recordLen - description
475 operation - description
476
477
478 Output: recordInserted - description
479
480
481 Result: noErr - success
482 E_RecordExits - insert operation failure
483 != noErr - GetNode, ReleaseNode, UpdateNode returned an error
484 -------------------------------------------------------------------------------*/
485
486 OSStatus TrySimpleReplace (BTreeControlBlockPtr btreePtr,
487 NodeDescPtr nodePtr,
488 BTreeIterator *iterator,
489 FSBufferDescriptor *record,
490 UInt16 recordLen,
491 Boolean *recordInserted )
492 {
493 UInt32 oldSpace;
494 UInt32 spaceNeeded;
495 UInt16 index;
496 UInt16 keySize;
497 Boolean foundIt;
498 Boolean didItFit;
499
500
501 *recordInserted = false; // we'll assume this won't work...
502
503 if ( nodePtr->kind != kBTLeafNode )
504 return noErr; // we're in the weeds!
505
506 foundIt = SearchNode (btreePtr, nodePtr, &iterator->key, &index);
507
508 if ( foundIt == false )
509 return noErr; // we might be lost...
510
511 keySize = CalcKeySize(btreePtr, &iterator->key); // includes length field
512
513 spaceNeeded = CalcKeyRecordSize (keySize, recordLen);
514
515 oldSpace = GetRecordSize (btreePtr, nodePtr, index);
516
517 if ( spaceNeeded == oldSpace )
518 {
519 UInt8 * dst;
520
521 dst = GetRecordAddress (btreePtr, nodePtr, index);
522
523 if ( M_IsOdd (keySize) )
524 ++keySize; // add pad byte
525
526 dst += keySize; // skip over key to point at record
527
528 CopyMemory(record->bufferAddress, dst, recordLen); // blast away...
529
530 *recordInserted = true;
531 }
532 else if ( (GetNodeFreeSize(btreePtr, nodePtr) + oldSpace) >= spaceNeeded)
533 {
534 DeleteRecord (btreePtr, nodePtr, index);
535
536 didItFit = InsertKeyRecord (btreePtr, nodePtr, index,
537 &iterator->key, KeyLength(btreePtr, &iterator->key),
538 record->bufferAddress, recordLen);
539 PanicIf (didItFit == false, "\pTrySimpleInsert: InsertKeyRecord returned false!");
540
541 *recordInserted = true;
542 }
543 // else not enough space...
544
545 return noErr;
546 }
547
548
549 /*-------------------------------------------------------------------------------
550 Routine: IsItAHint - checks the hint within a BTreeInterator.
551
552 Function: checks the hint within a BTreeInterator. If it is non-zero, it may
553 possibly be valid.
554
555 Input: btreePtr - pointer to control block for BTree file
556 iterator - pointer to BTreeIterator
557
558 Output: answer - true if the hint looks reasonable
559 - false if the hint is 0
560
561 Result: noErr - success
562 -------------------------------------------------------------------------------*/
563
564
565 OSStatus IsItAHint (BTreeControlBlockPtr btreePtr, BTreeIterator *iterator, Boolean *answer)
566 {
567 ++btreePtr->numHintChecks;
568
569 //¥¥ shouldn't we do a range check?
570 if (iterator->hint.nodeNum == 0)
571 {
572 *answer = false;
573 }
574 else
575 {
576 *answer = true;
577 ++btreePtr->numPossibleHints;
578 }
579
580 return noErr;
581 }
mirror of hfs