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


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