]> git.saurik.com Git - apple/hfs.git/blob - fsck_hfs/dfalib/BTreeAllocate.c
projects / apple / hfs.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
hfs-556.41.1.tar.gz
[apple/hfs.git] / fsck_hfs / dfalib / BTreeAllocate.c
1 /*
2 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
11 * file.
12 *
13 * The Original Code and all software distributed under the License are
14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
20 *
21 * @APPLE_LICENSE_HEADER_END@
22 */
23 /*
24 File: BTreeAllocate.c
25
26 Contains: BTree Node Allocation routines for the BTree Module.
27
28 Version: xxx put the technology version here xxx
29
30 Written by: Gordon Sheridan and Bill Bruffey
31
32 Copyright: © 1992-1999 by Apple Computer, Inc., all rights reserved.
33 */
34
35 #include "BTreePrivate.h"
36 #include "hfs_endian.h"
37
38 ///////////////////// Routines Internal To BTreeAllocate.c //////////////////////
39
40 OSStatus GetMapNode (BTreeControlBlockPtr btreePtr,
41 BlockDescriptor *nodePtr,
42 UInt16 **mapPtr,
43 UInt16 *mapSize );
44
45 /////////////////////////////////////////////////////////////////////////////////
46
47 /*-------------------------------------------------------------------------------
48
49 Routine: AllocateNode - Find Free Node, Mark It Used, and Return Node Number.
50
51 Function: Searches the map records for the first free node, marks it "in use" and
52 returns the node number found. This routine should really only be called
53 when we know there are free blocks, otherwise it's just a waste of time.
54
55 Note: We have to examine map nodes a word at a time rather than a long word
56 because the External BTree Mgr used map records that were not an integral
57 number of long words. Too bad. In our spare time could develop a more
58 sophisticated algorithm that read map records by long words (and long
59 word aligned) and handled the spare bytes at the beginning and end
60 appropriately.
61
62 Input: btreePtr - pointer to control block for BTree file
63
64 Output: nodeNum - number of node allocated
65
66
67 Result: noErr - success
68 fsBTNoMoreMapNodesErr - no free blocks were found
69 != noErr - failure
70 -------------------------------------------------------------------------------*/
71
72 OSStatus AllocateNode (BTreeControlBlockPtr btreePtr, UInt32 *nodeNum)
73 {
74 OSStatus err;
75 BlockDescriptor node;
76 UInt16 *mapPtr, *pos;
77 UInt16 mapSize, size;
78 UInt16 freeWord;
79 UInt16 mask;
80 UInt16 bitOffset;
81 UInt32 nodeNumber;
82
83
84 nodeNumber = 0; // first node number of header map record
85 node.buffer = nil; // clear node.buffer to get header node
86 // - and for ErrorExit
87
88 while (true)
89 {
90 err = GetMapNode (btreePtr, &node, &mapPtr, &mapSize);
91 M_ExitOnError (err);
92
93 //////////////////////// Find Word with Free Bit ////////////////////////////
94
95 pos = mapPtr;
96 size = mapSize;
97 size >>= 1; // convert to number of words
98 //¥¥ assumes mapRecords contain an integral number of words
99
100 while ( size-- )
101 {
102 if ( *pos++ != 0xFFFF ) // assume test fails, and increment pos
103 break;
104 }
105
106 --pos; // whoa! backup
107
108 if (*pos != 0xFFFF) // hey, we got one!
109 break;
110
111 nodeNumber += mapSize << 3; // covert to number of bits (nodes)
112 }
113
114 ///////////////////////// Find Free Bit in Word /////////////////////////////
115
116 freeWord = SWAP_BE16 (*pos);
117 bitOffset = 15;
118 mask = 0x8000;
119
120 do {
121 if ( (freeWord & mask) == 0)
122 break;
123 mask >>= 1;
124 } while (--bitOffset);
125
126 ////////////////////// Calculate Free Node Number ///////////////////////////
127
128 nodeNumber += ((pos - mapPtr) << 4) + (15 - bitOffset); // (pos-mapPtr) = # of words!
129
130
131 ///////////////////////// Check for End of Map //////////////////////////////
132
133 if (nodeNumber >= btreePtr->totalNodes)
134 {
135 err = fsBTFullErr;
136 goto ErrorExit;
137 }
138
139 /////////////////////////// Allocate the Node ///////////////////////////////
140
141 *pos |= SWAP_BE16 (mask); // set the map bit for the node
142
143 err = UpdateNode (btreePtr, &node);
144 M_ExitOnError (err);
145
146 --btreePtr->freeNodes;
147 btreePtr->flags |= kBTHeaderDirty;
148 *nodeNum = nodeNumber;
149
150 return noErr;
151
152 ////////////////////////////////// Error Exit ///////////////////////////////////
153
154 ErrorExit:
155
156 (void) ReleaseNode (btreePtr, &node);
157 *nodeNum = 0;
158
159 return err;
160 }
161
162
163
164 /*-------------------------------------------------------------------------------
165
166 Routine: FreeNode - Clear allocation bit for node.
167
168 Function: Finds the bit representing the node specified by nodeNum in the node
169 map and clears the bit.
170
171
172 Input: btreePtr - pointer to control block for BTree file
173 nodeNum - number of node to mark free
174
175 Output: none
176
177 Result: noErr - success
178 fsBTNoMoreMapNodesErr - node number is beyond end of node map
179 != noErr - GetNode or ReleaseNode encountered some difficulty
180 -------------------------------------------------------------------------------*/
181
182 OSStatus FreeNode (BTreeControlBlockPtr btreePtr, UInt32 nodeNum)
183 {
184 OSStatus err;
185 BlockDescriptor node;
186 UInt32 nodeIndex;
187 UInt16 mapSize;
188 UInt16 *mapPos;
189 UInt16 bitOffset;
190
191
192 //////////////////////////// Find Map Record ////////////////////////////////
193 nodeIndex = 0; // first node number of header map record
194 node.buffer = nil; // invalidate node.buffer to get header node
195
196 while (nodeNum >= nodeIndex)
197 {
198 err = GetMapNode (btreePtr, &node, &mapPos, &mapSize);
199 M_ExitOnError (err);
200
201 nodeIndex += mapSize << 3; // covert to number of bits (nodes)
202 }
203
204 //////////////////////////// Mark Node Free /////////////////////////////////
205
206 nodeNum -= (nodeIndex - (mapSize << 3)); // relative to this map record
207 bitOffset = 15 - (nodeNum & 0x0000000F); // last 4 bits are bit offset
208 mapPos += nodeNum >> 4; // point to word containing map bit
209 M_SWAP_BE16_ClearBitNum (*mapPos, bitOffset); // clear it
210
211 err = UpdateNode (btreePtr, &node);
212 M_ExitOnError (err);
213
214
215 ++btreePtr->freeNodes;
216 btreePtr->flags |= kBTHeaderDirty; //¥¥ how about a macro for this
217
218 return noErr;
219
220 ErrorExit:
221
222 (void) ReleaseNode (btreePtr, &node);
223
224 return err;
225 }
226
227
228
229 /*-------------------------------------------------------------------------------
230
231 Routine: ExtendBTree - Call FSAgent to extend file, and allocate necessary map nodes.
232
233 Function: This routine calls the the FSAgent to extend the end of fork, if necessary,
234 to accomodate the number of nodes requested. It then allocates as many
235 map nodes as are necessary to account for all the nodes in the B*Tree.
236 If newTotalNodes is less than the current number of nodes, no action is
237 taken.
238
239 Note: Internal HFS File Manager BTree Module counts on an integral number of
240 long words in map records, although they are not long word aligned.
241
242 Input: btreePtr - pointer to control block for BTree file
243 newTotalNodes - total number of nodes the B*Tree is to extended to
244
245 Output: none
246
247 Result: noErr - success
248 != noErr - failure
249 -------------------------------------------------------------------------------*/
250
251 OSStatus ExtendBTree (BTreeControlBlockPtr btreePtr,
252 UInt32 newTotalNodes )
253 {
254 OSStatus err;
255 SFCB *filePtr;
256 FSSize minEOF, maxEOF;
257 UInt16 nodeSize;
258 UInt32 oldTotalNodes;
259 UInt32 newMapNodes;
260 UInt32 mapBits, totalMapBits;
261 UInt32 recStartBit;
262 UInt32 nodeNum, nextNodeNum;
263 UInt32 firstNewMapNodeNum, lastNewMapNodeNum;
264 BlockDescriptor mapNode, newNode;
265 UInt16 *mapPos;
266 UInt16 *mapStart;
267 UInt16 mapSize;
268 UInt16 mapNodeRecSize;
269 UInt32 bitInWord, bitInRecord;
270 UInt16 mapIndex;
271
272
273 oldTotalNodes = btreePtr->totalNodes;
274 if (newTotalNodes <= oldTotalNodes) // we're done!
275 return noErr;
276
277 nodeSize = btreePtr->nodeSize;
278 filePtr = btreePtr->fcbPtr;
279
280 mapNode.buffer = nil;
281 newNode.buffer = nil;
282
283 mapNodeRecSize = nodeSize - sizeof(BTNodeDescriptor) - 6; // 2 bytes of free space (see note)
284
285 //¥¥ update for proper 64 bit arithmetic!!
286
287
288 //////////////////////// Count Bits In Node Map /////////////////////////////
289
290 totalMapBits = 0;
291 do {
292 err = GetMapNode (btreePtr, &mapNode, &mapStart, &mapSize);
293 M_ExitOnError (err);
294
295 mapBits = mapSize << 3; // mapSize (in bytes) * 8
296 recStartBit = totalMapBits; // bit number of first bit in map record
297 totalMapBits += mapBits;
298
299 } while ( ((BTNodeDescriptor*)mapNode.buffer)->fLink != 0 );
300
301 if (DEBUG_BUILD && totalMapBits != CalcMapBits (btreePtr))
302 Panic ("\pExtendBTree: totalMapBits != CalcMapBits");
303
304 /////////////////////// Extend LEOF If Necessary ////////////////////////////
305
306 minEOF = (UInt64)newTotalNodes * (UInt64)nodeSize;
307 if ( filePtr->fcbLogicalSize < minEOF )
308 {
309 maxEOF = 0xFFFFFFFFFFFFFFFFULL;
310
311 err = btreePtr->setEndOfForkProc (btreePtr->fcbPtr, minEOF, maxEOF);
312 M_ExitOnError (err);
313 }
314
315
316 //////////////////// Calc New Total Number Of Nodes /////////////////////////
317
318 newTotalNodes = (UInt32)(filePtr->fcbLogicalSize / nodeSize); //¥¥ hack!
319 //¥¥ do we wish to perform any verification of newTotalNodes at this point?
320
321 btreePtr->totalNodes = newTotalNodes; //¥¥ do we need to update freeNodes here too?
322
323
324 ////////////// Calculate Number Of New Map Nodes Required ///////////////////
325
326 newMapNodes = 0;
327 if (newTotalNodes > totalMapBits)
328 {
329 newMapNodes = (((newTotalNodes - totalMapBits) >> 3) / mapNodeRecSize) + 1;
330 firstNewMapNodeNum = oldTotalNodes;
331 lastNewMapNodeNum = firstNewMapNodeNum + newMapNodes - 1;
332 }
333 else
334 {
335 err = ReleaseNode (btreePtr, &mapNode);
336 M_ExitOnError (err);
337
338 goto Success;
339 }
340
341
342 /////////////////////// Initialize New Map Nodes ////////////////////////////
343
344 ((BTNodeDescriptor*)mapNode.buffer)->fLink = firstNewMapNodeNum;
345
346 nodeNum = firstNewMapNodeNum;
347 while (true)
348 {
349 err = GetNewNode (btreePtr, nodeNum, &newNode);
350 M_ExitOnError (err);
351
352 ((NodeDescPtr)newNode.buffer)->numRecords = 1;
353 ((NodeDescPtr)newNode.buffer)->kind = kBTMapNode;
354
355 // set free space offset
356 *(UInt16 *)((Ptr)newNode.buffer + nodeSize - 4) = nodeSize - 6;
357
358 if (nodeNum++ == lastNewMapNodeNum)
359 break;
360
361 ((BTNodeDescriptor*)newNode.buffer)->fLink = nodeNum; // point to next map node
362
363 err = UpdateNode (btreePtr, &newNode);
364 M_ExitOnError (err);
365 }
366
367 err = UpdateNode (btreePtr, &newNode);
368 M_ExitOnError (err);
369
370
371 ///////////////////// Mark New Map Nodes Allocated //////////////////////////
372
373 nodeNum = firstNewMapNodeNum;
374 do {
375 bitInRecord = nodeNum - recStartBit;
376
377 while (bitInRecord >= mapBits)
378 {
379 nextNodeNum = ((NodeDescPtr)mapNode.buffer)->fLink;
380 if ( nextNodeNum == 0)
381 {
382 err = fsBTNoMoreMapNodesErr;
383 goto ErrorExit;
384 }
385
386 err = UpdateNode (btreePtr, &mapNode);
387 M_ExitOnError (err);
388
389 err = GetNode (btreePtr, nextNodeNum, &mapNode);
390 M_ExitOnError (err);
391
392 mapIndex = 0;
393
394 mapStart = (UInt16 *) GetRecordAddress (btreePtr, mapNode.buffer, mapIndex);
395 mapSize = GetRecordSize (btreePtr, mapNode.buffer, mapIndex);
396
397 if (DEBUG_BUILD && mapSize != M_MapRecordSize (btreePtr->nodeSize) )
398 {
399 Panic ("\pExtendBTree: mapSize != M_MapRecordSize");
400 }
401
402 mapBits = mapSize << 3; // mapSize (in bytes) * 8
403 recStartBit = totalMapBits; // bit number of first bit in map record
404 totalMapBits += mapBits;
405
406 bitInRecord = nodeNum - recStartBit;
407 }
408
409 mapPos = mapStart + ((nodeNum - recStartBit) >> 4);
410 bitInWord = 15 - ((nodeNum - recStartBit) & 0x0000000F);
411 M_SWAP_BE16_SetBitNum (*mapPos, bitInWord);
412
413 ++nodeNum;
414
415 } while (nodeNum <= lastNewMapNodeNum);
416
417 err = UpdateNode (btreePtr, &mapNode);
418 M_ExitOnError (err);
419
420
421 //////////////////////////////// Success ////////////////////////////////////
422
423 Success:
424
425 btreePtr->totalNodes = newTotalNodes;
426 btreePtr->freeNodes += (newTotalNodes - oldTotalNodes) - newMapNodes;
427
428 btreePtr->flags |= kBTHeaderDirty; //¥¥ how about a macro for this
429
430 return noErr;
431
432
433 ////////////////////////////// Error Exit ///////////////////////////////////
434
435 ErrorExit:
436
437 (void) ReleaseNode (btreePtr, &mapNode);
438 (void) ReleaseNode (btreePtr, &newNode);
439
440 return err;
441 }
442
443
444
445 /*-------------------------------------------------------------------------------
446
447 Routine: GetMapNode - Get the next map node and pointer to the map record.
448
449 Function: Given a BlockDescriptor to a map node in nodePtr, GetMapNode releases
450 it and gets the next node. If nodePtr->buffer is nil, then the header
451 node is retrieved.
452
453
454 Input: btreePtr - pointer to control block for BTree file
455 nodePtr - pointer to a BlockDescriptor of a map node
456
457 Output: nodePtr - pointer to the BlockDescriptor for the next map node
458 mapPtr - pointer to the map record within the map node
459 mapSize - number of bytes in the map record
460
461 Result: noErr - success
462 fsBTNoMoreMapNodesErr - we've run out of map nodes
463 fsBTInvalidNodeErr - bad node, or not node type kMapNode
464 != noErr - failure
465 -------------------------------------------------------------------------------*/
466
467 OSStatus GetMapNode (BTreeControlBlockPtr btreePtr,
468 BlockDescriptor *nodePtr,
469 UInt16 **mapPtr,
470 UInt16 *mapSize )
471 {
472 OSStatus err;
473 UInt16 mapIndex;
474 UInt32 nextNodeNum;
475
476 if (nodePtr->buffer != nil) // if iterator is valid...
477 {
478 nextNodeNum = ((NodeDescPtr)nodePtr->buffer)->fLink;
479 if (nextNodeNum == 0)
480 {
481 err = fsBTNoMoreMapNodesErr;
482 goto ErrorExit;
483 }
484
485 err = ReleaseNode (btreePtr, nodePtr);
486 M_ExitOnError (err);
487
488 err = GetNode (btreePtr, nextNodeNum, nodePtr);
489 M_ExitOnError (err);
490
491 if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTMapNode)
492 {
493 err = fsBTBadNodeType;
494 goto ErrorExit;
495 }
496
497 ++btreePtr->numMapNodesRead;
498 mapIndex = 0;
499 } else {
500 err = GetNode (btreePtr, kHeaderNodeNum, nodePtr);
501 M_ExitOnError (err);
502
503 if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTHeaderNode)
504 {
505 err = fsBTInvalidHeaderErr; //¥¥ or fsBTBadNodeType
506 goto ErrorExit;
507 }
508
509 mapIndex = 2;
510 }
511
512
513 *mapPtr = (UInt16 *) GetRecordAddress (btreePtr, nodePtr->buffer, mapIndex);
514 *mapSize = GetRecordSize (btreePtr, nodePtr->buffer, mapIndex);
515
516 return noErr;
517
518
519 ErrorExit:
520
521 (void) ReleaseNode (btreePtr, nodePtr);
522
523 *mapPtr = nil;
524 *mapSize = 0;
525
526 return err;
527 }
528
529
530
531 ////////////////////////////////// CalcMapBits //////////////////////////////////
532
533 UInt32 CalcMapBits (BTreeControlBlockPtr btreePtr)
534 {
535 UInt32 mapBits;
536
537 mapBits = (UInt32)(M_HeaderMapRecordSize (btreePtr->nodeSize) << 3);
538
539 while (mapBits < btreePtr->totalNodes)
540 mapBits += M_MapRecordSize (btreePtr->nodeSize) << 3;
541
542 return mapBits;
543 }
mirror of hfs