]> 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-344.tar.gz
[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
327 //////////////////////// Count Bits In Node Map /////////////////////////////
328
329 totalMapBits = 0;
330 do {
331 err = GetMapNode (btreePtr, &mapNode, &mapStart, &mapSize);
332 M_ExitOnError (err);
333
334 mapBits = mapSize << 3; // mapSize (in bytes) * 8
335 recStartBit = totalMapBits; // bit number of first bit in map record
336 totalMapBits += mapBits;
337
338 } while ( ((BTNodeDescriptor*)mapNode.buffer)->fLink != 0 );
339
340 if (DEBUG_BUILD && totalMapBits != CalcMapBits (btreePtr))
341 Panic ("\pExtendBTree: totalMapBits != CalcMapBits");
342
343 /////////////////////// Extend LEOF If Necessary ////////////////////////////
344
345 minEOF = (UInt64)newTotalNodes * (UInt64)nodeSize;
346 if ( filePtr->fcbEOF < minEOF )
347 {
348 maxEOF = (UInt64)0x7fffffffLL * (UInt64)nodeSize;
349
350 err = btreePtr->setEndOfForkProc (btreePtr->fileRefNum, minEOF, maxEOF);
351 M_ExitOnError (err);
352 }
353
354
355 //////////////////// Calc New Total Number Of Nodes /////////////////////////
356
357 newTotalNodes = filePtr->fcbEOF / nodeSize; // hack!
358 // do we wish to perform any verification of newTotalNodes at this point?
359
360 btreePtr->totalNodes = newTotalNodes; // do we need to update freeNodes here too?
361
362
363 ////////////// Calculate Number Of New Map Nodes Required ///////////////////
364
365 newMapNodes = 0;
366 if (newTotalNodes > totalMapBits)
367 {
368 newMapNodes = (((newTotalNodes - totalMapBits) >> 3) / mapNodeRecSize) + 1;
369 firstNewMapNodeNum = oldTotalNodes;
370 lastNewMapNodeNum = firstNewMapNodeNum + newMapNodes - 1;
371 }
372 else
373 {
374 err = ReleaseNode (btreePtr, &mapNode);
375 M_ExitOnError (err);
376
377 goto Success;
378 }
379
380
381 /////////////////////// Initialize New Map Nodes ////////////////////////////
382
383 ((BTNodeDescriptor*)mapNode.buffer)->fLink = firstNewMapNodeNum;
384
385 nodeNum = firstNewMapNodeNum;
386 while (true)
387 {
388 err = GetNewNode (btreePtr, nodeNum, &newNode);
389 M_ExitOnError (err);
390
391 ((NodeDescPtr)newNode.buffer)->numRecords = 1;
392 ((NodeDescPtr)newNode.buffer)->kind = kBTMapNode;
393
394 // set free space offset
395 *(UInt16 *)((Ptr)newNode.buffer + nodeSize - 4) = nodeSize - 6;
396
397 if (nodeNum++ == lastNewMapNodeNum)
398 break;
399
400 ((BTNodeDescriptor*)newNode.buffer)->fLink = nodeNum; // point to next map node
401
402 err = UpdateNode (btreePtr, &newNode, 0, kLockTransaction);
403 M_ExitOnError (err);
404 }
405
406 err = UpdateNode (btreePtr, &newNode, 0, kLockTransaction);
407 M_ExitOnError (err);
408
409
410 ///////////////////// Mark New Map Nodes Allocated //////////////////////////
411
412 nodeNum = firstNewMapNodeNum;
413 do {
414 bitInRecord = nodeNum - recStartBit;
415
416 while (bitInRecord >= mapBits)
417 {
418 nextNodeNum = ((NodeDescPtr)mapNode.buffer)->fLink;
419 if ( nextNodeNum == 0)
420 {
421 err = fsBTNoMoreMapNodesErr;
422 goto ErrorExit;
423 }
424
425 err = UpdateNode (btreePtr, &mapNode, 0, kLockTransaction);
426 M_ExitOnError (err);
427
428 err = GetNode (btreePtr, nextNodeNum, &mapNode);
429 M_ExitOnError (err);
430
431 mapIndex = 0;
432
433 mapStart = (UInt16 *) GetRecordAddress (btreePtr, mapNode.buffer, mapIndex);
434 mapSize = GetRecordSize (btreePtr, mapNode.buffer, mapIndex);
435
436 if (DEBUG_BUILD && mapSize != M_MapRecordSize (btreePtr->nodeSize) )
437 {
438 Panic ("\pExtendBTree: mapSize != M_MapRecordSize");
439 }
440
441 mapBits = mapSize << 3; // mapSize (in bytes) * 8
442 recStartBit = totalMapBits; // bit number of first bit in map record
443 totalMapBits += mapBits;
444
445 bitInRecord = nodeNum - recStartBit;
446 }
447
448 mapPos = mapStart + ((nodeNum - recStartBit) >> 4);
449 bitInWord = 15 - ((nodeNum - recStartBit) & 0x0000000F);
450
451 M_SWAP_BE16_SetBitNum (*mapPos, bitInWord);
452
453 ++nodeNum;
454
455 } while (nodeNum <= lastNewMapNodeNum);
456
457 err = UpdateNode (btreePtr, &mapNode, 0, kLockTransaction);
458 M_ExitOnError (err);
459
460
461 //////////////////////////////// Success ////////////////////////////////////
462
463 Success:
464
465 btreePtr->totalNodes = newTotalNodes;
466 btreePtr->freeNodes += (newTotalNodes - oldTotalNodes) - newMapNodes;
467
468 btreePtr->flags |= kBTHeaderDirty; //\80\80 how about a macro for this
469
470 /* Force the b-tree header changes to disk */
471 (void) UpdateHeader (btreePtr, true);
472
473 return noErr;
474
475
476 ////////////////////////////// Error Exit ///////////////////////////////////
477
478 ErrorExit:
479
480 (void) ReleaseNode (btreePtr, &mapNode);
481 (void) ReleaseNode (btreePtr, &newNode);
482
483 return err;
484 }
485
486
487
488 /*-------------------------------------------------------------------------------
489
490 Routine: GetMapNode - Get the next map node and pointer to the map record.
491
492 Function: Given a BlockDescriptor to a map node in nodePtr, GetMapNode releases
493 it and gets the next node. If nodePtr->buffer is nil, then the header
494 node is retrieved.
495
496
497 Input: btreePtr - pointer to control block for BTree file
498 nodePtr - pointer to a BlockDescriptor of a map node
499
500 Output: nodePtr - pointer to the BlockDescriptor for the next map node
501 mapPtr - pointer to the map record within the map node
502 mapSize - number of bytes in the map record
503
504 Result: noErr - success
505 fsBTNoMoreMapNodesErr - we've run out of map nodes
506 fsBTInvalidNodeErr - bad node, or not node type kMapNode
507 != noErr - failure
508 -------------------------------------------------------------------------------*/
509
510 OSStatus GetMapNode (BTreeControlBlockPtr btreePtr,
511 BlockDescriptor *nodePtr,
512 UInt16 **mapPtr,
513 UInt16 *mapSize )
514 {
515 OSStatus err;
516 UInt16 mapIndex;
517 UInt32 nextNodeNum;
518
519 if (nodePtr->buffer != nil) // if iterator is valid...
520 {
521 nextNodeNum = ((NodeDescPtr)nodePtr->buffer)->fLink;
522 if (nextNodeNum == 0)
523 {
524 err = fsBTNoMoreMapNodesErr;
525 goto ErrorExit;
526 }
527
528 err = ReleaseNode (btreePtr, nodePtr);
529 M_ExitOnError (err);
530
531 err = GetNode (btreePtr, nextNodeNum, nodePtr);
532 M_ExitOnError (err);
533
534 if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTMapNode)
535 {
536 err = fsBTBadNodeType;
537 goto ErrorExit;
538 }
539
540 ++btreePtr->numMapNodesRead;
541 mapIndex = 0;
542 } else {
543 err = GetNode (btreePtr, kHeaderNodeNum, nodePtr);
544 M_ExitOnError (err);
545
546 if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTHeaderNode)
547 {
548 err = fsBTInvalidHeaderErr; //\80\80 or fsBTBadNodeType
549 goto ErrorExit;
550 }
551
552 mapIndex = 2;
553 }
554
555
556 *mapPtr = (UInt16 *) GetRecordAddress (btreePtr, nodePtr->buffer, mapIndex);
557 *mapSize = GetRecordSize (btreePtr, nodePtr->buffer, mapIndex);
558
559 return noErr;
560
561
562 ErrorExit:
563
564 (void) ReleaseNode (btreePtr, nodePtr);
565
566 *mapPtr = nil;
567 *mapSize = 0;
568
569 return err;
570 }
571
572
573
574 ////////////////////////////////// CalcMapBits //////////////////////////////////
575
576 UInt32 CalcMapBits (BTreeControlBlockPtr btreePtr)
577 {
578 UInt32 mapBits;
579
580 mapBits = M_HeaderMapRecordSize (btreePtr->nodeSize) << 3;
581
582 while (mapBits < btreePtr->totalNodes)
583 mapBits += M_MapRecordSize (btreePtr->nodeSize) << 3;
584
585 return mapBits;
586 }
mirror of XNU