2
* Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
4
* @APPLE_LICENSE_HEADER_START@
6
* "Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7
* Reserved. This file contains Original Code and/or Modifications of
8
* Original Code as defined in and that are subject to the Apple Public
9
* Source License Version 1.0 (the 'License'). You may not use this file
10
* except in compliance with the License. Please obtain a copy of the
11
* License at http://www.apple.com/publicsource and read it before using
14
* The Original Code and all software distributed under the License are
15
* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18
* FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19
* License for the specific language governing rights and limitations
22
* @APPLE_LICENSE_HEADER_END@
27
Contains: BTree Node Allocation routines for the BTree Module.
29
Version: xxx put the technology version here xxx
31
Written by: Gordon Sheridan and Bill Bruffey
33
Copyright: � 1992-1999 by Apple Computer, Inc., all rights reserved.
36
#include "BTreePrivate.h"
37
#include "hfs_endian.h"
39
///////////////////// Routines Internal To BTreeAllocate.c //////////////////////
41
OSStatus GetMapNode (BTreeControlBlockPtr btreePtr,
42
BlockDescriptor *nodePtr,
46
/////////////////////////////////////////////////////////////////////////////////
48
/*-------------------------------------------------------------------------------
50
Routine: AllocateNode - Find Free Node, Mark It Used, and Return Node Number.
52
Function: Searches the map records for the first free node, marks it "in use" and
53
returns the node number found. This routine should really only be called
54
when we know there are free blocks, otherwise it's just a waste of time.
56
Note: We have to examine map nodes a word at a time rather than a long word
57
because the External BTree Mgr used map records that were not an integral
58
number of long words. Too bad. In our spare time could develop a more
59
sophisticated algorithm that read map records by long words (and long
60
word aligned) and handled the spare bytes at the beginning and end
63
Input: btreePtr - pointer to control block for BTree file
65
Output: nodeNum - number of node allocated
68
Result: noErr - success
69
fsBTNoMoreMapNodesErr - no free blocks were found
71
-------------------------------------------------------------------------------*/
73
OSStatus AllocateNode (BTreeControlBlockPtr btreePtr, UInt32 *nodeNum)
85
nodeNumber = 0; // first node number of header map record
86
node.buffer = nil; // clear node.buffer to get header node
87
// - and for ErrorExit
91
err = GetMapNode (btreePtr, &node, &mapPtr, &mapSize);
94
//////////////////////// Find Word with Free Bit ////////////////////////////
98
size >>= 1; // convert to number of words
99
//�� assumes mapRecords contain an integral number of words
103
if ( *pos++ != 0xFFFF ) // assume test fails, and increment pos
107
--pos; // whoa! backup
109
if (*pos != 0xFFFF) // hey, we got one!
112
nodeNumber += mapSize << 3; // covert to number of bits (nodes)
115
///////////////////////// Find Free Bit in Word /////////////////////////////
117
freeWord = SWAP_BE16 (*pos);
122
if ( (freeWord & mask) == 0)
125
} while (--bitOffset);
127
////////////////////// Calculate Free Node Number ///////////////////////////
129
nodeNumber += ((pos - mapPtr) << 4) + (15 - bitOffset); // (pos-mapPtr) = # of words!
132
///////////////////////// Check for End of Map //////////////////////////////
134
if (nodeNumber >= btreePtr->totalNodes)
140
/////////////////////////// Allocate the Node ///////////////////////////////
142
*pos |= SWAP_BE16 (mask); // set the map bit for the node
144
err = UpdateNode (btreePtr, &node);
147
--btreePtr->freeNodes;
148
btreePtr->flags |= kBTHeaderDirty;
149
*nodeNum = nodeNumber;
153
////////////////////////////////// Error Exit ///////////////////////////////////
157
(void) ReleaseNode (btreePtr, &node);
165
/*-------------------------------------------------------------------------------
167
Routine: FreeNode - Clear allocation bit for node.
169
Function: Finds the bit representing the node specified by nodeNum in the node
170
map and clears the bit.
173
Input: btreePtr - pointer to control block for BTree file
174
nodeNum - number of node to mark free
178
Result: noErr - success
179
fsBTNoMoreMapNodesErr - node number is beyond end of node map
180
!= noErr - GetNode or ReleaseNode encountered some difficulty
181
-------------------------------------------------------------------------------*/
183
OSStatus FreeNode (BTreeControlBlockPtr btreePtr, UInt32 nodeNum)
186
BlockDescriptor node;
193
//////////////////////////// Find Map Record ////////////////////////////////
194
nodeIndex = 0; // first node number of header map record
195
node.buffer = nil; // invalidate node.buffer to get header node
197
while (nodeNum >= nodeIndex)
199
err = GetMapNode (btreePtr, &node, &mapPos, &mapSize);
202
nodeIndex += mapSize << 3; // covert to number of bits (nodes)
205
//////////////////////////// Mark Node Free /////////////////////////////////
207
nodeNum -= (nodeIndex - (mapSize << 3)); // relative to this map record
208
bitOffset = 15 - (nodeNum & 0x0000000F); // last 4 bits are bit offset
209
mapPos += nodeNum >> 4; // point to word containing map bit
210
M_SWAP_BE16_ClearBitNum (*mapPos, bitOffset); // clear it
212
err = UpdateNode (btreePtr, &node);
216
++btreePtr->freeNodes;
217
btreePtr->flags |= kBTHeaderDirty; //�� how about a macro for this
223
(void) ReleaseNode (btreePtr, &node);
230
/*-------------------------------------------------------------------------------
232
Routine: ExtendBTree - Call FSAgent to extend file, and allocate necessary map nodes.
234
Function: This routine calls the the FSAgent to extend the end of fork, if necessary,
235
to accomodate the number of nodes requested. It then allocates as many
236
map nodes as are necessary to account for all the nodes in the B*Tree.
237
If newTotalNodes is less than the current number of nodes, no action is
240
Note: Internal HFS File Manager BTree Module counts on an integral number of
241
long words in map records, although they are not long word aligned.
243
Input: btreePtr - pointer to control block for BTree file
244
newTotalNodes - total number of nodes the B*Tree is to extended to
248
Result: noErr - success
250
-------------------------------------------------------------------------------*/
252
OSStatus ExtendBTree (BTreeControlBlockPtr btreePtr,
253
UInt32 newTotalNodes )
257
FSSize minEOF, maxEOF;
259
UInt32 oldTotalNodes;
261
UInt32 mapBits, totalMapBits;
263
UInt32 nodeNum, nextNodeNum;
264
UInt32 firstNewMapNodeNum, lastNewMapNodeNum;
265
BlockDescriptor mapNode, newNode;
269
UInt16 mapNodeRecSize;
270
UInt32 bitInWord, bitInRecord;
274
oldTotalNodes = btreePtr->totalNodes;
275
if (newTotalNodes <= oldTotalNodes) // we're done!
278
nodeSize = btreePtr->nodeSize;
279
filePtr = btreePtr->fcbPtr;
281
mapNode.buffer = nil;
282
newNode.buffer = nil;
284
mapNodeRecSize = nodeSize - sizeof(BTNodeDescriptor) - 6; // 2 bytes of free space (see note)
286
//�� update for proper 64 bit arithmetic!!
289
//////////////////////// Count Bits In Node Map /////////////////////////////
293
err = GetMapNode (btreePtr, &mapNode, &mapStart, &mapSize);
296
mapBits = mapSize << 3; // mapSize (in bytes) * 8
297
recStartBit = totalMapBits; // bit number of first bit in map record
298
totalMapBits += mapBits;
300
} while ( ((BTNodeDescriptor*)mapNode.buffer)->fLink != 0 );
302
if (DEBUG_BUILD && totalMapBits != CalcMapBits (btreePtr))
303
Panic ("\pExtendBTree: totalMapBits != CalcMapBits");
305
/////////////////////// Extend LEOF If Necessary ////////////////////////////
307
minEOF = (UInt64)newTotalNodes * (UInt64)nodeSize;
308
if ( filePtr->fcbLogicalSize < minEOF )
310
maxEOF = 0xFFFFFFFFFFFFFFFFULL;
312
err = btreePtr->setEndOfForkProc (btreePtr->fcbPtr, minEOF, maxEOF);
317
//////////////////// Calc New Total Number Of Nodes /////////////////////////
319
newTotalNodes = filePtr->fcbLogicalSize / nodeSize; //�� hack!
320
//�� do we wish to perform any verification of newTotalNodes at this point?
322
btreePtr->totalNodes = newTotalNodes; //�� do we need to update freeNodes here too?
325
////////////// Calculate Number Of New Map Nodes Required ///////////////////
328
if (newTotalNodes > totalMapBits)
330
newMapNodes = (((newTotalNodes - totalMapBits) >> 3) / mapNodeRecSize) + 1;
331
firstNewMapNodeNum = oldTotalNodes;
332
lastNewMapNodeNum = firstNewMapNodeNum + newMapNodes - 1;
336
err = ReleaseNode (btreePtr, &mapNode);
343
/////////////////////// Initialize New Map Nodes ////////////////////////////
345
((BTNodeDescriptor*)mapNode.buffer)->fLink = firstNewMapNodeNum;
347
nodeNum = firstNewMapNodeNum;
350
err = GetNewNode (btreePtr, nodeNum, &newNode);
353
((NodeDescPtr)newNode.buffer)->numRecords = 1;
354
((NodeDescPtr)newNode.buffer)->kind = kBTMapNode;
356
// set free space offset
357
*(UInt16 *)((Ptr)newNode.buffer + nodeSize - 4) = nodeSize - 6;
359
if (nodeNum++ == lastNewMapNodeNum)
362
((BTNodeDescriptor*)newNode.buffer)->fLink = nodeNum; // point to next map node
364
err = UpdateNode (btreePtr, &newNode);
368
err = UpdateNode (btreePtr, &newNode);
372
///////////////////// Mark New Map Nodes Allocated //////////////////////////
374
nodeNum = firstNewMapNodeNum;
376
bitInRecord = nodeNum - recStartBit;
378
while (bitInRecord >= mapBits)
380
nextNodeNum = ((NodeDescPtr)mapNode.buffer)->fLink;
381
if ( nextNodeNum == 0)
383
err = fsBTNoMoreMapNodesErr;
387
err = UpdateNode (btreePtr, &mapNode);
390
err = GetNode (btreePtr, nextNodeNum, &mapNode);
395
mapStart = (UInt16 *) GetRecordAddress (btreePtr, mapNode.buffer, mapIndex);
396
mapSize = GetRecordSize (btreePtr, mapNode.buffer, mapIndex);
398
if (DEBUG_BUILD && mapSize != M_MapRecordSize (btreePtr->nodeSize) )
400
Panic ("\pExtendBTree: mapSize != M_MapRecordSize");
403
mapBits = mapSize << 3; // mapSize (in bytes) * 8
404
recStartBit = totalMapBits; // bit number of first bit in map record
405
totalMapBits += mapBits;
407
bitInRecord = nodeNum - recStartBit;
410
mapPos = mapStart + ((nodeNum - recStartBit) >> 4);
411
bitInWord = 15 - ((nodeNum - recStartBit) & 0x0000000F);
412
M_SWAP_BE16_SetBitNum (*mapPos, bitInWord);
416
} while (nodeNum <= lastNewMapNodeNum);
418
err = UpdateNode (btreePtr, &mapNode);
422
//////////////////////////////// Success ////////////////////////////////////
426
btreePtr->totalNodes = newTotalNodes;
427
btreePtr->freeNodes += (newTotalNodes - oldTotalNodes) - newMapNodes;
429
btreePtr->flags |= kBTHeaderDirty; //�� how about a macro for this
434
////////////////////////////// Error Exit ///////////////////////////////////
438
(void) ReleaseNode (btreePtr, &mapNode);
439
(void) ReleaseNode (btreePtr, &newNode);
446
/*-------------------------------------------------------------------------------
448
Routine: GetMapNode - Get the next map node and pointer to the map record.
450
Function: Given a BlockDescriptor to a map node in nodePtr, GetMapNode releases
451
it and gets the next node. If nodePtr->buffer is nil, then the header
455
Input: btreePtr - pointer to control block for BTree file
456
nodePtr - pointer to a BlockDescriptor of a map node
458
Output: nodePtr - pointer to the BlockDescriptor for the next map node
459
mapPtr - pointer to the map record within the map node
460
mapSize - number of bytes in the map record
462
Result: noErr - success
463
fsBTNoMoreMapNodesErr - we've run out of map nodes
464
fsBTInvalidNodeErr - bad node, or not node type kMapNode
466
-------------------------------------------------------------------------------*/
468
OSStatus GetMapNode (BTreeControlBlockPtr btreePtr,
469
BlockDescriptor *nodePtr,
477
if (nodePtr->buffer != nil) // if iterator is valid...
479
nextNodeNum = ((NodeDescPtr)nodePtr->buffer)->fLink;
480
if (nextNodeNum == 0)
482
err = fsBTNoMoreMapNodesErr;
486
err = ReleaseNode (btreePtr, nodePtr);
489
err = GetNode (btreePtr, nextNodeNum, nodePtr);
492
if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTMapNode)
494
err = fsBTBadNodeType;
498
++btreePtr->numMapNodesRead;
501
err = GetNode (btreePtr, kHeaderNodeNum, nodePtr);
504
if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTHeaderNode)
506
err = fsBTInvalidHeaderErr; //�� or fsBTBadNodeType
514
*mapPtr = (UInt16 *) GetRecordAddress (btreePtr, nodePtr->buffer, mapIndex);
515
*mapSize = GetRecordSize (btreePtr, nodePtr->buffer, mapIndex);
522
(void) ReleaseNode (btreePtr, nodePtr);
532
////////////////////////////////// CalcMapBits //////////////////////////////////
534
UInt32 CalcMapBits (BTreeControlBlockPtr btreePtr)
538
mapBits = M_HeaderMapRecordSize (btreePtr->nodeSize) << 3;
540
while (mapBits < btreePtr->totalNodes)
541
mapBits += M_MapRecordSize (btreePtr->nodeSize) << 3;
added
removed
.pc/0010-Rename-custom-macro-nil-with-NULL.patch/fsck_hfs.tproj/dfalib/BTreeAllocate.c
