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


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