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


e08170ee133fb606bf1f37c8964fa14876f07629
[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 * 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
197 /* Account for allocations from node reserve */
198 BTUpdateReserve(btreePtr, 1);
199
200 *nodeNum = nodeNumber;
201
202 return noErr;
203
204 ////////////////////////////////// Error Exit ///////////////////////////////////
205
206 ErrorExit:
207
208 (void) ReleaseNode (btreePtr, &node);
209 *nodeNum = 0;
210
211 return err;
212 }
213
214
215
216 /*-------------------------------------------------------------------------------
217
218 Routine: FreeNode - Clear allocation bit for node.
219
220 Function: Finds the bit representing the node specified by nodeNum in the node
221 map and clears the bit.
222
223
224 Input: btreePtr - pointer to control block for BTree file
225 nodeNum - number of node to mark free
226
227 Output: none
228
229 Result: noErr - success
230 fsBTNoMoreMapNodesErr - node number is beyond end of node map
231 != noErr - GetNode or ReleaseNode encountered some difficulty
232 -------------------------------------------------------------------------------*/
233
234 OSStatus FreeNode (BTreeControlBlockPtr btreePtr, UInt32 nodeNum)
235 {
236 OSStatus err;
237 BlockDescriptor node;
238 UInt32 nodeIndex;
239 UInt16 mapSize;
240 UInt16 *mapPos;
241 UInt16 bitOffset;
242
243
244 //////////////////////////// Find Map Record ////////////////////////////////
245 nodeIndex = 0; // first node number of header map record
246 node.buffer = nil; // invalidate node.buffer to get header node
247 node.blockHeader = nil;
248
249 while (nodeNum >= nodeIndex)
250 {
251 err = GetMapNode (btreePtr, &node, &mapPos, &mapSize);
252 M_ExitOnError (err);
253
254 nodeIndex += mapSize << 3; // covert to number of bits (nodes)
255 }
256
257 //////////////////////////// Mark Node Free /////////////////////////////////
258
259 // XXXdbg
260 ModifyBlockStart(btreePtr->fileRefNum, &node);
261
262 nodeNum -= (nodeIndex - (mapSize << 3)); // relative to this map record
263 bitOffset = 15 - (nodeNum & 0x0000000F); // last 4 bits are bit offset
264 mapPos += nodeNum >> 4; // point to word containing map bit
265
266 M_SWAP_BE16_ClearBitNum (*mapPos, bitOffset); // clear it
267
268 err = UpdateNode (btreePtr, &node, 0, kLockTransaction);
269 M_ExitOnError (err);
270
271 ++btreePtr->freeNodes;
272 btreePtr->flags |= kBTHeaderDirty; // how about a macro for this
273
274 return noErr;
275
276 ErrorExit:
277
278 (void) ReleaseNode (btreePtr, &node);
279
280 return err;
281 }
282
283
284
285 /*-------------------------------------------------------------------------------
286
287 Routine: ExtendBTree - Call FSAgent to extend file, and allocate necessary map nodes.
288
289 Function: This routine calls the the FSAgent to extend the end of fork, if necessary,
290 to accomodate the number of nodes requested. It then allocates as many
291 map nodes as are necessary to account for all the nodes in the B*Tree.
292 If newTotalNodes is less than the current number of nodes, no action is
293 taken.
294
295 Note: Internal HFS File Manager BTree Module counts on an integral number of
296 long words in map records, although they are not long word aligned.
297
298 Input: btreePtr - pointer to control block for BTree file
299 newTotalNodes - total number of nodes the B*Tree is to extended to
300
301 Output: none
302
303 Result: noErr - success
304 != noErr - failure
305 -------------------------------------------------------------------------------*/
306
307 OSStatus ExtendBTree (BTreeControlBlockPtr btreePtr,
308 UInt32 newTotalNodes )
309 {
310 OSStatus err;
311 FCB *filePtr;
312 FSSize minEOF, maxEOF;
313 UInt16 nodeSize;
314 UInt32 oldTotalNodes;
315 UInt32 newMapNodes;
316 UInt32 mapBits, totalMapBits;
317 UInt32 recStartBit;
318 UInt32 nodeNum, nextNodeNum;
319 UInt32 firstNewMapNodeNum, lastNewMapNodeNum;
320 BlockDescriptor mapNode, newNode;
321 UInt16 *mapPos;
322 UInt16 *mapStart;
323 UInt16 mapSize;
324 UInt16 mapNodeRecSize;
325 UInt32 bitInWord, bitInRecord;
326 UInt16 mapIndex;
327
328
329 oldTotalNodes = btreePtr->totalNodes;
330 if (newTotalNodes <= oldTotalNodes) // we're done!
331 return noErr;
332
333 nodeSize = btreePtr->nodeSize;
334 filePtr = GetFileControlBlock(btreePtr->fileRefNum);
335
336 mapNode.buffer = nil;
337 mapNode.blockHeader = nil;
338 newNode.buffer = nil;
339 newNode.blockHeader = nil;
340
341 mapNodeRecSize = nodeSize - sizeof(BTNodeDescriptor) - 6; // 2 bytes of free space (see note)
342
343
344 //////////////////////// Count Bits In Node Map /////////////////////////////
345
346 totalMapBits = 0;
347 do {
348 err = GetMapNode (btreePtr, &mapNode, &mapStart, &mapSize);
349 M_ExitOnError (err);
350
351 mapBits = mapSize << 3; // mapSize (in bytes) * 8
352 recStartBit = totalMapBits; // bit number of first bit in map record
353 totalMapBits += mapBits;
354
355 } while ( ((BTNodeDescriptor*)mapNode.buffer)->fLink != 0 );
356
357 if (DEBUG_BUILD && totalMapBits != CalcMapBits (btreePtr))
358 Panic ("\pExtendBTree: totalMapBits != CalcMapBits");
359
360 /////////////////////// Extend LEOF If Necessary ////////////////////////////
361
362 minEOF = (UInt64)newTotalNodes * (UInt64)nodeSize;
363 if ( filePtr->fcbEOF < minEOF )
364 {
365 maxEOF = (UInt64)0x7fffffffLL * (UInt64)nodeSize;
366
367 err = btreePtr->setEndOfForkProc (btreePtr->fileRefNum, minEOF, maxEOF);
368 M_ExitOnError (err);
369 }
370
371
372 //////////////////// Calc New Total Number Of Nodes /////////////////////////
373
374 newTotalNodes = filePtr->fcbEOF / nodeSize; // hack!
375 // do we wish to perform any verification of newTotalNodes at this point?
376
377 btreePtr->totalNodes = newTotalNodes; // do we need to update freeNodes here too?
378
379
380 ////////////// Calculate Number Of New Map Nodes Required ///////////////////
381
382 newMapNodes = 0;
383 if (newTotalNodes > totalMapBits)
384 {
385 newMapNodes = (((newTotalNodes - totalMapBits) >> 3) / mapNodeRecSize) + 1;
386 firstNewMapNodeNum = oldTotalNodes;
387 lastNewMapNodeNum = firstNewMapNodeNum + newMapNodes - 1;
388 }
389 else
390 {
391 err = ReleaseNode (btreePtr, &mapNode);
392 M_ExitOnError (err);
393
394 goto Success;
395 }
396
397
398 /////////////////////// Initialize New Map Nodes ////////////////////////////
399 // XXXdbg - this is the correct place for this:
400 ModifyBlockStart(btreePtr->fileRefNum, &mapNode);
401
402 ((BTNodeDescriptor*)mapNode.buffer)->fLink = firstNewMapNodeNum;
403
404 nodeNum = firstNewMapNodeNum;
405 while (true)
406 {
407 err = GetNewNode (btreePtr, nodeNum, &newNode);
408 M_ExitOnError (err);
409
410 // XXXdbg
411 ModifyBlockStart(btreePtr->fileRefNum, &newNode);
412
413 ((NodeDescPtr)newNode.buffer)->numRecords = 1;
414 ((NodeDescPtr)newNode.buffer)->kind = kBTMapNode;
415
416 // set free space offset
417 *(UInt16 *)((Ptr)newNode.buffer + nodeSize - 4) = nodeSize - 6;
418
419 if (nodeNum++ == lastNewMapNodeNum)
420 break;
421
422 ((BTNodeDescriptor*)newNode.buffer)->fLink = nodeNum; // point to next map node
423
424 err = UpdateNode (btreePtr, &newNode, 0, kLockTransaction);
425 M_ExitOnError (err);
426 }
427
428 err = UpdateNode (btreePtr, &newNode, 0, kLockTransaction);
429 M_ExitOnError (err);
430
431
432 ///////////////////// Mark New Map Nodes Allocated //////////////////////////
433
434 nodeNum = firstNewMapNodeNum;
435 do {
436 bitInRecord = nodeNum - recStartBit;
437
438 while (bitInRecord >= mapBits)
439 {
440 nextNodeNum = ((NodeDescPtr)mapNode.buffer)->fLink;
441 if ( nextNodeNum == 0)
442 {
443 err = fsBTNoMoreMapNodesErr;
444 goto ErrorExit;
445 }
446
447 err = UpdateNode (btreePtr, &mapNode, 0, kLockTransaction);
448 M_ExitOnError (err);
449
450 err = GetNode (btreePtr, nextNodeNum, &mapNode);
451 M_ExitOnError (err);
452
453 // XXXdbg
454 ModifyBlockStart(btreePtr->fileRefNum, &mapNode);
455
456 mapIndex = 0;
457
458 mapStart = (UInt16 *) GetRecordAddress (btreePtr, mapNode.buffer, mapIndex);
459 mapSize = GetRecordSize (btreePtr, mapNode.buffer, mapIndex);
460
461 if (DEBUG_BUILD && mapSize != M_MapRecordSize (btreePtr->nodeSize) )
462 {
463 Panic ("\pExtendBTree: mapSize != M_MapRecordSize");
464 }
465
466 mapBits = mapSize << 3; // mapSize (in bytes) * 8
467 recStartBit = totalMapBits; // bit number of first bit in map record
468 totalMapBits += mapBits;
469
470 bitInRecord = nodeNum - recStartBit;
471 }
472
473 mapPos = mapStart + ((nodeNum - recStartBit) >> 4);
474 bitInWord = 15 - ((nodeNum - recStartBit) & 0x0000000F);
475
476 M_SWAP_BE16_SetBitNum (*mapPos, bitInWord);
477
478 ++nodeNum;
479
480 } while (nodeNum <= lastNewMapNodeNum);
481
482 err = UpdateNode (btreePtr, &mapNode, 0, kLockTransaction);
483 M_ExitOnError (err);
484
485
486 //////////////////////////////// Success ////////////////////////////////////
487
488 Success:
489
490 btreePtr->totalNodes = newTotalNodes;
491 btreePtr->freeNodes += (newTotalNodes - oldTotalNodes) - newMapNodes;
492
493 btreePtr->flags |= kBTHeaderDirty; //\80\80 how about a macro for this
494
495 /* Force the b-tree header changes to disk */
496 (void) UpdateHeader (btreePtr, true);
497
498 return noErr;
499
500
501 ////////////////////////////// Error Exit ///////////////////////////////////
502
503 ErrorExit:
504
505 (void) ReleaseNode (btreePtr, &mapNode);
506 (void) ReleaseNode (btreePtr, &newNode);
507
508 return err;
509 }
510
511
512
513 /*-------------------------------------------------------------------------------
514
515 Routine: GetMapNode - Get the next map node and pointer to the map record.
516
517 Function: Given a BlockDescriptor to a map node in nodePtr, GetMapNode releases
518 it and gets the next node. If nodePtr->buffer is nil, then the header
519 node is retrieved.
520
521
522 Input: btreePtr - pointer to control block for BTree file
523 nodePtr - pointer to a BlockDescriptor of a map node
524
525 Output: nodePtr - pointer to the BlockDescriptor for the next map node
526 mapPtr - pointer to the map record within the map node
527 mapSize - number of bytes in the map record
528
529 Result: noErr - success
530 fsBTNoMoreMapNodesErr - we've run out of map nodes
531 fsBTInvalidNodeErr - bad node, or not node type kMapNode
532 != noErr - failure
533 -------------------------------------------------------------------------------*/
534
535 OSStatus GetMapNode (BTreeControlBlockPtr btreePtr,
536 BlockDescriptor *nodePtr,
537 UInt16 **mapPtr,
538 UInt16 *mapSize )
539 {
540 OSStatus err;
541 UInt16 mapIndex;
542 UInt32 nextNodeNum;
543
544 if (nodePtr->buffer != nil) // if iterator is valid...
545 {
546 nextNodeNum = ((NodeDescPtr)nodePtr->buffer)->fLink;
547 if (nextNodeNum == 0)
548 {
549 err = fsBTNoMoreMapNodesErr;
550 goto ErrorExit;
551 }
552
553 err = ReleaseNode (btreePtr, nodePtr);
554 M_ExitOnError (err);
555
556 err = GetNode (btreePtr, nextNodeNum, nodePtr);
557 M_ExitOnError (err);
558
559 if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTMapNode)
560 {
561 err = fsBTBadNodeType;
562 goto ErrorExit;
563 }
564
565 ++btreePtr->numMapNodesRead;
566 mapIndex = 0;
567 } else {
568 err = GetNode (btreePtr, kHeaderNodeNum, nodePtr);
569 M_ExitOnError (err);
570
571 if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTHeaderNode)
572 {
573 err = fsBTInvalidHeaderErr; //\80\80 or fsBTBadNodeType
574 goto ErrorExit;
575 }
576
577 mapIndex = 2;
578 }
579
580
581 *mapPtr = (UInt16 *) GetRecordAddress (btreePtr, nodePtr->buffer, mapIndex);
582 *mapSize = GetRecordSize (btreePtr, nodePtr->buffer, mapIndex);
583
584 return noErr;
585
586
587 ErrorExit:
588
589 (void) ReleaseNode (btreePtr, nodePtr);
590
591 *mapPtr = nil;
592 *mapSize = 0;
593
594 return err;
595 }
596
597
598
599 ////////////////////////////////// CalcMapBits //////////////////////////////////
600
601 UInt32 CalcMapBits (BTreeControlBlockPtr btreePtr)
602 {
603 UInt32 mapBits;
604
605 mapBits = M_HeaderMapRecordSize (btreePtr->nodeSize) << 3;
606
607 while (mapBits < btreePtr->totalNodes)
608 mapBits += M_MapRecordSize (btreePtr->nodeSize) << 3;
609
610 return mapBits;
611 }
mirror of XNU