![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to BTreeAllocate.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / XNU / bsd / hfs / hfscommon / BTree|
Return to BTreeAllocate.c CVS log | Up to [Apple XNU] / XNU / bsd / hfs / hfscommon / BTree |
1.1 root 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 "../headers/BTreesPrivate.h"
77:
78: ///////////////////// Routines Internal To BTreeAllocate.c //////////////////////
79:
80: OSStatus GetMapNode (BTreeControlBlockPtr btreePtr,
81: BlockDescriptor *nodePtr,
82: UInt16 **mapPtr,
83: UInt16 *mapSize );
84:
85: /////////////////////////////////////////////////////////////////////////////////
86:
87: /*-------------------------------------------------------------------------------
88:
89: Routine: AllocateNode - Find Free Node, Mark It Used, and Return Node Number.
90:
91: Function: Searches the map records for the first free node, marks it "in use" and
92: returns the node number found. This routine should really only be called
93: when we know there are free blocks, otherwise it's just a waste of time.
94:
95: Note: We have to examine map nodes a word at a time rather than a long word
96: because the External BTree Mgr used map records that were not an integral
97: number of long words. Too bad. In our spare time could develop a more
98: sophisticated algorithm that read map records by long words (and long
99: word aligned) and handled the spare bytes at the beginning and end
100: appropriately.
101:
102: Input: btreePtr - pointer to control block for BTree file
103:
104: Output: nodeNum - number of node allocated
105:
106:
107: Result: noErr - success
108: fsBTNoMoreMapNodesErr - no free blocks were found
109: != noErr - failure
110: -------------------------------------------------------------------------------*/
111:
112: OSStatus AllocateNode (BTreeControlBlockPtr btreePtr, UInt32 *nodeNum)
113: {
114: OSStatus err;
115: BlockDescriptor node;
116: UInt16 *mapPtr, *pos;
117: UInt16 mapSize, size;
118: UInt16 freeWord;
119: UInt16 mask;
120: UInt16 bitOffset;
121: UInt32 nodeNumber;
122:
123:
124: nodeNumber = 0; // first node number of header map record
125: node.buffer = nil; // clear node.buffer to get header node
126: // - and for ErrorExit
127:
128: while (true)
129: {
130: err = GetMapNode (btreePtr, &node, &mapPtr, &mapSize);
131: M_ExitOnError (err);
132:
133: //////////////////////// Find Word with Free Bit ////////////////////////////
134:
135: pos = mapPtr;
136: size = mapSize;
137: size >>= 1; // convert to number of words
138: //�� assumes mapRecords contain an integral number of words
139:
140: while ( size-- )
141: {
142: if ( *pos++ != 0xFFFF ) // assume test fails, and increment pos
143: break;
144: }
145:
146: --pos; // whoa! backup
147:
148: if (*pos != 0xFFFF) // hey, we got one!
149: break;
150:
151: nodeNumber += mapSize << 3; // covert to number of bits (nodes)
152: }
153:
154: ///////////////////////// Find Free Bit in Word /////////////////////////////
155:
156: freeWord = *pos;
157: bitOffset = 15;
158: mask = 0x8000;
159:
160: do {
161: if ( (freeWord & mask) == 0)
162: break;
163: mask >>= 1;
164: } while (--bitOffset);
165:
166: ////////////////////// Calculate Free Node Number ///////////////////////////
167:
168: nodeNumber += ((pos - mapPtr) << 4) + (15 - bitOffset); // (pos-mapPtr) = # of words!
169:
170:
171: ///////////////////////// Check for End of Map //////////////////////////////
172:
173: if (nodeNumber >= btreePtr->totalNodes)
174: {
175: err = fsBTFullErr;
176: goto ErrorExit;
177: }
178:
179: /////////////////////////// Allocate the Node ///////////////////////////////
180:
181: *pos |= mask; // set the map bit for the node
182:
183: err = UpdateNode (btreePtr, &node, 0, kLockTransaction);
184: M_ExitOnError (err);
185:
186: --btreePtr->freeNodes;
187: btreePtr->flags |= kBTHeaderDirty;
188: *nodeNum = nodeNumber;
189:
190: return noErr;
191:
192: ////////////////////////////////// Error Exit ///////////////////////////////////
193:
194: ErrorExit:
195:
196: (void) ReleaseNode (btreePtr, &node);
197: *nodeNum = 0;
198:
199: return err;
200: }
201:
202:
203:
204: /*-------------------------------------------------------------------------------
205:
206: Routine: FreeNode - Clear allocation bit for node.
207:
208: Function: Finds the bit representing the node specified by nodeNum in the node
209: map and clears the bit.
210:
211:
212: Input: btreePtr - pointer to control block for BTree file
213: nodeNum - number of node to mark free
214:
215: Output: none
216:
217: Result: noErr - success
218: fsBTNoMoreMapNodesErr - node number is beyond end of node map
219: != noErr - GetNode or ReleaseNode encountered some difficulty
220: -------------------------------------------------------------------------------*/
221:
222: OSStatus FreeNode (BTreeControlBlockPtr btreePtr, UInt32 nodeNum)
223: {
224: OSStatus err;
225: BlockDescriptor node;
226: UInt32 nodeIndex;
227: UInt16 mapSize;
228: UInt16 *mapPos;
229: UInt16 bitOffset;
230:
231:
232: //////////////////////////// Find Map Record ////////////////////////////////
233: nodeIndex = 0; // first node number of header map record
234: node.buffer = nil; // invalidate node.buffer to get header node
235:
236: while (nodeNum >= nodeIndex)
237: {
238: err = GetMapNode (btreePtr, &node, &mapPos, &mapSize);
239: M_ExitOnError (err);
240:
241: nodeIndex += mapSize << 3; // covert to number of bits (nodes)
242: }
243:
244: //////////////////////////// Mark Node Free /////////////////////////////////
245:
246: nodeNum -= (nodeIndex - (mapSize << 3)); // relative to this map record
247: bitOffset = 15 - (nodeNum & 0x0000000F); // last 4 bits are bit offset
248: mapPos += nodeNum >> 4; // point to word containing map bit
249: M_ClearBitNum (*mapPos, bitOffset); // clear it
250:
251: err = UpdateNode (btreePtr, &node, 0, kLockTransaction);
252: M_ExitOnError (err);
253:
254:
255: ++btreePtr->freeNodes;
256: btreePtr->flags |= kBTHeaderDirty; //�� how about a macro for this
257:
258: return noErr;
259:
260: ErrorExit:
261:
262: (void) ReleaseNode (btreePtr, &node);
263:
264: return err;
265: }
266:
267:
268:
269: /*-------------------------------------------------------------------------------
270:
271: Routine: ExtendBTree - Call FSAgent to extend file, and allocate necessary map nodes.
272:
273: Function: This routine calls the the FSAgent to extend the end of fork, if necessary,
274: to accomodate the number of nodes requested. It then allocates as many
275: map nodes as are necessary to account for all the nodes in the B*Tree.
276: If newTotalNodes is less than the current number of nodes, no action is
277: taken.
278:
279: Note: Internal HFS File Manager BTree Module counts on an integral number of
280: long words in map records, although they are not long word aligned.
281:
282: Input: btreePtr - pointer to control block for BTree file
283: newTotalNodes - total number of nodes the B*Tree is to extended to
284:
285: Output: none
286:
287: Result: noErr - success
288: != noErr - failure
289: -------------------------------------------------------------------------------*/
290:
291: OSStatus ExtendBTree (BTreeControlBlockPtr btreePtr,
292: UInt32 newTotalNodes )
293: {
294: OSStatus err;
295: FCB *filePtr;
296: FSSize minEOF, maxEOF;
297: UInt16 nodeSize;
298: UInt32 oldTotalNodes;
299: UInt32 newMapNodes;
300: UInt32 mapBits, totalMapBits;
301: UInt32 recStartBit;
302: UInt32 nodeNum, nextNodeNum;
303: UInt32 firstNewMapNodeNum, lastNewMapNodeNum;
304: BlockDescriptor mapNode, newNode;
305: UInt16 *mapPos;
306: UInt16 *mapStart;
307: UInt16 mapSize;
308: UInt16 mapNodeRecSize;
309: UInt32 bitInWord, bitInRecord;
310: UInt16 mapIndex;
311:
312:
313: oldTotalNodes = btreePtr->totalNodes;
314: if (newTotalNodes <= oldTotalNodes) // we're done!
315: return noErr;
316:
317: nodeSize = btreePtr->nodeSize;
318: filePtr = GetFileControlBlock(btreePtr->fileRefNum);
319:
320: mapNode.buffer = nil;
321: newNode.buffer = nil;
322:
323: mapNodeRecSize = nodeSize - sizeof(BTNodeDescriptor) - 6; // 2 bytes of free space (see note)
324:
325: //�� update for proper 64 bit arithmetic!!
326:
327:
328: //////////////////////// Count Bits In Node Map /////////////////////////////
329:
330: totalMapBits = 0;
331: do {
332: err = GetMapNode (btreePtr, &mapNode, &mapStart, &mapSize);
333: M_ExitOnError (err);
334:
335: mapBits = mapSize << 3; // mapSize (in bytes) * 8
336: recStartBit = totalMapBits; // bit number of first bit in map record
337: totalMapBits += mapBits;
338:
339: } while ( ((BTNodeDescriptor*)mapNode.buffer)->fLink != 0 );
340:
341: if (DEBUG_BUILD && totalMapBits != CalcMapBits (btreePtr))
342: Panic ("\pExtendBTree: totalMapBits != CalcMapBits");
343:
344: /////////////////////// Extend LEOF If Necessary ////////////////////////////
345:
346: minEOF = newTotalNodes * nodeSize;
347: if ( filePtr->fcbEOF < minEOF )
348: {
349: //��
350: //�� ???? Does this B*Tree pack stop working when LEOF > 2^32-1?
351: //��
352: maxEOF = ((UInt32)0xFFFFFFFFL);
353:
354: err = btreePtr->setEndOfForkProc (btreePtr->fileRefNum, minEOF, maxEOF);
355: M_ExitOnError (err);
356: }
357:
358:
359: //////////////////// Calc New Total Number Of Nodes /////////////////////////
360:
361: newTotalNodes = filePtr->fcbEOF / nodeSize; //�� hack!
362: //�� do we wish to perform any verification of newTotalNodes at this point?
363:
364: btreePtr->totalNodes = newTotalNodes; //�� do we need to update freeNodes here too?
365:
366:
367: ////////////// Calculate Number Of New Map Nodes Required ///////////////////
368:
369: newMapNodes = 0;
370: if (newTotalNodes > totalMapBits)
371: {
372: newMapNodes = (((newTotalNodes - totalMapBits) >> 3) / mapNodeRecSize) + 1;
373: firstNewMapNodeNum = oldTotalNodes;
374: lastNewMapNodeNum = firstNewMapNodeNum + newMapNodes - 1;
375: }
376: else
377: {
378: err = ReleaseNode (btreePtr, &mapNode);
379: M_ExitOnError (err);
380:
381: goto Success;
382: }
383:
384:
385: /////////////////////// Initialize New Map Nodes ////////////////////////////
386:
387: ((BTNodeDescriptor*)mapNode.buffer)->fLink = firstNewMapNodeNum;
388:
389: nodeNum = firstNewMapNodeNum;
390: while (true)
391: {
392: err = GetNewNode (btreePtr, nodeNum, &newNode);
393: M_ExitOnError (err);
394:
395: ((NodeDescPtr)newNode.buffer)->numRecords = 1;
396: ((NodeDescPtr)newNode.buffer)->kind = kBTMapNode;
397:
398: // set free space offset
399: *(UInt16 *)((Ptr)newNode.buffer + nodeSize - 4) = nodeSize - 6;
400:
401: if (nodeNum++ == lastNewMapNodeNum)
402: break;
403:
404: ((BTNodeDescriptor*)newNode.buffer)->fLink = nodeNum; // point to next map node
405:
406: err = UpdateNode (btreePtr, &newNode, 0, kLockTransaction);
407: M_ExitOnError (err);
408: }
409:
410: err = UpdateNode (btreePtr, &newNode, 0, kLockTransaction);
411: M_ExitOnError (err);
412:
413:
414: ///////////////////// Mark New Map Nodes Allocated //////////////////////////
415:
416: nodeNum = firstNewMapNodeNum;
417: do {
418: bitInRecord = nodeNum - recStartBit;
419:
420: while (bitInRecord >= mapBits)
421: {
422: nextNodeNum = ((NodeDescPtr)mapNode.buffer)->fLink;
423: if ( nextNodeNum == 0)
424: {
425: err = fsBTNoMoreMapNodesErr;
426: goto ErrorExit;
427: }
428:
429: err = UpdateNode (btreePtr, &mapNode, 0, kLockTransaction);
430: M_ExitOnError (err);
431:
432: err = GetNode (btreePtr, nextNodeNum, &mapNode);
433: M_ExitOnError (err);
434:
435: mapIndex = 0;
436:
437: mapStart = (UInt16 *) GetRecordAddress (btreePtr, mapNode.buffer, mapIndex);
438: mapSize = GetRecordSize (btreePtr, mapNode.buffer, mapIndex);
439:
440: if (DEBUG_BUILD && mapSize != M_MapRecordSize (btreePtr->nodeSize) )
441: {
442: Panic ("\pExtendBTree: mapSize != M_MapRecordSize");
443: }
444:
445: mapBits = mapSize << 3; // mapSize (in bytes) * 8
446: recStartBit = totalMapBits; // bit number of first bit in map record
447: totalMapBits += mapBits;
448:
449: bitInRecord = nodeNum - recStartBit;
450: }
451:
452: mapPos = mapStart + ((nodeNum - recStartBit) >> 4);
453: bitInWord = 15 - ((nodeNum - recStartBit) & 0x0000000F);
454: M_SetBitNum (*mapPos, bitInWord);
455:
456: ++nodeNum;
457:
458: } while (nodeNum <= lastNewMapNodeNum);
459:
460: err = UpdateNode (btreePtr, &mapNode, 0, kLockTransaction);
461: M_ExitOnError (err);
462:
463:
464: //////////////////////////////// Success ////////////////////////////////////
465:
466: Success:
467:
468: btreePtr->totalNodes = newTotalNodes;
469: btreePtr->freeNodes += (newTotalNodes - oldTotalNodes) - newMapNodes;
470:
471: btreePtr->flags |= kBTHeaderDirty; //�� how about a macro for this
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; //�� 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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.