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


557cd19cf299c405d64b099163b57da1c6c1b8c3
[apple/xnu.git] / bsd / hfs / hfscommon / BTree / BTreeAllocate.c
1 /*
2 * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved.
7 *
8 * This file contains Original Code and/or Modifications of Original Code
9 * as defined in and that are subject to the Apple Public Source License
10 * Version 2.0 (the 'License'). You may not use this file except in
11 * compliance with the License. Please obtain a copy of the License at
12 * http://www.opensource.apple.com/apsl/ and read it before using this
13 * file.
14 *
15 * The Original Code and all software distributed under the License are
16 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
17 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
18 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
20 * Please see the License for the specific language governing rights and
21 * limitations under the License.
22 *
23 * @APPLE_LICENSE_HEADER_END@
24 */
25 /*
26 File: BTreeAllocate.c
27
28 Contains: BTree Node Allocation routines for the BTree Module.
29
30 Version: xxx put the technology version here xxx
31
32 Written by: Gordon Sheridan and Bill Bruffey
33
34 Copyright: © 1992-1999 by Apple Computer, Inc., all rights reserved.
35
36 File Ownership:
37
38 DRI: Don Brady
39
40 Other Contact: Mark Day
41
42 Technology: File Systems
43
44 Writers:
45
46 (djb) Don Brady
47 (ser) Scott Roberts
48 (msd) Mark Day
49
50 Change History (most recent first):
51
52 <MOSXS> 6/1/99 djb Sync up with Mac OS 8.6.
53 <CS3> 11/24/97 djb Remove some debug code (Panic calls).
54 <CS2> 7/24/97 djb CallbackProcs now take refnum instead of an FCB.
55 <CS1> 4/23/97 djb first checked in
56
57 <HFS2> 2/19/97 djb Change E_BadNodeType to fsBTBadNodeType.
58 <HFS1> 12/19/96 djb first checked in
59
60 History applicable to original Scarecrow Design:
61
62 <4> 10/25/96 ser Changing for new VFPI
63 <3> 10/18/96 ser Converting over VFPI changes
64 <2> 1/10/96 msd Change 64-bit math to use real function names from Math64.i.
65 <1> 10/18/95 rst Moved from Scarecrow project.
66
67 <8> 1/12/95 wjk Adopt Model FileSystem changes in D5.
68 <7> 9/30/94 prp Get in sync with D2 interface changes.
69 <6> 7/22/94 wjk Convert to the new set of header files.
70 <5> 8/31/93 prp Use U64SetU instead of S64Set.
71 <4> 5/21/93 gs Fix ExtendBTree bug.
72 <3> 5/10/93 gs Fix pointer arithmetic bug in AllocateNode.
73 <2> 3/23/93 gs finish ExtendBTree routine.
74 <1> 2/8/93 gs first checked in
75 <0> 1/1/93 gs begin AllocateNode and FreeNode
76
77 */
78
79 #include "../../hfs_endian.h"
80 #include "../headers/BTreesPrivate.h"
81
82 ///////////////////// Routines Internal To BTreeAllocate.c //////////////////////
83
84 OSStatus GetMapNode (BTreeControlBlockPtr btreePtr,
85 BlockDescriptor *nodePtr,
86 UInt16 **mapPtr,
87 UInt16 *mapSize );
88
89 /////////////////////////////////////////////////////////////////////////////////
90
91 /*-------------------------------------------------------------------------------
92
93 Routine: AllocateNode - Find Free Node, Mark It Used, and Return Node Number.
94
95 Function: Searches the map records for the first free node, marks it "in use" and
96 returns the node number found. This routine should really only be called
97 when we know there are free blocks, otherwise it's just a waste of time.
98
99 Note: We have to examine map nodes a word at a time rather than a long word
100 because the External BTree Mgr used map records that were not an integral
101 number of long words. Too bad. In our spare time could develop a more
102 sophisticated algorithm that read map records by long words (and long
103 word aligned) and handled the spare bytes at the beginning and end
104 appropriately.
105
106 Input: btreePtr - pointer to control block for BTree file
107
108 Output: nodeNum - number of node allocated
109
110
111 Result: noErr - success
112 fsBTNoMoreMapNodesErr - no free blocks were found
113 != noErr - failure
114 -------------------------------------------------------------------------------*/
115
116 OSStatus AllocateNode (BTreeControlBlockPtr btreePtr, UInt32 *nodeNum)
117 {
118 OSStatus err;
119 BlockDescriptor node;
120 UInt16 *mapPtr, *pos;
121 UInt16 mapSize, size;
122 UInt16 freeWord;
123 UInt16 mask;
124 UInt16 bitOffset;
125 UInt32 nodeNumber;
126
127
128 nodeNumber = 0; // first node number of header map record
129 node.buffer = nil; // clear node.buffer to get header node
130 // - and for ErrorExit
131 node.blockHeader = nil;
132
133 while (true)
134 {
135 err = GetMapNode (btreePtr, &node, &mapPtr, &mapSize);
136 M_ExitOnError (err);
137
138 // XXXdbg
139 ModifyBlockStart(btreePtr->fileRefNum, &node);
140
141 //////////////////////// Find Word with Free Bit ////////////////////////////
142
143 pos = mapPtr;
144 size = mapSize;
145 size >>= 1; // convert to number of words
146 //\80\80 assumes mapRecords contain an integral number of words
147
148 while ( size-- )
149 {
150 if ( *pos++ != 0xFFFF ) // assume test fails, and increment pos
151 break;
152 }
153
154 --pos; // whoa! backup
155
156 if (*pos != 0xFFFF) // hey, we got one!
157 break;
158
159 nodeNumber += mapSize << 3; // covert to number of bits (nodes)
160 }
161
162 ///////////////////////// Find Free Bit in Word /////////////////////////////
163
164 freeWord = SWAP_BE16 (*pos);
165 bitOffset = 15;
166 mask = 0x8000;
167
168 do {
169 if ( (freeWord & mask) == 0)
170 break;
171 mask >>= 1;
172 } while (--bitOffset);
173
174 ////////////////////// Calculate Free Node Number ///////////////////////////
175
176 nodeNumber += ((pos - mapPtr) << 4) + (15 - bitOffset); // (pos-mapPtr) = # of words!
177
178
179 ///////////////////////// Check for End of Map //////////////////////////////
180
181 if (nodeNumber >= btreePtr->totalNodes)
182 {
183 err = fsBTFullErr;
184 goto ErrorExit;
185 }
186
187 /////////////////////////// Allocate the Node ///////////////////////////////
188
189 *pos |= SWAP_BE16 (mask); // set the map bit for the node
190
191 err = UpdateNode (btreePtr, &node, 0, kLockTransaction);
192 M_ExitOnError (err);
193
194 --btreePtr->freeNodes;
195 btreePtr->flags |= kBTHeaderDirty;
196 *nodeNum = nodeNumber;
197
198 return noErr;
199
200 ////////////////////////////////// Error Exit ///////////////////////////////////
201
202 ErrorExit:
203
204 (void) ReleaseNode (btreePtr, &node);
205 *nodeNum = 0;
206
207 return err;
208 }
209
210
211
212 /*-------------------------------------------------------------------------------
213
214 Routine: FreeNode - Clear allocation bit for node.
215
216 Function: Finds the bit representing the node specified by nodeNum in the node
217 map and clears the bit.
218
219
220 Input: btreePtr - pointer to control block for BTree file
221 nodeNum - number of node to mark free
222
223 Output: none
224
225 Result: noErr - success
226 fsBTNoMoreMapNodesErr - node number is beyond end of node map
227 != noErr - GetNode or ReleaseNode encountered some difficulty
228 -------------------------------------------------------------------------------*/
229
230 OSStatus FreeNode (BTreeControlBlockPtr btreePtr, UInt32 nodeNum)
231 {
232 OSStatus err;
233 BlockDescriptor node;
234 UInt32 nodeIndex;
235 UInt16 mapSize;
236 UInt16 *mapPos;
237 UInt16 bitOffset;
238
239
240 //////////////////////////// Find Map Record ////////////////////////////////
241 nodeIndex = 0; // first node number of header map record
242 node.buffer = nil; // invalidate node.buffer to get header node
243 node.blockHeader = nil;
244
245 while (nodeNum >= nodeIndex)
246 {
247 err = GetMapNode (btreePtr, &node, &mapPos, &mapSize);
248 M_ExitOnError (err);
249
250 nodeIndex += mapSize << 3; // covert to number of bits (nodes)
251 }
252
253 //////////////////////////// Mark Node Free /////////////////////////////////
254
255 // XXXdbg
256 ModifyBlockStart(btreePtr->fileRefNum, &node);
257
258 nodeNum -= (nodeIndex - (mapSize << 3)); // relative to this map record
259 bitOffset = 15 - (nodeNum & 0x0000000F); // last 4 bits are bit offset
260 mapPos += nodeNum >> 4; // point to word containing map bit
261
262 M_SWAP_BE16_ClearBitNum (*mapPos, bitOffset); // clear it
263
264 err = UpdateNode (btreePtr, &node, 0, kLockTransaction);
265 M_ExitOnError (err);
266
267 ++btreePtr->freeNodes;
268 btreePtr->flags |= kBTHeaderDirty; // how about a macro for this
269
270 return noErr;
271
272 ErrorExit:
273
274 (void) ReleaseNode (btreePtr, &node);
275
276 return err;
277 }
278
279
280
281 /*-------------------------------------------------------------------------------
282
283 Routine: ExtendBTree - Call FSAgent to extend file, and allocate necessary map nodes.
284
285 Function: This routine calls the the FSAgent to extend the end of fork, if necessary,
286 to accomodate the number of nodes requested. It then allocates as many
287 map nodes as are necessary to account for all the nodes in the B*Tree.
288 If newTotalNodes is less than the current number of nodes, no action is
289 taken.
290
291 Note: Internal HFS File Manager BTree Module counts on an integral number of
292 long words in map records, although they are not long word aligned.
293
294 Input: btreePtr - pointer to control block for BTree file
295 newTotalNodes - total number of nodes the B*Tree is to extended to
296
297 Output: none
298
299 Result: noErr - success
300 != noErr - failure
301 -------------------------------------------------------------------------------*/
302
303 OSStatus ExtendBTree (BTreeControlBlockPtr btreePtr,
304 UInt32 newTotalNodes )
305 {
306 OSStatus err;
307 FCB *filePtr;
308 FSSize minEOF, maxEOF;
309 UInt16 nodeSize;
310 UInt32 oldTotalNodes;
311 UInt32 newMapNodes;
312 UInt32 mapBits, totalMapBits;
313 UInt32 recStartBit;
314 UInt32 nodeNum, nextNodeNum;
315 UInt32 firstNewMapNodeNum, lastNewMapNodeNum;
316 BlockDescriptor mapNode, newNode;
317 UInt16 *mapPos;
318 UInt16 *mapStart;
319 UInt16 mapSize;
320 UInt16 mapNodeRecSize;
321 UInt32 bitInWord, bitInRecord;
322 UInt16 mapIndex;
323
324
325 oldTotalNodes = btreePtr->totalNodes;
326 if (newTotalNodes <= oldTotalNodes) // we're done!
327 return noErr;
328
329 nodeSize = btreePtr->nodeSize;
330 filePtr = GetFileControlBlock(btreePtr->fileRefNum);
331
332 mapNode.buffer = nil;
333 mapNode.blockHeader = nil;
334 newNode.buffer = nil;
335 newNode.blockHeader = nil;
336
337 mapNodeRecSize = nodeSize - sizeof(BTNodeDescriptor) - 6; // 2 bytes of free space (see note)
338
339
340 //////////////////////// Count Bits In Node Map /////////////////////////////
341
342 totalMapBits = 0;
343 do {
344 err = GetMapNode (btreePtr, &mapNode, &mapStart, &mapSize);
345 M_ExitOnError (err);
346
347 mapBits = mapSize << 3; // mapSize (in bytes) * 8
348 recStartBit = totalMapBits; // bit number of first bit in map record
349 totalMapBits += mapBits;
350
351 } while ( ((BTNodeDescriptor*)mapNode.buffer)->fLink != 0 );
352
353 if (DEBUG_BUILD && totalMapBits != CalcMapBits (btreePtr))
354 Panic ("\pExtendBTree: totalMapBits != CalcMapBits");
355
356 /////////////////////// Extend LEOF If Necessary ////////////////////////////
357
358 minEOF = (UInt64)newTotalNodes * (UInt64)nodeSize;
359 if ( filePtr->fcbEOF < minEOF )
360 {
361 maxEOF = (UInt64)0x7fffffffLL * (UInt64)nodeSize;
362
363 err = btreePtr->setEndOfForkProc (btreePtr->fileRefNum, minEOF, maxEOF);
364 M_ExitOnError (err);
365 }
366
367
368 //////////////////// Calc New Total Number Of Nodes /////////////////////////
369
370 newTotalNodes = filePtr->fcbEOF / nodeSize; // hack!
371 // do we wish to perform any verification of newTotalNodes at this point?
372
373 btreePtr->totalNodes = newTotalNodes; // do we need to update freeNodes here too?
374
375
376 ////////////// Calculate Number Of New Map Nodes Required ///////////////////
377
378 newMapNodes = 0;
379 if (newTotalNodes > totalMapBits)
380 {
381 newMapNodes = (((newTotalNodes - totalMapBits) >> 3) / mapNodeRecSize) + 1;
382 firstNewMapNodeNum = oldTotalNodes;
383 lastNewMapNodeNum = firstNewMapNodeNum + newMapNodes - 1;
384 }
385 else
386 {
387 err = ReleaseNode (btreePtr, &mapNode);
388 M_ExitOnError (err);
389
390 goto Success;
391 }
392
393
394 /////////////////////// Initialize New Map Nodes ////////////////////////////
395 // XXXdbg - this is the correct place for this:
396 ModifyBlockStart(btreePtr->fileRefNum, &mapNode);
397
398 ((BTNodeDescriptor*)mapNode.buffer)->fLink = firstNewMapNodeNum;
399
400 nodeNum = firstNewMapNodeNum;
401 while (true)
402 {
403 err = GetNewNode (btreePtr, nodeNum, &newNode);
404 M_ExitOnError (err);
405
406 // XXXdbg
407 ModifyBlockStart(btreePtr->fileRefNum, &newNode);
408
409 ((NodeDescPtr)newNode.buffer)->numRecords = 1;
410 ((NodeDescPtr)newNode.buffer)->kind = kBTMapNode;
411
412 // set free space offset
413 *(UInt16 *)((Ptr)newNode.buffer + nodeSize - 4) = nodeSize - 6;
414
415 if (nodeNum++ == lastNewMapNodeNum)
416 break;
417
418 ((BTNodeDescriptor*)newNode.buffer)->fLink = nodeNum; // point to next map node
419
420 err = UpdateNode (btreePtr, &newNode, 0, kLockTransaction);
421 M_ExitOnError (err);
422 }
423
424 err = UpdateNode (btreePtr, &newNode, 0, kLockTransaction);
425 M_ExitOnError (err);
426
427
428 ///////////////////// Mark New Map Nodes Allocated //////////////////////////
429
430 nodeNum = firstNewMapNodeNum;
431 do {
432 bitInRecord = nodeNum - recStartBit;
433
434 while (bitInRecord >= mapBits)
435 {
436 nextNodeNum = ((NodeDescPtr)mapNode.buffer)->fLink;
437 if ( nextNodeNum == 0)
438 {
439 err = fsBTNoMoreMapNodesErr;
440 goto ErrorExit;
441 }
442
443 err = UpdateNode (btreePtr, &mapNode, 0, kLockTransaction);
444 M_ExitOnError (err);
445
446 err = GetNode (btreePtr, nextNodeNum, &mapNode);
447 M_ExitOnError (err);
448
449 // XXXdbg
450 ModifyBlockStart(btreePtr->fileRefNum, &mapNode);
451
452 mapIndex = 0;
453
454 mapStart = (UInt16 *) GetRecordAddress (btreePtr, mapNode.buffer, mapIndex);
455 mapSize = GetRecordSize (btreePtr, mapNode.buffer, mapIndex);
456
457 if (DEBUG_BUILD && mapSize != M_MapRecordSize (btreePtr->nodeSize) )
458 {
459 Panic ("\pExtendBTree: mapSize != M_MapRecordSize");
460 }
461
462 mapBits = mapSize << 3; // mapSize (in bytes) * 8
463 recStartBit = totalMapBits; // bit number of first bit in map record
464 totalMapBits += mapBits;
465
466 bitInRecord = nodeNum - recStartBit;
467 }
468
469 mapPos = mapStart + ((nodeNum - recStartBit) >> 4);
470 bitInWord = 15 - ((nodeNum - recStartBit) & 0x0000000F);
471
472 M_SWAP_BE16_SetBitNum (*mapPos, bitInWord);
473
474 ++nodeNum;
475
476 } while (nodeNum <= lastNewMapNodeNum);
477
478 err = UpdateNode (btreePtr, &mapNode, 0, kLockTransaction);
479 M_ExitOnError (err);
480
481
482 //////////////////////////////// Success ////////////////////////////////////
483
484 Success:
485
486 btreePtr->totalNodes = newTotalNodes;
487 btreePtr->freeNodes += (newTotalNodes - oldTotalNodes) - newMapNodes;
488
489 btreePtr->flags |= kBTHeaderDirty; //\80\80 how about a macro for this
490
491 /* Force the b-tree header changes to disk */
492 (void) UpdateHeader (btreePtr, true);
493
494 return noErr;
495
496
497 ////////////////////////////// Error Exit ///////////////////////////////////
498
499 ErrorExit:
500
501 (void) ReleaseNode (btreePtr, &mapNode);
502 (void) ReleaseNode (btreePtr, &newNode);
503
504 return err;
505 }
506
507
508
509 /*-------------------------------------------------------------------------------
510
511 Routine: GetMapNode - Get the next map node and pointer to the map record.
512
513 Function: Given a BlockDescriptor to a map node in nodePtr, GetMapNode releases
514 it and gets the next node. If nodePtr->buffer is nil, then the header
515 node is retrieved.
516
517
518 Input: btreePtr - pointer to control block for BTree file
519 nodePtr - pointer to a BlockDescriptor of a map node
520
521 Output: nodePtr - pointer to the BlockDescriptor for the next map node
522 mapPtr - pointer to the map record within the map node
523 mapSize - number of bytes in the map record
524
525 Result: noErr - success
526 fsBTNoMoreMapNodesErr - we've run out of map nodes
527 fsBTInvalidNodeErr - bad node, or not node type kMapNode
528 != noErr - failure
529 -------------------------------------------------------------------------------*/
530
531 OSStatus GetMapNode (BTreeControlBlockPtr btreePtr,
532 BlockDescriptor *nodePtr,
533 UInt16 **mapPtr,
534 UInt16 *mapSize )
535 {
536 OSStatus err;
537 UInt16 mapIndex;
538 UInt32 nextNodeNum;
539
540 if (nodePtr->buffer != nil) // if iterator is valid...
541 {
542 nextNodeNum = ((NodeDescPtr)nodePtr->buffer)->fLink;
543 if (nextNodeNum == 0)
544 {
545 err = fsBTNoMoreMapNodesErr;
546 goto ErrorExit;
547 }
548
549 err = ReleaseNode (btreePtr, nodePtr);
550 M_ExitOnError (err);
551
552 err = GetNode (btreePtr, nextNodeNum, nodePtr);
553 M_ExitOnError (err);
554
555 if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTMapNode)
556 {
557 err = fsBTBadNodeType;
558 goto ErrorExit;
559 }
560
561 ++btreePtr->numMapNodesRead;
562 mapIndex = 0;
563 } else {
564 err = GetNode (btreePtr, kHeaderNodeNum, nodePtr);
565 M_ExitOnError (err);
566
567 if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTHeaderNode)
568 {
569 err = fsBTInvalidHeaderErr; //\80\80 or fsBTBadNodeType
570 goto ErrorExit;
571 }
572
573 mapIndex = 2;
574 }
575
576
577 *mapPtr = (UInt16 *) GetRecordAddress (btreePtr, nodePtr->buffer, mapIndex);
578 *mapSize = GetRecordSize (btreePtr, nodePtr->buffer, mapIndex);
579
580 return noErr;
581
582
583 ErrorExit:
584
585 (void) ReleaseNode (btreePtr, nodePtr);
586
587 *mapPtr = nil;
588 *mapSize = 0;
589
590 return err;
591 }
592
593
594
595 ////////////////////////////////// CalcMapBits //////////////////////////////////
596
597 UInt32 CalcMapBits (BTreeControlBlockPtr btreePtr)
598 {
599 UInt32 mapBits;
600
601 mapBits = M_HeaderMapRecordSize (btreePtr->nodeSize) << 3;
602
603 while (mapBits < btreePtr->totalNodes)
604 mapBits += M_MapRecordSize (btreePtr->nodeSize) << 3;
605
606 return mapBits;
607 }
mirror of XNU