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