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


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