![[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 Darwin 0.x] / kernel / bsd / hfs / hfscommon / BTree|
Return to BTreeAllocate.c CVS log | Up to [Apple Darwin 0.x] / kernel / bsd / hfs / hfscommon / BTree |
1.1 root 1: /*
2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7: * Reserved. This file contains Original Code and/or Modifications of
8: * Original Code as defined in and that are subject to the Apple Public
9: * Source License Version 1.1 (the "License"). You may not use this file
10: * except in compliance with the License. Please obtain a copy of the
11: * License at http://www.apple.com/publicsource and read it before using
12: * this file.
13: *
14: * The Original Code and all software distributed under the License are
15: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19: * License for the specific language governing rights and limitations
20: * under the License.
21: *
22: * @APPLE_LICENSE_HEADER_END@
23: */
24:
25: /*
26: File: BTreeAllocate.c
27:
28: Contains: BTree Node Allocation routines for the BTree Module.
29:
30: Version: xxx put the technology version here xxx
31:
32: Written by: Gordon Sheridan and Bill Bruffey
33:
34: Copyright: � 1992-1998 by Apple Computer, Inc., all rights reserved.
35:
36: File Ownership:
37:
38: DRI: Don Brady
39:
40: Other Contact: Mark Day
41:
42: Technology: File Systems
43:
44: Writers:
45:
46: (djb) Don Brady
47: (ser) Scott Roberts
48: (msd) Mark Day
49:
50: Change History (most recent first):
51:
52: <CS3> 11/24/97 djb Remove some debug code (Panic calls).
53: <CS2> 7/24/97 djb CallbackProcs now take refnum instead of an FCB.
54: <CS1> 4/23/97 djb first checked in
55:
56: <HFS2> 2/19/97 djb Change E_BadNodeType to fsBTBadNodeType.
57: <HFS1> 12/19/96 djb first checked in
58:
59: History applicable to original Scarecrow Design:
60:
61: <4> 10/25/96 ser Changing for new VFPI
62: <3> 10/18/96 ser Converting over VFPI changes
63: <2> 1/10/96 msd Change 64-bit math to use real function names from Math64.i.
64: <1> 10/18/95 rst Moved from Scarecrow project.
65:
66: <8> 1/12/95 wjk Adopt Model FileSystem changes in D5.
67: <7> 9/30/94 prp Get in sync with D2 interface changes.
68: <6> 7/22/94 wjk Convert to the new set of header files.
69: <5> 8/31/93 prp Use U64SetU instead of S64Set.
70: <4> 5/21/93 gs Fix ExtendBTree bug.
71: <3> 5/10/93 gs Fix pointer arithmetic bug in AllocateNode.
72: <2> 3/23/93 gs finish ExtendBTree routine.
73: <1> 2/8/93 gs first checked in
74: <0> 1/1/93 gs begin AllocateNode and FreeNode
75:
76: */
77:
78: #include "../headers/BTreesPrivate.h"
79:
80: ///////////////////// Routines Internal To BTreeAllocate.c //////////////////////
81:
82: OSStatus GetMapNode (BTreeControlBlockPtr btreePtr,
83: BlockDescriptor *nodePtr,
84: UInt16 **mapPtr,
85: UInt16 *mapSize );
86:
87: /////////////////////////////////////////////////////////////////////////////////
88:
89: /*-------------------------------------------------------------------------------
90:
91: Routine: AllocateNode - Find Free Node, Mark It Used, and Return Node Number.
92:
93: Function: Searches the map records for the first free node, marks it "in use" and
94: returns the node number found. This routine should really only be called
95: when we know there are free blocks, otherwise it's just a waste of time.
96:
97: Note: We have to examine map nodes a word at a time rather than a long word
98: because the External BTree Mgr used map records that were not an integral
99: number of long words. Too bad. In our spare time could develop a more
100: sophisticated algorithm that read map records by long words (and long
101: word aligned) and handled the spare bytes at the beginning and end
102: appropriately.
103:
104: Input: btreePtr - pointer to control block for BTree file
105:
106: Output: nodeNum - number of node allocated
107:
108:
109: Result: noErr - success
110: fsBTNoMoreMapNodesErr - no free blocks were found
111: != noErr - failure
112: -------------------------------------------------------------------------------*/
113:
114: OSStatus AllocateNode (BTreeControlBlockPtr btreePtr, UInt32 *nodeNum)
115: {
116: OSStatus err;
117: BlockDescriptor node;
118: UInt16 *mapPtr, *pos;
119: UInt16 mapSize, size;
120: UInt16 freeWord;
121: UInt16 mask;
122: UInt16 bitOffset;
123: UInt32 nodeNumber;
124:
125:
126: nodeNumber = 0; // first node number of header map record
127: node.buffer = nil; // clear node.buffer to get header node
128: // - and for ErrorExit
129:
130: while (true)
131: {
132: err = GetMapNode (btreePtr, &node, &mapPtr, &mapSize);
133: M_ExitOnError (err);
134:
135: //////////////////////// Find Word with Free Bit ////////////////////////////
136:
137: pos = mapPtr;
138: size = mapSize;
139: size >>= 1; // convert to number of words
140: //�� assumes mapRecords contain an integral number of words
141:
142: while ( size-- )
143: {
144: if ( *pos++ != 0xFFFF ) // assume test fails, and increment pos
145: break;
146: }
147:
148: --pos; // whoa! backup
149:
150: if (*pos != 0xFFFF) // hey, we got one!
151: break;
152:
153: nodeNumber += mapSize << 3; // covert to number of bits (nodes)
154: }
155:
156: ///////////////////////// Find Free Bit in Word /////////////////////////////
157:
158: freeWord = *pos;
159: bitOffset = 15;
160: mask = 0x8000;
161:
162: do {
163: if ( (freeWord & mask) == 0)
164: break;
165: mask >>= 1;
166: } while (--bitOffset);
167:
168: ////////////////////// Calculate Free Node Number ///////////////////////////
169:
170: nodeNumber += ((pos - mapPtr) << 4) + (15 - bitOffset); // (pos-mapPtr) = # of words!
171:
172:
173: ///////////////////////// Check for End of Map //////////////////////////////
174:
175: if (nodeNumber >= btreePtr->totalNodes)
176: {
177: err = fsBTFullErr;
178: goto ErrorExit;
179: }
180:
181: /////////////////////////// Allocate the Node ///////////////////////////////
182:
183: *pos |= mask; // set the map bit for the node
184:
185: err = UpdateNode (btreePtr, &node);
186: M_ExitOnError (err);
187:
188: --btreePtr->freeNodes;
189: btreePtr->flags |= kBTHeaderDirty;
190: *nodeNum = nodeNumber;
191:
192: return noErr;
193:
194: ////////////////////////////////// Error Exit ///////////////////////////////////
195:
196: ErrorExit:
197:
198: (void) ReleaseNode (btreePtr, &node);
199: *nodeNum = 0;
200:
201: return err;
202: }
203:
204:
205:
206: /*-------------------------------------------------------------------------------
207:
208: Routine: FreeNode - Clear allocation bit for node.
209:
210: Function: Finds the bit representing the node specified by nodeNum in the node
211: map and clears the bit.
212:
213:
214: Input: btreePtr - pointer to control block for BTree file
215: nodeNum - number of node to mark free
216:
217: Output: none
218:
219: Result: noErr - success
220: fsBTNoMoreMapNodesErr - node number is beyond end of node map
221: != noErr - GetNode or ReleaseNode encountered some difficulty
222: -------------------------------------------------------------------------------*/
223:
224: OSStatus FreeNode (BTreeControlBlockPtr btreePtr, UInt32 nodeNum)
225: {
226: OSStatus err;
227: BlockDescriptor node;
228: UInt32 nodeIndex;
229: UInt16 mapSize;
230: UInt16 *mapPos;
231: UInt16 bitOffset;
232:
233:
234: //////////////////////////// Find Map Record ////////////////////////////////
235: nodeIndex = 0; // first node number of header map record
236: node.buffer = nil; // invalidate node.buffer to get header node
237:
238: while (nodeNum >= nodeIndex)
239: {
240: err = GetMapNode (btreePtr, &node, &mapPos, &mapSize);
241: M_ExitOnError (err);
242:
243: nodeIndex += mapSize << 3; // covert to number of bits (nodes)
244: }
245:
246: //////////////////////////// Mark Node Free /////////////////////////////////
247:
248: nodeNum -= (nodeIndex - (mapSize << 3)); // relative to this map record
249: bitOffset = 15 - (nodeNum & 0x0000000F); // last 4 bits are bit offset
250: mapPos += nodeNum >> 4; // point to word containing map bit
251: M_ClearBitNum (*mapPos, bitOffset); // clear it
252:
253: err = UpdateNode (btreePtr, &node);
254: M_ExitOnError (err);
255:
256:
257: ++btreePtr->freeNodes;
258: btreePtr->flags |= kBTHeaderDirty; //�� how about a macro for this
259:
260: return noErr;
261:
262: ErrorExit:
263:
264: (void) ReleaseNode (btreePtr, &node);
265:
266: return err;
267: }
268:
269:
270:
271: /*-------------------------------------------------------------------------------
272:
273: Routine: ExtendBTree - Call FSAgent to extend file, and allocate necessary map nodes.
274:
275: Function: This routine calls the the FSAgent to extend the end of fork, if necessary,
276: to accomodate the number of nodes requested. It then allocates as many
277: map nodes as are necessary to account for all the nodes in the B*Tree.
278: If newTotalNodes is less than the current number of nodes, no action is
279: taken.
280:
281: Note: Internal HFS File Manager BTree Module counts on an integral number of
282: long words in map records, although they are not long word aligned.
283:
284: Input: btreePtr - pointer to control block for BTree file
285: newTotalNodes - total number of nodes the B*Tree is to extended to
286:
287: Output: none
288:
289: Result: noErr - success
290: != noErr - failure
291: -------------------------------------------------------------------------------*/
292:
293: OSStatus ExtendBTree (BTreeControlBlockPtr btreePtr,
294: UInt32 newTotalNodes )
295: {
296: OSStatus err;
297: FCB *filePtr;
298: FSSize minEOF, maxEOF;
299: UInt16 nodeSize;
300: UInt32 oldTotalNodes;
301: UInt32 newMapNodes;
302: UInt32 mapBits, totalMapBits;
303: UInt32 recStartBit;
304: UInt32 nodeNum, nextNodeNum;
305: UInt32 firstNewMapNodeNum, lastNewMapNodeNum;
306: BlockDescriptor mapNode, newNode;
307: UInt16 *mapPos;
308: UInt16 *mapStart;
309: UInt16 mapSize;
310: UInt16 mapNodeRecSize;
311: UInt32 bitInWord, bitInRecord;
312: UInt16 mapIndex;
313:
314:
315: oldTotalNodes = btreePtr->totalNodes;
316: if (newTotalNodes <= oldTotalNodes) // we're done!
317: return noErr;
318:
319: nodeSize = btreePtr->nodeSize;
320: filePtr = GetFileControlBlock(btreePtr->fileRefNum);
321:
322: mapNode.buffer = nil;
323: newNode.buffer = nil;
324:
325: mapNodeRecSize = nodeSize - sizeof(BTNodeDescriptor) - 6; // 2 bytes of free space (see note)
326:
327: //�� update for proper 64 bit arithmetic!!
328:
329:
330: //////////////////////// Count Bits In Node Map /////////////////////////////
331:
332: totalMapBits = 0;
333: do {
334: err = GetMapNode (btreePtr, &mapNode, &mapStart, &mapSize);
335: M_ExitOnError (err);
336:
337: mapBits = mapSize << 3; // mapSize (in bytes) * 8
338: recStartBit = totalMapBits; // bit number of first bit in map record
339: totalMapBits += mapBits;
340:
341: } while ( ((BTNodeDescriptor*)mapNode.buffer)->fLink != 0 );
342:
343: if (DEBUG_BUILD && totalMapBits != CalcMapBits (btreePtr))
344: Panic ("\pExtendBTree: totalMapBits != CalcMapBits");
345:
346: /////////////////////// Extend LEOF If Necessary ////////////////////////////
347:
348: minEOF = newTotalNodes * nodeSize;
349: if ( filePtr->fcbEOF < minEOF )
350: {
351: //��
352: //�� ???? Does this B*Tree pack stop working when LEOF > 2^32-1?
353: //��
354: maxEOF = ((UInt32)0xFFFFFFFFL);
355:
356: err = btreePtr->setEndOfForkProc (btreePtr->fileRefNum, minEOF, maxEOF);
357: M_ExitOnError (err);
358: }
359:
360:
361: //////////////////// Calc New Total Number Of Nodes /////////////////////////
362:
363: newTotalNodes = filePtr->fcbEOF / nodeSize; //�� hack!
364: //�� do we wish to perform any verification of newTotalNodes at this point?
365:
366: btreePtr->totalNodes = newTotalNodes; //�� do we need to update freeNodes here too?
367:
368:
369: ////////////// Calculate Number Of New Map Nodes Required ///////////////////
370:
371: newMapNodes = 0;
372: if (newTotalNodes > totalMapBits)
373: {
374: newMapNodes = (((newTotalNodes - totalMapBits) >> 3) / mapNodeRecSize) + 1;
375: firstNewMapNodeNum = oldTotalNodes;
376: lastNewMapNodeNum = firstNewMapNodeNum + newMapNodes - 1;
377: }
378: else
379: {
380: err = ReleaseNode (btreePtr, &mapNode);
381: M_ExitOnError (err);
382:
383: goto Success;
384: }
385:
386:
387: /////////////////////// Initialize New Map Nodes ////////////////////////////
388:
389: ((BTNodeDescriptor*)mapNode.buffer)->fLink = firstNewMapNodeNum;
390:
391: nodeNum = firstNewMapNodeNum;
392: while (true)
393: {
394: err = GetNewNode (btreePtr, nodeNum, &newNode);
395: M_ExitOnError (err);
396:
397: ((NodeDescPtr)newNode.buffer)->numRecords = 1;
398: ((NodeDescPtr)newNode.buffer)->type = kMapNode;
399:
400: // set free space offset
401: *(UInt16 *)((Ptr)newNode.buffer + nodeSize - 4) = nodeSize - 6;
402:
403: if (nodeNum++ == lastNewMapNodeNum)
404: break;
405:
406: ((BTNodeDescriptor*)newNode.buffer)->fLink = nodeNum; // point to next map node
407:
408: err = UpdateNode (btreePtr, &newNode);
409: M_ExitOnError (err);
410: }
411:
412: err = UpdateNode (btreePtr, &newNode);
413: M_ExitOnError (err);
414:
415:
416: ///////////////////// Mark New Map Nodes Allocated //////////////////////////
417:
418: nodeNum = firstNewMapNodeNum;
419: do {
420: bitInRecord = nodeNum - recStartBit;
421:
422: while (bitInRecord >= mapBits)
423: {
424: nextNodeNum = ((NodeDescPtr)mapNode.buffer)->fLink;
425: if ( nextNodeNum == 0)
426: {
427: err = fsBTNoMoreMapNodesErr;
428: goto ErrorExit;
429: }
430:
431: err = UpdateNode (btreePtr, &mapNode);
432: M_ExitOnError (err);
433:
434: err = GetNode (btreePtr, nextNodeNum, &mapNode);
435: M_ExitOnError (err);
436:
437: mapIndex = 0;
438:
439: mapStart = (UInt16 *) GetRecordAddress (btreePtr, mapNode.buffer, mapIndex);
440: mapSize = GetRecordSize (btreePtr, mapNode.buffer, mapIndex);
441:
442: if (DEBUG_BUILD && mapSize != M_MapRecordSize (btreePtr->nodeSize) )
443: {
444: Panic ("\pExtendBTree: mapSize != M_MapRecordSize");
445: }
446:
447: mapBits = mapSize << 3; // mapSize (in bytes) * 8
448: recStartBit = totalMapBits; // bit number of first bit in map record
449: totalMapBits += mapBits;
450:
451: bitInRecord = nodeNum - recStartBit;
452: }
453:
454: mapPos = mapStart + ((nodeNum - recStartBit) >> 4);
455: bitInWord = 15 - ((nodeNum - recStartBit) & 0x0000000F);
456: M_SetBitNum (*mapPos, bitInWord);
457:
458: ++nodeNum;
459:
460: } while (nodeNum <= lastNewMapNodeNum);
461:
462: err = UpdateNode (btreePtr, &mapNode);
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; //�� 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)->type != kMapNode)
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)->type != kHeaderNode)
549: {
550: err = fsBTInvalidHeaderErr; //�� 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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.