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


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