]> git.saurik.com Git - apple/xnu.git/blob - bsd/hfs/hfscommon/BTree/BTree.c
projects / apple / xnu.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
xnu-792.6.56.tar.gz
[apple/xnu.git] / bsd / hfs / hfscommon / BTree / BTree.c
1 /*
2 * Copyright (c) 2000-2004 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: BTree.c
25
26 Contains: Implementation of public interface routines for B-tree manager.
27
28 Version: HFS Plus 1.0
29
30 Written by: Gordon Sheridan and Bill Bruffey
31
32 Copyright: © 1992-1999 by Apple Computer, Inc., all rights reserved.
33
34 File Ownership:
35
36 DRI: Don Brady
37
38 Other Contact: Mark Day
39
40 Technology: File Systems
41
42 Writers:
43
44 (msd) Mark Day
45 (DSH) Deric Horn
46 (djb) Don Brady
47
48 Change History (most recent first):
49 <MOSXS> 9/22/99 ser Added routines BTGetLastSync and BTSetLastSync
50 <MOSXS> 6/1/99 djb Sync up with Mac OS 8.6.
51 <MOSXS> 6/30/98 djb In BTOpenPath make sure nodes are contiguous on disk (radar #2249539).
52 <MOSXS> 4/15/98 djb In BTOpenPath need to clear nodeRec.buffer if GetBlockProc fails.
53 <MOSXS> 4/11/98 djb Add RequireFileLock checking to all external entry points.
54
55 <MOSXS> 03/23/98 djb In BTOpenPath use kTrashBlock option when releasing the header so
56 that we get a full node when we call GetNode.
57
58 <CS9> 12/12/97 djb Radar #2202682, BTIterateRecord with kBTreeCurrentRecord was not
59 checking if we had a record and could call BlockMove with an
60 uninitialize source pointer (causing a bus error).
61 <CS8> 10/24/97 msd In BTIterateRecord, when moving to the previous or next record
62 and we have to move to another node, see if we need to release
63 the node about to be "shifted out" (opposite sibling of the
64 direction we need to move).
65 <CS7> 7/25/97 DSH BTSearchRecord now takes a heuristicHint, nodeNum, and tries it
66 before calling SearchBTree
67 <CS6> 7/24/97 djb GetBlockProc now take a file refnum instead of an FCB ptr.
68 <CS5> 7/22/97 djb Move trace points from BTreeWrapper.c to here.
69 <CS4> 7/21/97 djb LogEndTime now takes an error code.
70 <CS3> 7/16/97 DSH FilesInternal.i renamed FileMgrInternal.i to avoid name
71 collision
72 <CS2> 5/19/97 djb Add summary traces to BTIterateRecord.
73 <CS1> 4/23/97 djb first checked in
74
75 <HFS7> 2/19/97 djb Enable variable sized index keys for HFS+ volumes. Added node
76 cache to support nodes larger than 512 bytes.
77 <HFS6> 1/27/97 djb Calls to InsertTree and DeleteTree are now recursive (to support
78 variable sized index keys).
79 <HFS5> 1/13/97 djb Added support for getting current record to BTIterateRecord.
80 <HFS4> 1/6/97 djb Initialize "BigKeys" attribute in BTOpen.
81 <HFS3> 1/3/97 djb Added support for large keys.
82 <HFS2> 12/23/96 djb On exit map fsBTEmptyErr and fsBTEndOfIterationErr to
83 fsBTRecordNotFoundErr.
84 <HFS1> 12/19/96 djb first checked in
85
86 History applicable to original Scarecrow Design:
87
88 <13> 10/25/96 ser Changing for new VFPI
89 <12> 10/18/96 ser Converting over VFPI changes
90 <11> 9/17/96 dkh More BTree statistics. Modified hint checks to not bail out when
91 an error is returned from GetNode.
92 <10> 9/16/96 dkh Revised BTree statistics.
93 <9> 8/23/96 dkh Remove checks for multiple paths to BTree file. Need to add
94 equivalent mechanism later.
95 <8> 6/20/96 dkh Radar #1358740. Switch from using Pools to debug MemAllocators.
96 <7> 3/14/96 jev Fix BTreeSetRecord, recordFound was not set for the case of a
97 simple replace causing the leafRecords count to get bumped even
98 though we didn't have to add a record.
99 <6> 3/1/96 prp Fix lint problems. Bug in BTSetRecord that does not initialize
100 recordFound.
101 <5> 1/22/96 dkh Add #include Memory.h
102 <4> 1/10/96 msd Use the real function names from Math64.i.
103 <3> 1/4/96 jev Fix BTItererateRecord for the condition when the iterator
104 position routine does not find the record and we are looking for
105 the next record. In such a case, if the node's forrward link is
106 non-zero, we have to keep iterating next and not return
107 fsBTEndOfIterationErr error.
108 <2> 12/7/95 dkh D10E2 build. Changed usage of Ref data type to LogicalAddress.
109 <1> 10/18/95 rst Moved from Scarecrow project.
110
111 <24> 7/18/95 mbb Change MoveData & ClearBytes to BlockMoveData & BlockZero.
112 <23> 1/31/95 prp GetBlockProc interface uses a 64 bit node number.
113 <22> 1/12/95 wjk Adopt Model FileSystem changes in D5.
114 <21> 11/16/94 prp Add IsItAHint routine and use it whenever hint's node number was
115 used for testing.
116 <20> 11/10/94 prp BTGetInfo name collides with the same name in FileManagerPriv.i.
117 Change it to BTGetInformation.
118 <19> 9/30/94 prp Get in sync with D2 interface changes.
119 <18> 7/22/94 wjk Convert to the new set of header files.
120 <17> 12/9/93 wjk Cleanup usage of char, Byte, int8, UInt8, etc.
121 <16> 12/2/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and
122 NRCmds environments.
123 <15> 11/30/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and
124 NRCmds environments.
125 <14> 9/30/93 gs Rename E_NoGetNodeProc and E_NoReleaseNodeProc to
126 E_NoXxxxBlockProc.
127 <13> 8/31/93 prp Use Set64U instead of Set64.
128 <12> 8/16/93 prp In BTSearchRecord, if the input hint found the node and record,
129 set the local nodeNum variable correctly so that the resultant
130 iterator gets set correctly.
131 <11> 7/1/93 gs Fix bug in BTIterateRecord related to kBTreePrevRecord
132 operation.
133 <10> 6/2/93 gs Update for changes to FSErrors.h and add some comments.
134 <9> 5/24/93 gs Fix bug in BTInsert/Set/ReplaceRecord which didn't set node hint
135 properly in some cases.
136 <8> 5/24/93 gs Do NOT map fsBTEmptyErr to fsBTRecordNotFoundErr in BTSearchRecord.
137 <7> 5/24/93 gs Rename BTFlush to BTFlushPath.
138 <6> 5/21/93 gs Add hint optimization to Set/Replace routines.
139 <5> 5/10/93 gs Remove Panic from BTInitialize for small logicalEOF. Implement
140 Insert, Set, Replace, and Delete.
141 <4> 3/23/93 gs Finish BTInitialize.
142 <3> 2/8/93 gs Implement BTSearchRecord and BTIterateRecord.
143 <2> 12/8/92 gs Implement Open and Close routines.
144 <1> 11/15/92 gs first checked in
145
146 */
147
148 #include "../headers/BTreesPrivate.h"
149
150 /*
151 * The amount that the BTree header leaf count can be wrong before we assume
152 * it is in an infinite loop.
153 */
154 #define kNumLeafRecSlack 10
155
156 /* BTree accessor routines */
157 extern OSStatus GetBTreeBlock(FileReference vp, UInt32 blockNum, GetBlockOptions options, BlockDescriptor *block);
158 extern OSStatus SetBTreeBlockSize(FileReference vp, ByteCount blockSize, ItemCount minBlockCount);
159 extern OSStatus ExtendBTreeFile(FileReference vp, FSSize minEOF, FSSize maxEOF);
160 extern OSStatus ReleaseBTreeBlock(FileReference vp, BlockDescPtr blockPtr, ReleaseBlockOptions options);
161
162 //////////////////////////////////// Globals ////////////////////////////////////
163
164
165 /////////////////////////// BTree Module Entry Points ///////////////////////////
166
167
168
169 /*-------------------------------------------------------------------------------
170 Routine: BTOpenPath - Open a file for access as a B*Tree.
171
172 Function: Create BTree control block for a file, if necessary. Validates the
173 file to be sure it looks like a BTree file.
174
175
176 Input: filePtr - pointer to file to open as a B-tree
177 keyCompareProc - pointer to client's KeyCompare function
178
179 Result: noErr - success
180 paramErr - required ptr was nil
181 fsBTInvalidFileErr -
182 memFullErr -
183 != noErr - failure
184 -------------------------------------------------------------------------------*/
185
186 OSStatus BTOpenPath(FCB *filePtr, KeyCompareProcPtr keyCompareProc)
187 {
188 OSStatus err;
189 BTreeControlBlockPtr btreePtr;
190 BTHeaderRec *header;
191 NodeRec nodeRec;
192
193 ////////////////////// Preliminary Error Checking ///////////////////////////
194
195 if ( filePtr == nil )
196 {
197 return paramErr;
198 }
199
200 /*
201 * Subsequent opens allow key compare proc to be changed.
202 */
203 if ( filePtr->fcbBTCBPtr != nil && keyCompareProc != nil) {
204 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
205 btreePtr->keyCompareProc = keyCompareProc;
206 return noErr;
207 }
208
209 if ( filePtr->fcbEOF < kMinNodeSize )
210 return fsBTInvalidFileErr;
211
212
213 //////////////////////// Allocate Control Block /////////////////////////////
214
215 btreePtr = (BTreeControlBlock*) NewPtrSysClear( sizeof( BTreeControlBlock ) );
216 if (btreePtr == nil)
217 {
218 Panic ("\pBTOpen: no memory for btreePtr.");
219 return memFullErr;
220 }
221
222 btreePtr->getBlockProc = GetBTreeBlock;
223 btreePtr->releaseBlockProc = ReleaseBTreeBlock;
224 btreePtr->setEndOfForkProc = ExtendBTreeFile;
225 btreePtr->keyCompareProc = keyCompareProc;
226
227 /////////////////////////// Read Header Node ////////////////////////////////
228
229 nodeRec.buffer = nil; // so we can call ReleaseNode
230 btreePtr->fileRefNum = GetFileRefNumFromFCB(filePtr);
231 filePtr->fcbBTCBPtr = (Ptr) btreePtr; // attach btree cb to file
232
233 /* The minimum node size is the physical block size */
234 nodeRec.blockSize = VTOHFS(btreePtr->fileRefNum)->hfs_phys_block_size;
235
236 /* Start with the allocation block size for regular files. */
237 if (FTOC(filePtr)->c_fileid >= kHFSFirstUserCatalogNodeID)
238 {
239 nodeRec.blockSize = FCBTOVCB(filePtr)->blockSize;
240 }
241 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
242
243 // it is now safe to call M_ExitOnError (err)
244
245 err = SetBTreeBlockSize (btreePtr->fileRefNum, nodeRec.blockSize, 1);
246 M_ExitOnError (err);
247
248
249 err = GetBTreeBlock(btreePtr->fileRefNum,
250 kHeaderNodeNum,
251 kGetBlock,
252 &nodeRec );
253 if (err != noErr)
254 {
255 nodeRec.buffer = nil;
256 nodeRec.blockHeader = nil;
257 Panic("\pBTOpen: getNodeProc returned error getting header node.");
258 goto ErrorExit;
259 }
260 ++btreePtr->numGetNodes;
261 header = (BTHeaderRec*) ((u_long)nodeRec.buffer + sizeof(BTNodeDescriptor));
262
263
264 ///////////////////////////// verify header /////////////////////////////////
265
266 err = VerifyHeader (filePtr, header);
267 M_ExitOnError (err);
268
269
270 ///////////////////// Initalize fields from header //////////////////////////
271
272 PanicIf ( (FCBTOVCB(filePtr)->vcbSigWord != 0x4244) && (header->nodeSize == 512), "\p BTOpenPath: wrong node size for HFS+ volume!"); // 0x4244 = 'BD'
273
274 btreePtr->treeDepth = header->treeDepth;
275 btreePtr->rootNode = header->rootNode;
276 btreePtr->leafRecords = header->leafRecords;
277 btreePtr->firstLeafNode = header->firstLeafNode;
278 btreePtr->lastLeafNode = header->lastLeafNode;
279 btreePtr->nodeSize = header->nodeSize;
280 btreePtr->maxKeyLength = header->maxKeyLength;
281 btreePtr->totalNodes = header->totalNodes;
282 btreePtr->freeNodes = header->freeNodes;
283 if (FTOC(filePtr)->c_fileid >= kHFSFirstUserCatalogNodeID)
284 filePtr->ff_clumpsize = header->clumpSize;
285 btreePtr->btreeType = header->btreeType;
286
287 btreePtr->keyCompareType = header->keyCompareType;
288
289 btreePtr->attributes = header->attributes;
290
291 if ( btreePtr->maxKeyLength > 40 )
292 btreePtr->attributes |= (kBTBigKeysMask + kBTVariableIndexKeysMask); //\80\80 we need a way to save these attributes
293
294 /////////////////////// Initialize dynamic fields ///////////////////////////
295
296 btreePtr->version = kBTreeVersion;
297 btreePtr->flags = 0;
298 btreePtr->writeCount = 1;
299
300 /////////////////////////// Check Header Node ///////////////////////////////
301
302 // set kBadClose attribute bit, and UpdateNode
303
304 /* b-tree node size must be at least as big as the physical block size */
305 if (btreePtr->nodeSize < nodeRec.blockSize)
306 {
307 /*
308 * If this tree has any records or the media is writeable then
309 * we cannot mount using the current physical block size.
310 */
311 if (btreePtr->leafRecords > 0 ||
312 VTOHFS(btreePtr->fileRefNum)->hfs_flags & HFS_WRITEABLE_MEDIA)
313 {
314 err = fsBTBadNodeSize;
315 goto ErrorExit;
316 }
317 }
318
319 /*
320 * If the actual node size is different than the amount we read,
321 * then release and trash this block, and re-read with the correct
322 * node size.
323 */
324 if ( btreePtr->nodeSize != nodeRec.blockSize )
325 {
326 err = SetBTreeBlockSize (btreePtr->fileRefNum, btreePtr->nodeSize, 32);
327 M_ExitOnError (err);
328
329 /*
330 * Need to use kTrashBlock option to force the
331 * buffer cache to read the entire node
332 */
333 err = ReleaseBTreeBlock(btreePtr->fileRefNum, &nodeRec, kTrashBlock);
334 ++btreePtr->numReleaseNodes;
335 M_ExitOnError (err);
336
337 err = GetNode (btreePtr, kHeaderNodeNum, &nodeRec );
338 M_ExitOnError (err);
339 }
340
341 //\80\80 total nodes * node size <= LEOF?
342
343
344 err = ReleaseNode (btreePtr, &nodeRec);
345 M_ExitOnError (err);
346
347 /*
348 * Under Mac OS, b-tree nodes can be non-contiguous on disk when the
349 * allocation block size is smaller than the b-tree node size.
350 *
351 * If journaling is turned on for this volume we can't deal with this
352 * situation and so we bail out. If journaling isn't on it's ok as
353 * hfs_strategy_fragmented() deals with it. Journaling can't support
354 * this because it assumes that if you give it a block that it's
355 * contiguous on disk.
356 */
357 if ( FCBTOHFS(filePtr)->jnl && !NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize) ) {
358 return fsBTInvalidNodeErr;
359 }
360
361 //////////////////////////////// Success ////////////////////////////////////
362
363 //\80\80 align LEOF to multiple of node size? - just on close
364
365 return noErr;
366
367
368 /////////////////////// Error - Clean up and Exit ///////////////////////////
369
370 ErrorExit:
371
372 filePtr->fcbBTCBPtr = nil;
373 (void) ReleaseNode (btreePtr, &nodeRec);
374 DisposePtr( (Ptr) btreePtr );
375
376 return err;
377 }
378
379
380
381 /*-------------------------------------------------------------------------------
382 Routine: BTClosePath - Flush BTree Header and Deallocate Memory for BTree.
383
384 Function: Flush the BTreeControlBlock fields to header node, and delete BTree control
385 block and key descriptor associated with the file if filePtr is last
386 path of type kBTreeType ('btre').
387
388
389 Input: filePtr - pointer to file to delete BTree control block for.
390
391 Result: noErr - success
392 fsBTInvalidFileErr -
393 != noErr - failure
394 -------------------------------------------------------------------------------*/
395
396 OSStatus BTClosePath (FCB *filePtr)
397 {
398 OSStatus err;
399 BTreeControlBlockPtr btreePtr;
400
401 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
402
403 if (btreePtr == nil)
404 return fsBTInvalidFileErr;
405
406 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
407
408 ////////////////////// Check for other BTree Paths //////////////////////////
409
410 btreePtr->attributes &= ~kBTBadCloseMask; // clear "bad close" attribute bit
411 err = UpdateHeader (btreePtr, true);
412 M_ExitOnError (err);
413
414 DisposePtr( (Ptr) btreePtr );
415 filePtr->fcbBTCBPtr = nil;
416
417 return noErr;
418
419 /////////////////////// Error - Clean Up and Exit ///////////////////////////
420
421 ErrorExit:
422
423 return err;
424 }
425
426
427
428 /*-------------------------------------------------------------------------------
429 Routine: BTSearchRecord - Search BTree for a record with a matching key.
430
431 Function: Search for position in B*Tree indicated by searchKey. If a valid node hint
432 is provided, it will be searched first, then SearchTree will be called.
433 If a BTreeIterator is provided, it will be set to the position found as
434 a result of the search. If a record exists at that position, and a BufferDescriptor
435 is supplied, the record will be copied to the buffer (as much as will fit),
436 and recordLen will be set to the length of the record.
437
438 If an error other than fsBTRecordNotFoundErr occurs, the BTreeIterator, if any,
439 is invalidated, and recordLen is set to 0.
440
441
442 Input: pathPtr - pointer to path for BTree file.
443 searchKey - pointer to search key to match.
444 hintPtr - pointer to hint (may be nil)
445
446 Output: record - pointer to BufferDescriptor containing record
447 recordLen - length of data at recordPtr
448 iterator - pointer to BTreeIterator indicating position result of search
449
450 Result: noErr - success, record contains copy of record found
451 fsBTRecordNotFoundErr - record was not found, no data copied
452 fsBTInvalidFileErr - no BTreeControlBlock is allocated for the fork
453 fsBTInvalidKeyLengthErr -
454 != noErr - failure
455 -------------------------------------------------------------------------------*/
456
457 OSStatus BTSearchRecord (FCB *filePtr,
458 BTreeIterator *searchIterator,
459 FSBufferDescriptor *record,
460 UInt16 *recordLen,
461 BTreeIterator *resultIterator )
462 {
463 OSStatus err;
464 BTreeControlBlockPtr btreePtr;
465 TreePathTable treePathTable;
466 UInt32 nodeNum;
467 BlockDescriptor node;
468 UInt16 index;
469 BTreeKeyPtr keyPtr;
470 RecordPtr recordPtr;
471 UInt16 len;
472 Boolean foundRecord;
473 Boolean validHint;
474
475 if (filePtr == nil) return paramErr;
476 if (searchIterator == nil) return paramErr;
477
478 node.buffer = nil;
479 node.blockHeader = nil;
480
481 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
482 if (btreePtr == nil) return fsBTInvalidFileErr;
483
484 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
485
486 foundRecord = false;
487
488 ////////////////////////////// Take A Hint //////////////////////////////////
489
490 err = IsItAHint (btreePtr, searchIterator, &validHint);
491 M_ExitOnError (err);
492
493 if (validHint)
494 {
495 nodeNum = searchIterator->hint.nodeNum;
496
497 err = GetNode (btreePtr, nodeNum, &node);
498 if( err == noErr )
499 {
500 if ( ((BTNodeDescriptor*) node.buffer)->kind == kBTLeafNode &&
501 ((BTNodeDescriptor*) node.buffer)->numRecords > 0 )
502 {
503 foundRecord = SearchNode (btreePtr, node.buffer, &searchIterator->key, &index);
504
505 //\80\80 if !foundRecord, we could still skip tree search if ( 0 < index < numRecords )
506 }
507
508 if (foundRecord == false)
509 {
510 err = ReleaseNode (btreePtr, &node);
511 M_ExitOnError (err);
512 }
513 else
514 {
515 ++btreePtr->numValidHints;
516 }
517 }
518
519 if( foundRecord == false )
520 (void) BTInvalidateHint( searchIterator );
521 }
522
523
524 //////////////////////////// Search The Tree ////////////////////////////////
525
526 if (foundRecord == false)
527 {
528 err = SearchTree ( btreePtr, &searchIterator->key, treePathTable, &nodeNum, &node, &index);
529 switch (err)
530 {
531 case noErr: foundRecord = true; break;
532 case fsBTRecordNotFoundErr: break;
533 default: goto ErrorExit;
534 }
535 }
536
537
538 //////////////////////////// Get the Record /////////////////////////////////
539
540 if (foundRecord == true)
541 {
542 //XXX Should check for errors! Or BlockMove could choke on recordPtr!!!
543 GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
544
545 if (recordLen != nil) *recordLen = len;
546
547 if (record != nil)
548 {
549 ByteCount recordSize;
550
551 recordSize = record->itemCount * record->itemSize;
552
553 if (len > recordSize) len = recordSize;
554
555 BlockMoveData (recordPtr, record->bufferAddress, len);
556 }
557 }
558
559
560 /////////////////////// Success - Update Iterator ///////////////////////////
561
562 if (resultIterator != nil)
563 {
564 resultIterator->hint.writeCount = btreePtr->writeCount;
565 resultIterator->hint.nodeNum = nodeNum;
566 resultIterator->hint.index = index;
567 #if DEBUG_BUILD
568 resultIterator->hint.reserved1 = 0;
569 resultIterator->hint.reserved2 = 0;
570 resultIterator->version = 0;
571 resultIterator->reserved = 0;
572 #endif
573 // copy the key in the BTree when found rather than searchIterator->key to get proper case/diacriticals
574 if (foundRecord == true)
575 BlockMoveData ((Ptr)keyPtr, (Ptr)&resultIterator->key, CalcKeySize(btreePtr, keyPtr));
576 else
577 BlockMoveData ((Ptr)&searchIterator->key, (Ptr)&resultIterator->key, CalcKeySize(btreePtr, &searchIterator->key));
578 }
579
580 err = ReleaseNode (btreePtr, &node);
581 M_ExitOnError (err);
582
583 if (foundRecord == false) return fsBTRecordNotFoundErr;
584 else return noErr;
585
586
587 /////////////////////// Error - Clean Up and Exit ///////////////////////////
588
589 ErrorExit:
590
591 if (recordLen != nil)
592 *recordLen = 0;
593
594 if (resultIterator != nil)
595 {
596 resultIterator->hint.writeCount = 0;
597 resultIterator->hint.nodeNum = 0;
598 resultIterator->hint.index = 0;
599 resultIterator->hint.reserved1 = 0;
600 resultIterator->hint.reserved2 = 0;
601
602 resultIterator->version = 0;
603 resultIterator->reserved = 0;
604 resultIterator->key.length16 = 0; // zero out two bytes to cover both types of keys
605 }
606
607 if ( err == fsBTEmptyErr )
608 err = fsBTRecordNotFoundErr;
609
610 return err;
611 }
612
613
614
615 /*-------------------------------------------------------------------------------
616 Routine: BTIterateRecord - Find the first, next, previous, or last record.
617
618 Function: Find the first, next, previous, or last record in the BTree
619
620 Input: pathPtr - pointer to path iterate records for.
621 operation - iteration operation (first,next,prev,last)
622 iterator - pointer to iterator indicating start position
623
624 Output: iterator - iterator is updated to indicate new position
625 newKeyPtr - pointer to buffer to copy key found by iteration
626 record - pointer to buffer to copy record found by iteration
627 recordLen - length of record
628
629 Result: noErr - success
630 != noErr - failure
631 -------------------------------------------------------------------------------*/
632
633 OSStatus BTIterateRecord (FCB *filePtr,
634 BTreeIterationOperation operation,
635 BTreeIterator *iterator,
636 FSBufferDescriptor *record,
637 UInt16 *recordLen )
638 {
639 OSStatus err;
640 BTreeControlBlockPtr btreePtr;
641 BTreeKeyPtr keyPtr;
642 RecordPtr recordPtr;
643 UInt16 len;
644
645 Boolean foundRecord;
646 UInt32 nodeNum;
647
648 BlockDescriptor left, node, right;
649 UInt16 index;
650
651
652 ////////////////////////// Priliminary Checks ///////////////////////////////
653
654 left.buffer = nil;
655 left.blockHeader = nil;
656 right.buffer = nil;
657 right.blockHeader = nil;
658 node.buffer = nil;
659 node.blockHeader = nil;
660
661
662 if (filePtr == nil)
663 {
664 return paramErr;
665 }
666
667 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
668 if (btreePtr == nil)
669 {
670 return fsBTInvalidFileErr; //\80\80 handle properly
671 }
672
673 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
674
675 if ((operation != kBTreeFirstRecord) &&
676 (operation != kBTreeNextRecord) &&
677 (operation != kBTreeCurrentRecord) &&
678 (operation != kBTreePrevRecord) &&
679 (operation != kBTreeLastRecord))
680 {
681 err = fsInvalidIterationMovmentErr;
682 goto ErrorExit;
683 }
684
685 /////////////////////// Find First or Last Record ///////////////////////////
686
687 if ((operation == kBTreeFirstRecord) || (operation == kBTreeLastRecord))
688 {
689 if (operation == kBTreeFirstRecord) nodeNum = btreePtr->firstLeafNode;
690 else nodeNum = btreePtr->lastLeafNode;
691
692 if (nodeNum == 0)
693 {
694 err = fsBTEmptyErr;
695 goto ErrorExit;
696 }
697
698 err = GetNode (btreePtr, nodeNum, &node);
699 M_ExitOnError (err);
700
701 if ( ((NodeDescPtr) node.buffer)->kind != kBTLeafNode ||
702 ((NodeDescPtr) node.buffer)->numRecords <= 0 )
703 {
704 err = ReleaseNode (btreePtr, &node);
705 M_ExitOnError (err);
706
707 err = fsBTInvalidNodeErr;
708 MARK_VOLUMEDAMAGED(filePtr);
709 goto ErrorExit;
710 }
711
712 if (operation == kBTreeFirstRecord) index = 0;
713 else index = ((BTNodeDescriptor*) node.buffer)->numRecords - 1;
714
715 goto CopyData; //\80\80 is there a cleaner way?
716 }
717
718
719 //////////////////////// Find Iterator Position /////////////////////////////
720
721 err = FindIteratorPosition (btreePtr, iterator,
722 &left, &node, &right, &nodeNum, &index, &foundRecord);
723 M_ExitOnError (err);
724
725
726 ///////////////////// Find Next Or Previous Record //////////////////////////
727
728 if (operation == kBTreePrevRecord)
729 {
730 if (index > 0)
731 {
732 --index;
733 }
734 else
735 {
736 if (left.buffer == nil)
737 {
738 nodeNum = ((NodeDescPtr) node.buffer)->bLink;
739 if ( nodeNum > 0)
740 {
741 err = GetNode (btreePtr, nodeNum, &left);
742 M_ExitOnError (err);
743 } else {
744 err = fsBTStartOfIterationErr;
745 goto ErrorExit;
746 }
747 }
748 // Before we stomp on "right", we'd better release it if needed
749 if (right.buffer != nil) {
750 err = ReleaseNode(btreePtr, &right);
751 M_ExitOnError(err);
752 }
753 right = node;
754 node = left;
755 left.buffer = nil;
756 index = ((NodeDescPtr) node.buffer)->numRecords -1;
757 }
758 }
759 else if (operation == kBTreeNextRecord)
760 {
761 if ((foundRecord != true) &&
762 (((NodeDescPtr) node.buffer)->fLink == 0) &&
763 (index == ((NodeDescPtr) node.buffer)->numRecords))
764 {
765 err = fsBTEndOfIterationErr;
766 goto ErrorExit;
767 }
768
769 // we did not find the record but the index is already positioned correctly
770 if ((foundRecord == false) && (index != ((NodeDescPtr) node.buffer)->numRecords))
771 goto CopyData;
772
773 // we found the record OR we have to look in the next node
774 if (index < ((NodeDescPtr) node.buffer)->numRecords -1)
775 {
776 ++index;
777 }
778 else
779 {
780 if (right.buffer == nil)
781 {
782 nodeNum = ((NodeDescPtr) node.buffer)->fLink;
783 if ( nodeNum > 0)
784 {
785 err = GetNode (btreePtr, nodeNum, &right);
786 M_ExitOnError (err);
787 } else {
788 err = fsBTEndOfIterationErr;
789 goto ErrorExit;
790 }
791 }
792 // Before we stomp on "left", we'd better release it if needed
793 if (left.buffer != nil) {
794 err = ReleaseNode(btreePtr, &left);
795 M_ExitOnError(err);
796 }
797 left = node;
798 node = right;
799 right.buffer = nil;
800 index = 0;
801 }
802 }
803 else // operation == kBTreeCurrentRecord
804 {
805 // make sure we have something... <CS9>
806 if ((foundRecord != true) &&
807 (index >= ((NodeDescPtr) node.buffer)->numRecords))
808 {
809 err = fsBTEndOfIterationErr;
810 goto ErrorExit;
811 }
812 }
813
814 //////////////////// Copy Record And Update Iterator ////////////////////////
815
816 CopyData:
817
818 // added check for errors <CS9>
819 err = GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
820 M_ExitOnError (err);
821
822 if (recordLen != nil)
823 *recordLen = len;
824
825 if (record != nil)
826 {
827 ByteCount recordSize;
828
829 recordSize = record->itemCount * record->itemSize;
830
831 if (len > recordSize) len = recordSize;
832
833 BlockMoveData (recordPtr, record->bufferAddress, len);
834 }
835
836 if (iterator != nil) // first & last do not require iterator
837 {
838 iterator->hint.writeCount = btreePtr->writeCount;
839 iterator->hint.nodeNum = nodeNum;
840 iterator->hint.index = index;
841 iterator->hint.reserved1 = 0;
842 iterator->hint.reserved2 = 0;
843
844 iterator->version = 0;
845 iterator->reserved = 0;
846
847 /* SER
848 * Check for infinite loops by making sure we do not
849 * process more leaf records, than can possibly be (or the BTree header
850 * is seriously damaged)....a brute force method.
851 */
852 if ((operation == kBTreeFirstRecord) || (operation == kBTreeLastRecord))
853 iterator->hitCount = 1;
854 else if (operation != kBTreeCurrentRecord)
855 iterator->hitCount += 1;
856 /* Always use the highest max, in case the grows while iterating */
857 iterator->maxLeafRecs = max(btreePtr->leafRecords, iterator->maxLeafRecs);
858
859 #if 0
860 if (iterator->hitCount > iterator->maxLeafRecs + kNumLeafRecSlack)
861 {
862 err = fsBTInvalidNodeErr;
863 MARK_VOLUMEDAMAGED(filePtr);
864 goto ErrorExit;
865 }
866 #endif
867
868 BlockMoveData ((Ptr)keyPtr, (Ptr)&iterator->key, CalcKeySize(btreePtr, keyPtr));
869 }
870
871
872 ///////////////////////////// Release Nodes /////////////////////////////////
873
874 err = ReleaseNode (btreePtr, &node);
875 M_ExitOnError (err);
876
877 if (left.buffer != nil)
878 {
879 err = ReleaseNode (btreePtr, &left);
880 M_ExitOnError (err);
881 }
882
883 if (right.buffer != nil)
884 {
885 err = ReleaseNode (btreePtr, &right);
886 M_ExitOnError (err);
887 }
888
889 return noErr;
890
891 /////////////////////// Error - Clean Up and Exit ///////////////////////////
892
893 ErrorExit:
894
895 (void) ReleaseNode (btreePtr, &left);
896 (void) ReleaseNode (btreePtr, &node);
897 (void) ReleaseNode (btreePtr, &right);
898
899 if (recordLen != nil)
900 *recordLen = 0;
901
902 if (iterator != nil)
903 {
904 iterator->hint.writeCount = 0;
905 iterator->hint.nodeNum = 0;
906 iterator->hint.index = 0;
907 iterator->hint.reserved1 = 0;
908 iterator->hint.reserved2 = 0;
909
910 iterator->version = 0;
911 iterator->reserved = 0;
912 iterator->key.length16 = 0;
913 }
914
915 if ( err == fsBTEmptyErr || err == fsBTEndOfIterationErr )
916 err = fsBTRecordNotFoundErr;
917
918 return err;
919 }
920
921
922 /*-------------------------------------------------------------------------------
923 Routine: BTIterateRecords
924
925 Function: Find a series of records
926
927 Input: filePtr - b-tree file
928 operation - iteration operation (first,next,prev,last)
929 iterator - pointer to iterator indicating start position
930 callBackProc - pointer to routince to process a record
931 callBackState - pointer to state data (used by callBackProc)
932
933 Output: iterator - iterator is updated to indicate new position
934
935 Result: noErr - success
936 != noErr - failure
937 -------------------------------------------------------------------------------*/
938
939 OSStatus
940 BTIterateRecords(FCB *filePtr, BTreeIterationOperation operation, BTreeIterator *iterator,
941 IterateCallBackProcPtr callBackProc, void * callBackState)
942 {
943 OSStatus err;
944 BTreeControlBlockPtr btreePtr;
945 BTreeKeyPtr keyPtr;
946 RecordPtr recordPtr;
947 UInt16 len;
948 Boolean foundRecord;
949 UInt32 nodeNum;
950 BlockDescriptor left, node, right;
951 UInt16 index;
952
953
954 ////////////////////////// Priliminary Checks ///////////////////////////////
955
956 left.buffer = nil;
957 left.blockHeader = nil;
958 right.buffer = nil;
959 right.blockHeader = nil;
960 node.buffer = nil;
961 node.blockHeader = nil;
962
963 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
964
965 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
966
967 if ((operation != kBTreeFirstRecord) &&
968 (operation != kBTreeNextRecord) &&
969 (operation != kBTreeCurrentRecord) &&
970 (operation != kBTreePrevRecord) &&
971 (operation != kBTreeLastRecord))
972 {
973 err = fsInvalidIterationMovmentErr;
974 goto ErrorExit;
975 }
976
977 /////////////////////// Find First or Last Record ///////////////////////////
978
979 if ((operation == kBTreeFirstRecord) || (operation == kBTreeLastRecord))
980 {
981 if (operation == kBTreeFirstRecord)
982 nodeNum = btreePtr->firstLeafNode;
983 else
984 nodeNum = btreePtr->lastLeafNode;
985
986 if (nodeNum == 0)
987 {
988 err = fsBTEmptyErr;
989 goto ErrorExit;
990 }
991
992 err = GetNode(btreePtr, nodeNum, &node);
993 M_ExitOnError(err);
994
995 if ( ((NodeDescPtr)node.buffer)->kind != kBTLeafNode ||
996 ((NodeDescPtr)node.buffer)->numRecords <= 0 )
997 {
998 err = ReleaseNode(btreePtr, &node);
999 M_ExitOnError(err);
1000
1001 err = fsBTInvalidNodeErr;
1002 MARK_VOLUMEDAMAGED(filePtr);
1003 goto ErrorExit;
1004 }
1005
1006 if (operation == kBTreeFirstRecord)
1007 index = 0;
1008 else
1009 index = ((BTNodeDescriptor*) node.buffer)->numRecords - 1;
1010
1011 goto ProcessData;
1012 }
1013
1014 //////////////////////// Find Iterator Position /////////////////////////////
1015
1016 err = FindIteratorPosition(btreePtr, iterator, &left, &node, &right,
1017 &nodeNum, &index, &foundRecord);
1018 if (err == fsBTRecordNotFoundErr)
1019 err = 0;
1020 M_ExitOnError(err);
1021
1022
1023 ///////////////////// Find Next Or Previous Record //////////////////////////
1024
1025 if (operation == kBTreePrevRecord)
1026 {
1027 if (index > 0)
1028 {
1029 --index;
1030 }
1031 else
1032 {
1033 if (left.buffer == nil)
1034 {
1035 nodeNum = ((NodeDescPtr) node.buffer)->bLink;
1036 if ( nodeNum > 0)
1037 {
1038 err = GetNode(btreePtr, nodeNum, &left);
1039 M_ExitOnError(err);
1040 } else {
1041 err = fsBTStartOfIterationErr;
1042 goto ErrorExit;
1043 }
1044 }
1045 // Before we stomp on "right", we'd better release it if needed
1046 if (right.buffer != nil) {
1047 err = ReleaseNode(btreePtr, &right);
1048 M_ExitOnError(err);
1049 }
1050 right = node;
1051 node = left;
1052 left.buffer = nil;
1053 index = ((NodeDescPtr) node.buffer)->numRecords -1;
1054 }
1055 }
1056 else if (operation == kBTreeNextRecord)
1057 {
1058 if ((foundRecord != true) &&
1059 (((NodeDescPtr)node.buffer)->fLink == 0) &&
1060 (index == ((NodeDescPtr)node.buffer)->numRecords))
1061 {
1062 err = fsBTEndOfIterationErr;
1063 goto ErrorExit;
1064 }
1065
1066 // we did not find the record but the index is already positioned correctly
1067 if ((foundRecord == false) && (index != ((NodeDescPtr)node.buffer)->numRecords))
1068 goto ProcessData;
1069
1070 // we found the record OR we have to look in the next node
1071 if (index < ((NodeDescPtr)node.buffer)->numRecords -1)
1072 {
1073 ++index;
1074 }
1075 else
1076 {
1077 if (right.buffer == nil)
1078 {
1079 nodeNum = ((NodeDescPtr)node.buffer)->fLink;
1080 if ( nodeNum > 0)
1081 {
1082 err = GetNode(btreePtr, nodeNum, &right);
1083 M_ExitOnError(err);
1084 } else {
1085 err = fsBTEndOfIterationErr;
1086 goto ErrorExit;
1087 }
1088 }
1089 // Before we stomp on "left", we'd better release it if needed
1090 if (left.buffer != nil) {
1091 err = ReleaseNode(btreePtr, &left);
1092 M_ExitOnError(err);
1093 }
1094 left = node;
1095 node = right;
1096 right.buffer = nil;
1097 index = 0;
1098 }
1099 }
1100 else // operation == kBTreeCurrentRecord
1101 {
1102 // make sure we have something... <CS9>
1103 if ((foundRecord != true) &&
1104 (index >= ((NodeDescPtr)node.buffer)->numRecords))
1105 {
1106 err = fsBTEndOfIterationErr;
1107 goto ErrorExit;
1108 }
1109 }
1110
1111 //////////////////// Process Records Using Callback ////////////////////////
1112
1113 ProcessData:
1114 err = GetRecordByIndex(btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
1115 if (err) {
1116 err = btBadNode;
1117 goto ErrorExit;
1118 }
1119
1120 while (err == 0) {
1121 if (callBackProc(keyPtr, recordPtr, callBackState) == 0)
1122 break;
1123
1124 if ((index+1) < ((NodeDescPtr)node.buffer)->numRecords) {
1125 ++index;
1126 } else {
1127 if (right.buffer == nil)
1128 {
1129 nodeNum = ((NodeDescPtr)node.buffer)->fLink;
1130 if ( nodeNum > 0)
1131 {
1132 err = GetNode(btreePtr, nodeNum, &right);
1133 M_ExitOnError(err);
1134 } else {
1135 err = fsBTEndOfIterationErr;
1136 break;
1137 }
1138 }
1139 // Before we stomp on "left", we'd better release it if needed
1140 if (left.buffer != nil) {
1141 err = ReleaseNode(btreePtr, &left);
1142 M_ExitOnError(err);
1143 }
1144 left = node;
1145 node = right;
1146 right.buffer = nil;
1147 index = 0;
1148 }
1149 err = GetRecordByIndex(btreePtr, node.buffer, index,
1150 &keyPtr, &recordPtr, &len);
1151 if (err) {
1152 err = btBadNode;
1153 goto ErrorExit;
1154 }
1155 }
1156
1157
1158 ///////////////// Update Iterator to Last Item Processed /////////////////////
1159
1160
1161 if (iterator != nil) // first & last have optional iterator
1162 {
1163 iterator->hint.writeCount = btreePtr->writeCount;
1164 iterator->hint.nodeNum = nodeNum;
1165 iterator->hint.index = index;
1166 iterator->version = 0;
1167
1168 BlockMoveData((Ptr)keyPtr, (Ptr)&iterator->key, CalcKeySize(btreePtr, keyPtr));
1169 }
1170 M_ExitOnError(err);
1171
1172
1173 ///////////////////////////// Release Nodes /////////////////////////////////
1174
1175 err = ReleaseNode(btreePtr, &node);
1176 M_ExitOnError(err);
1177
1178 if (left.buffer != nil)
1179 {
1180 err = ReleaseNode(btreePtr, &left);
1181 M_ExitOnError(err);
1182 }
1183
1184 if (right.buffer != nil)
1185 {
1186 err = ReleaseNode(btreePtr, &right);
1187 M_ExitOnError(err);
1188 }
1189
1190 return noErr;
1191
1192 /////////////////////// Error - Clean Up and Exit ///////////////////////////
1193
1194 ErrorExit:
1195
1196 (void) ReleaseNode(btreePtr, &left);
1197 (void) ReleaseNode(btreePtr, &node);
1198 (void) ReleaseNode(btreePtr, &right);
1199
1200 if (iterator != nil)
1201 {
1202 iterator->hint.writeCount = 0;
1203 iterator->hint.nodeNum = 0;
1204 iterator->hint.index = 0;
1205 iterator->version = 0;
1206 iterator->key.length16 = 0;
1207 }
1208
1209 if ( err == fsBTEmptyErr || err == fsBTEndOfIterationErr )
1210 err = fsBTRecordNotFoundErr;
1211
1212 return err;
1213 }
1214
1215
1216 //////////////////////////////// BTInsertRecord /////////////////////////////////
1217
1218 OSStatus BTInsertRecord (FCB *filePtr,
1219 BTreeIterator *iterator,
1220 FSBufferDescriptor *record,
1221 UInt16 recordLen )
1222 {
1223 OSStatus err;
1224 BTreeControlBlockPtr btreePtr;
1225 TreePathTable treePathTable;
1226 SInt32 nodesNeeded;
1227 BlockDescriptor nodeRec;
1228 UInt32 insertNodeNum;
1229 UInt16 index;
1230 Boolean recordFit;
1231
1232 ////////////////////////// Priliminary Checks ///////////////////////////////
1233
1234 nodeRec.buffer = nil; // so we can call ReleaseNode
1235 nodeRec.blockHeader = nil;
1236
1237 err = CheckInsertParams (filePtr, iterator, record, recordLen);
1238 if (err != noErr)
1239 return err;
1240
1241 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1242
1243 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
1244
1245
1246 ///////////////////////// Find Insert Position //////////////////////////////
1247
1248 // always call SearchTree for Insert
1249 err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
1250
1251 switch (err) // set/replace/insert decision point
1252 {
1253 case noErr: err = fsBTDuplicateRecordErr;
1254 goto ErrorExit;
1255
1256 case fsBTRecordNotFoundErr: break;
1257
1258 case fsBTEmptyErr: // if tree empty add 1st leaf node
1259
1260 if (BTAvailableNodes(btreePtr) == 0)
1261 {
1262 err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1);
1263 M_ExitOnError (err);
1264 }
1265
1266 err = AllocateNode (btreePtr, &insertNodeNum);
1267 M_ExitOnError (err);
1268
1269 err = GetNewNode (btreePtr, insertNodeNum, &nodeRec);
1270 M_ExitOnError (err);
1271
1272 // XXXdbg
1273 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
1274
1275 ((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode;
1276 ((NodeDescPtr)nodeRec.buffer)->height = 1;
1277
1278 recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, 0,
1279 &iterator->key, KeyLength(btreePtr, &iterator->key),
1280 record->bufferAddress, recordLen );
1281 if (recordFit != true)
1282 {
1283 err = fsBTRecordTooLargeErr;
1284 goto ErrorExit;
1285 }
1286
1287 /*
1288 * Update the B-tree control block. Do this before
1289 * calling UpdateNode since it will compare the node's
1290 * height with treeDepth.
1291 */
1292 btreePtr->treeDepth = 1;
1293 btreePtr->rootNode = insertNodeNum;
1294 btreePtr->firstLeafNode = insertNodeNum;
1295 btreePtr->lastLeafNode = insertNodeNum;
1296
1297 err = UpdateNode (btreePtr, &nodeRec, 0, kLockTransaction);
1298 M_ExitOnError (err);
1299
1300 M_BTreeHeaderDirty (btreePtr);
1301
1302 goto Success;
1303
1304 default: goto ErrorExit;
1305 }
1306
1307 if (index > 0)
1308 {
1309 // XXXdbg
1310 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
1311
1312 recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, index,
1313 &iterator->key, KeyLength(btreePtr, &iterator->key),
1314 record->bufferAddress, recordLen);
1315 if (recordFit == true)
1316 {
1317 err = UpdateNode (btreePtr, &nodeRec, 0, kLockTransaction);
1318 M_ExitOnError (err);
1319
1320 goto Success;
1321 }
1322 }
1323
1324 /////////////////////// Extend File If Necessary ////////////////////////////
1325
1326 nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);
1327 if (nodesNeeded > 0)
1328 {
1329 nodesNeeded += (SInt32)btreePtr->totalNodes;
1330 if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too!
1331 ++nodesNeeded;
1332
1333 err = ExtendBTree (btreePtr, nodesNeeded);
1334 M_ExitOnError (err);
1335 }
1336
1337 // no need to delete existing record
1338
1339 err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
1340 recordLen, &nodeRec, index, 1, kInsertRecord, &insertNodeNum);
1341 M_ExitOnError (err);
1342
1343
1344 //////////////////////////////// Success ////////////////////////////////////
1345
1346 Success:
1347 ++btreePtr->writeCount;
1348 ++btreePtr->leafRecords;
1349 M_BTreeHeaderDirty (btreePtr);
1350
1351 // create hint
1352 iterator->hint.writeCount = btreePtr->writeCount;
1353 iterator->hint.nodeNum = insertNodeNum;
1354 iterator->hint.index = 0; // unused
1355 iterator->hint.reserved1 = 0;
1356 iterator->hint.reserved2 = 0;
1357
1358 return noErr;
1359
1360
1361 ////////////////////////////// Error Exit ///////////////////////////////////
1362
1363 ErrorExit:
1364
1365 (void) ReleaseNode (btreePtr, &nodeRec);
1366
1367 iterator->hint.writeCount = 0;
1368 iterator->hint.nodeNum = 0;
1369 iterator->hint.index = 0;
1370 iterator->hint.reserved1 = 0;
1371 iterator->hint.reserved2 = 0;
1372
1373 if (err == fsBTEmptyErr)
1374 err = fsBTRecordNotFoundErr;
1375
1376 return err;
1377 }
1378
1379
1380 //////////////////////////////// BTReplaceRecord ////////////////////////////////
1381
1382 OSStatus BTReplaceRecord (FCB *filePtr,
1383 BTreeIterator *iterator,
1384 FSBufferDescriptor *record,
1385 UInt16 recordLen )
1386 {
1387 OSStatus err;
1388 BTreeControlBlockPtr btreePtr;
1389 TreePathTable treePathTable;
1390 SInt32 nodesNeeded;
1391 BlockDescriptor nodeRec;
1392 UInt32 insertNodeNum;
1393 UInt16 index;
1394 Boolean recordFit;
1395 Boolean validHint;
1396
1397
1398 ////////////////////////// Priliminary Checks ///////////////////////////////
1399
1400 nodeRec.buffer = nil; // so we can call ReleaseNode
1401 nodeRec.blockHeader = nil;
1402
1403 err = CheckInsertParams (filePtr, iterator, record, recordLen);
1404 if (err != noErr)
1405 return err;
1406
1407 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1408
1409 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
1410
1411 ////////////////////////////// Take A Hint //////////////////////////////////
1412
1413 err = IsItAHint (btreePtr, iterator, &validHint);
1414 M_ExitOnError (err);
1415
1416 if (validHint)
1417 {
1418 insertNodeNum = iterator->hint.nodeNum;
1419
1420 err = GetNode (btreePtr, insertNodeNum, &nodeRec);
1421 if( err == noErr )
1422 {
1423 // XXXdbg
1424 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
1425
1426 err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
1427 M_ExitOnError (err);
1428
1429 if (recordFit)
1430 {
1431 err = UpdateNode (btreePtr, &nodeRec, 0, 0);
1432 M_ExitOnError (err);
1433
1434 ++btreePtr->numValidHints;
1435
1436 goto Success;
1437 }
1438 else
1439 {
1440 (void) BTInvalidateHint( iterator );
1441 }
1442
1443 err = ReleaseNode (btreePtr, &nodeRec);
1444 M_ExitOnError (err);
1445 }
1446 else
1447 {
1448 (void) BTInvalidateHint( iterator );
1449 }
1450 }
1451
1452
1453 ////////////////////////////// Get A Clue ///////////////////////////////////
1454
1455 err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
1456 M_ExitOnError (err); // record must exit for Replace
1457
1458 // optimization - if simple replace will work then don't extend btree
1459 // \80\80 if we tried this before, and failed because it wouldn't fit then we shouldn't try this again...
1460
1461 // XXXdbg
1462 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
1463
1464 err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
1465 M_ExitOnError (err);
1466
1467 if (recordFit)
1468 {
1469 err = UpdateNode (btreePtr, &nodeRec, 0, 0);
1470 M_ExitOnError (err);
1471
1472 goto Success;
1473 }
1474
1475
1476 //////////////////////////// Make Some Room /////////////////////////////////
1477
1478 nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);
1479 if (nodesNeeded > 0)
1480 {
1481 nodesNeeded += (SInt32)btreePtr->totalNodes;
1482 if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too!
1483 ++nodesNeeded;
1484
1485 err = ExtendBTree (btreePtr, nodesNeeded);
1486 M_ExitOnError (err);
1487 }
1488
1489 // XXXdbg
1490 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
1491
1492 DeleteRecord (btreePtr, nodeRec.buffer, index); // delete existing key/record
1493
1494 err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
1495 recordLen, &nodeRec, index, 1, kReplaceRecord, &insertNodeNum);
1496 M_ExitOnError (err);
1497
1498 ++btreePtr->writeCount; /* writeCount changes only if the tree structure changed */
1499
1500 Success:
1501 // create hint
1502 iterator->hint.writeCount = btreePtr->writeCount;
1503 iterator->hint.nodeNum = insertNodeNum;
1504 iterator->hint.index = 0; // unused
1505 iterator->hint.reserved1 = 0;
1506 iterator->hint.reserved2 = 0;
1507
1508 return noErr;
1509
1510
1511 ////////////////////////////// Error Exit ///////////////////////////////////
1512
1513 ErrorExit:
1514
1515 (void) ReleaseNode (btreePtr, &nodeRec);
1516
1517 iterator->hint.writeCount = 0;
1518 iterator->hint.nodeNum = 0;
1519 iterator->hint.index = 0;
1520 iterator->hint.reserved1 = 0;
1521 iterator->hint.reserved2 = 0;
1522
1523 return err;
1524 }
1525
1526
1527
1528 //////////////////////////////// BTUpdateRecord ////////////////////////////////
1529
1530 OSStatus
1531 BTUpdateRecord(FCB *filePtr, BTreeIterator *iterator,
1532 IterateCallBackProcPtr callBackProc, void * callBackState)
1533 {
1534 OSStatus err;
1535 BTreeControlBlockPtr btreePtr;
1536 TreePathTable treePathTable;
1537 BlockDescriptor nodeRec;
1538 RecordPtr recordPtr;
1539 BTreeKeyPtr keyPtr;
1540 UInt32 insertNodeNum;
1541 UInt16 recordLen;
1542 UInt16 index;
1543 Boolean validHint;
1544
1545
1546 ////////////////////////// Priliminary Checks ///////////////////////////////
1547
1548 nodeRec.buffer = nil; // so we can call ReleaseNode
1549 nodeRec.blockHeader = nil;
1550
1551 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1552
1553 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
1554
1555 ////////////////////////////// Take A Hint //////////////////////////////////
1556
1557 err = IsItAHint (btreePtr, iterator, &validHint);
1558 M_ExitOnError (err);
1559
1560 if (validHint)
1561 {
1562 insertNodeNum = iterator->hint.nodeNum;
1563
1564 err = GetNode (btreePtr, insertNodeNum, &nodeRec);
1565 if (err == noErr)
1566 {
1567 if (((NodeDescPtr)nodeRec.buffer)->kind == kBTLeafNode &&
1568 SearchNode (btreePtr, nodeRec.buffer, &iterator->key, &index))
1569 {
1570 err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen);
1571 M_ExitOnError (err);
1572
1573 // XXXdbg
1574 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
1575
1576 err = callBackProc(keyPtr, recordPtr, callBackState);
1577 M_ExitOnError (err);
1578
1579 err = UpdateNode (btreePtr, &nodeRec, 0, 0);
1580 M_ExitOnError (err);
1581
1582 ++btreePtr->numValidHints;
1583
1584 goto Success;
1585 }
1586 else
1587 {
1588 (void) BTInvalidateHint( iterator );
1589 }
1590
1591 err = ReleaseNode (btreePtr, &nodeRec);
1592 M_ExitOnError (err);
1593 }
1594 else
1595 {
1596 (void) BTInvalidateHint( iterator );
1597 }
1598 }
1599
1600 ////////////////////////////// Get A Clue ///////////////////////////////////
1601
1602 err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
1603 M_ExitOnError (err);
1604
1605 err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen);
1606 M_ExitOnError (err);
1607
1608 // XXXdbg
1609 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
1610
1611 err = callBackProc(keyPtr, recordPtr, callBackState);
1612 M_ExitOnError (err);
1613
1614 err = UpdateNode (btreePtr, &nodeRec, 0, 0);
1615 M_ExitOnError (err);
1616
1617 Success:
1618 // create hint
1619 iterator->hint.writeCount = btreePtr->writeCount;
1620 iterator->hint.nodeNum = insertNodeNum;
1621 iterator->hint.index = 0;
1622 iterator->hint.reserved1 = 0;
1623 iterator->hint.reserved2 = 0;
1624 return noErr;
1625
1626 ////////////////////////////// Error Exit ///////////////////////////////////
1627
1628 ErrorExit:
1629
1630 (void) ReleaseNode (btreePtr, &nodeRec);
1631
1632 iterator->hint.writeCount = 0;
1633 iterator->hint.nodeNum = 0;
1634 iterator->hint.index = 0;
1635 iterator->hint.reserved1 = 0;
1636 iterator->hint.reserved2 = 0;
1637 return err;
1638 }
1639
1640
1641
1642 //////////////////////////////// BTDeleteRecord /////////////////////////////////
1643
1644 OSStatus BTDeleteRecord (FCB *filePtr,
1645 BTreeIterator *iterator )
1646 {
1647 OSStatus err;
1648 BTreeControlBlockPtr btreePtr;
1649 TreePathTable treePathTable;
1650 BlockDescriptor nodeRec;
1651 SInt32 nodesNeeded;
1652 UInt32 nodeNum;
1653 UInt16 index;
1654
1655
1656 ////////////////////////// Priliminary Checks ///////////////////////////////
1657
1658 nodeRec.buffer = nil; // so we can call ReleaseNode
1659 nodeRec.blockHeader = nil;
1660
1661 M_ReturnErrorIf (filePtr == nil, paramErr);
1662 M_ReturnErrorIf (iterator == nil, paramErr);
1663
1664 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1665 if (btreePtr == nil)
1666 {
1667 err = fsBTInvalidFileErr;
1668 goto ErrorExit;
1669 }
1670
1671 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
1672
1673
1674 /////////////////////////////// Find Key ////////////////////////////////////
1675
1676 //\80\80 check hint for simple delete case (index > 0, numRecords > 2)
1677
1678 err = SearchTree (btreePtr, &iterator->key, treePathTable, &nodeNum, &nodeRec, &index);
1679 M_ExitOnError (err); // record must exit for Delete
1680
1681
1682 /////////////////////// Extend File If Necessary ////////////////////////////
1683
1684 nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);
1685 if ((btreePtr->attributes & kBTVariableIndexKeysMask) && (nodesNeeded > 0))
1686 {
1687 nodesNeeded += (SInt32)btreePtr->totalNodes;
1688 if (nodesNeeded > CalcMapBits (btreePtr))
1689 ++nodesNeeded;
1690
1691 err = ExtendBTree (btreePtr, nodesNeeded);
1692 M_ExitOnError (err);
1693 }
1694
1695 ///////////////////////////// Delete Record /////////////////////////////////
1696
1697 err = DeleteTree (btreePtr, treePathTable, &nodeRec, index, 1);
1698 M_ExitOnError (err);
1699
1700 ++btreePtr->writeCount;
1701 --btreePtr->leafRecords;
1702 M_BTreeHeaderDirty (btreePtr);
1703
1704 iterator->hint.nodeNum = 0;
1705
1706 return noErr;
1707
1708 ////////////////////////////// Error Exit ///////////////////////////////////
1709
1710 ErrorExit:
1711 (void) ReleaseNode (btreePtr, &nodeRec);
1712
1713 return err;
1714 }
1715
1716
1717
1718 OSStatus BTGetInformation (FCB *filePtr,
1719 UInt16 version,
1720 BTreeInfoRec *info )
1721 {
1722 #pragma unused (version)
1723
1724 BTreeControlBlockPtr btreePtr;
1725
1726
1727 M_ReturnErrorIf (filePtr == nil, paramErr);
1728
1729 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1730
1731 /*
1732 * XXX SER
1733 * This should not require the whole tree to be locked, just maybe the BTreeControlBlockPtr
1734 *
1735 * REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
1736 */
1737
1738 M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
1739 M_ReturnErrorIf (info == nil, paramErr);
1740
1741 //\80\80 check version?
1742
1743 info->nodeSize = btreePtr->nodeSize;
1744 info->maxKeyLength = btreePtr->maxKeyLength;
1745 info->treeDepth = btreePtr->treeDepth;
1746 info->numRecords = btreePtr->leafRecords;
1747 info->numNodes = btreePtr->totalNodes;
1748 info->numFreeNodes = btreePtr->freeNodes;
1749 info->lastfsync = btreePtr->lastfsync;
1750 info->keyCompareType = btreePtr->keyCompareType;
1751 return noErr;
1752 }
1753
1754 // XXXdbg
1755 __private_extern__
1756 OSStatus
1757 BTIsDirty(FCB *filePtr)
1758 {
1759 BTreeControlBlockPtr btreePtr;
1760
1761 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1762 return TreeIsDirty(btreePtr);
1763 }
1764
1765 /*-------------------------------------------------------------------------------
1766 Routine: BTFlushPath - Flush BTreeControlBlock to Header Node.
1767
1768 Function: Brief_description_of_the_function_and_any_side_effects
1769
1770
1771 Input: pathPtr - pointer to path control block for B*Tree file to flush
1772
1773 Output: none
1774
1775 Result: noErr - success
1776 != noErr - failure
1777 -------------------------------------------------------------------------------*/
1778
1779 OSStatus BTFlushPath (FCB *filePtr)
1780 {
1781 OSStatus err;
1782 BTreeControlBlockPtr btreePtr;
1783
1784
1785 M_ReturnErrorIf (filePtr == nil, paramErr);
1786
1787 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1788
1789 M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
1790
1791 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
1792
1793 err = UpdateHeader (btreePtr, false);
1794
1795 return err;
1796 }
1797
1798
1799 /*-------------------------------------------------------------------------------
1800 Routine: BTReload - Reload B-tree Header Data.
1801
1802 Function: Reload B-tree header data from disk. This is called after fsck
1803 has made repairs to the root filesystem. The filesystem is
1804 mounted read-only when BTReload is caled.
1805
1806
1807 Input: filePtr - the B*Tree file that needs its header updated
1808
1809 Output: none
1810
1811 Result: noErr - success
1812 != noErr - failure
1813 -------------------------------------------------------------------------------*/
1814
1815 OSStatus
1816 BTReloadData(FCB *filePtr)
1817 {
1818 OSStatus err;
1819 BTreeControlBlockPtr btreePtr;
1820 BlockDescriptor node;
1821 BTHeaderRec *header;
1822
1823
1824 node.buffer = nil;
1825 node.blockHeader = nil;
1826
1827 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1828 if (btreePtr == nil)
1829 return (fsBTInvalidFileErr);
1830
1831 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
1832
1833 err = GetNode(btreePtr, kHeaderNodeNum, &node);
1834 if (err != noErr)
1835 return (err);
1836
1837 header = (BTHeaderRec*)((char *)node.buffer + sizeof(BTNodeDescriptor));
1838 if ((err = VerifyHeader (filePtr, header)) == 0) {
1839 btreePtr->treeDepth = header->treeDepth;
1840 btreePtr->rootNode = header->rootNode;
1841 btreePtr->leafRecords = header->leafRecords;
1842 btreePtr->firstLeafNode = header->firstLeafNode;
1843 btreePtr->lastLeafNode = header->lastLeafNode;
1844 btreePtr->maxKeyLength = header->maxKeyLength;
1845 btreePtr->totalNodes = header->totalNodes;
1846 btreePtr->freeNodes = header->freeNodes;
1847 btreePtr->btreeType = header->btreeType;
1848
1849 btreePtr->flags &= (~kBTHeaderDirty);
1850 }
1851
1852 (void) ReleaseNode(btreePtr, &node);
1853
1854 return err;
1855 }
1856
1857
1858 /*-------------------------------------------------------------------------------
1859 Routine: BTInvalidateHint - Invalidates the hint within a BTreeInterator.
1860
1861 Function: Invalidates the hint within a BTreeInterator.
1862
1863
1864 Input: iterator - pointer to BTreeIterator
1865
1866 Output: iterator - iterator with the hint.nodeNum cleared
1867
1868 Result: noErr - success
1869 paramErr - iterator == nil
1870 -------------------------------------------------------------------------------*/
1871
1872
1873 OSStatus BTInvalidateHint (BTreeIterator *iterator )
1874 {
1875 if (iterator == nil)
1876 return paramErr;
1877
1878 iterator->hint.nodeNum = 0;
1879
1880 return noErr;
1881 }
1882
1883
1884
1885
1886 /*-------------------------------------------------------------------------------
1887 Routine: BTGetLastSync
1888
1889 Function: Returns the last time that this btree was flushed, does not include header.
1890
1891 Input: filePtr - pointer file control block
1892
1893 Output: lastfsync - time in seconds of last update
1894
1895 Result: noErr - success
1896 paramErr - iterator == nil
1897 -------------------------------------------------------------------------------*/
1898
1899
1900 OSStatus BTGetLastSync (FCB *filePtr,
1901 UInt32 *lastsync)
1902 {
1903 BTreeControlBlockPtr btreePtr;
1904
1905
1906 M_ReturnErrorIf (filePtr == nil, paramErr);
1907
1908 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1909
1910 /* Maybe instead of requiring a lock..an atomic set might be more appropriate */
1911 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
1912
1913 M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
1914 M_ReturnErrorIf (lastsync == nil, paramErr);
1915
1916 *lastsync = btreePtr->lastfsync;
1917
1918 return noErr;
1919 }
1920
1921
1922
1923
1924 /*-------------------------------------------------------------------------------
1925 Routine: BTSetLastSync
1926
1927 Function: Sets the last time that this btree was flushed, does not include header.
1928
1929
1930 Input: fcb - pointer file control block
1931
1932 Output: lastfsync - time in seconds of last update
1933
1934 Result: noErr - success
1935 paramErr - iterator == nil
1936 -------------------------------------------------------------------------------*/
1937
1938
1939 OSStatus BTSetLastSync (FCB *filePtr,
1940 UInt32 lastsync)
1941 {
1942 BTreeControlBlockPtr btreePtr;
1943
1944
1945 M_ReturnErrorIf (filePtr == nil, paramErr);
1946
1947 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1948
1949 /* Maybe instead of requiring a lock..an atomic set might be more appropriate */
1950 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
1951
1952 M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
1953 M_ReturnErrorIf (lastsync == nil, paramErr);
1954
1955 btreePtr->lastfsync = lastsync;
1956
1957 return noErr;
1958 }
1959
1960
1961 __private_extern__
1962 OSStatus BTHasContiguousNodes (FCB *filePtr)
1963 {
1964 BTreeControlBlockPtr btreePtr;
1965
1966
1967 M_ReturnErrorIf (filePtr == nil, paramErr);
1968
1969 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1970
1971 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
1972
1973 M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
1974
1975 return NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize);
1976 }
1977
1978
1979 /*-------------------------------------------------------------------------------
1980 Routine: BTGetUserData
1981
1982 Function: Read the user data area of the b-tree header node.
1983
1984 -------------------------------------------------------------------------------*/
1985 __private_extern__
1986 OSStatus
1987 BTGetUserData(FCB *filePtr, void * dataPtr, int dataSize)
1988 {
1989 BTreeControlBlockPtr btreePtr;
1990 BlockDescriptor node;
1991 char * offset;
1992 OSStatus err;
1993
1994 if (dataSize > kBTreeHeaderUserBytes)
1995 return (EINVAL);
1996 node.buffer = nil;
1997 node.blockHeader = nil;
1998
1999 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
2000 if (btreePtr == nil)
2001 return (fsBTInvalidFileErr);
2002
2003 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
2004
2005 err = GetNode(btreePtr, kHeaderNodeNum, &node);
2006 if (err)
2007 return (err);
2008
2009 offset = (char *)node.buffer + sizeof(BTNodeDescriptor) + sizeof(BTHeaderRec);
2010 bcopy(offset, dataPtr, dataSize);
2011
2012 (void) ReleaseNode(btreePtr, &node);
2013
2014 return (0);
2015 }
2016
2017
2018 /*-------------------------------------------------------------------------------
2019 Routine: BTSetUserData
2020
2021 Function: Write the user data area of the b-tree header node.
2022 -------------------------------------------------------------------------------*/
2023 __private_extern__
2024 OSStatus
2025 BTSetUserData(FCB *filePtr, void * dataPtr, int dataSize)
2026 {
2027 BTreeControlBlockPtr btreePtr;
2028 BlockDescriptor node;
2029 char * offset;
2030 OSStatus err;
2031
2032 if (dataSize > kBTreeHeaderUserBytes)
2033 return (EINVAL);
2034 node.buffer = nil;
2035 node.blockHeader = nil;
2036
2037 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
2038 if (btreePtr == nil)
2039 return (fsBTInvalidFileErr);
2040
2041 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
2042
2043 err = GetNode(btreePtr, kHeaderNodeNum, &node);
2044 if (err)
2045 return (err);
2046
2047 ModifyBlockStart(btreePtr->fileRefNum, &node);
2048
2049 offset = (char *)node.buffer + sizeof(BTNodeDescriptor) + sizeof(BTHeaderRec);
2050 bcopy(dataPtr, offset, dataSize);
2051
2052 err = UpdateNode (btreePtr, &node, 0, 0);
2053
2054 return (err);
2055 }
2056
mirror of XNU