![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to BTreeWrapper.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 / Misc|
Return to BTreeWrapper.c CVS log | Up to [Apple XNU] / XNU / bsd / hfs / hfscommon / Misc |
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: BTreeWrapper.c
24:
25: Contains: Interface glue for new B-tree manager.
26:
27: Version: HFS Plus 1.0
28:
29: Copyright: � 1996-1998 by Apple Computer, Inc., all rights reserved.
30:
31: File Ownership:
32:
33: DRI: Don Brady
34:
35: Other Contact: Mark Day
36:
37: Technology: xxx put technology here xxx
38:
39: Writers:
40:
41: (msd) Mark Day
42: (DSH) Deric Horn
43: (djb) Don Brady
44:
45: Change History (most recent first):
46: <MacOSX> 8/10/98 djb Removed all references to btcb global iterator (lastIterator).
47: <MacOSX> 04/02/98 djb GetBTreeRecord is only used for MacOS builds.
48: <MacOSX> 03/31/98 djb Sync up with final HFSVolumes.h header file.
49: <CS18> 9/4/97 msd Fix ValidHFSRecord to determine the type of B-tree by FileID,
50: not record size. Add better checking for attribute b-tree keys.
51: <CS17> 8/22/97 djb Get blockReadFromDisk flag from GetCacheBlock call.
52: <CS16> 8/14/97 djb Remove reserved field checks in ValidHFSRecord (radar #1649593).
53: Only call if ValidHFSRecord HFS_DIAGNOSTIC is true.
54: <CS15> 8/11/97 djb Bug 1670441. In SetEndOfForkProc, don't DebugStr if the disk is
55: full.
56: <CS14> 7/25/97 DSH Pass heuristicHint to BTSearchRecord from SearchBTreeRecord.
57: <CS13> 7/24/97 djb CallBackProcs now take a file refNum instead of an FCB.
58: GetBlockProc now reports if block came from disk.
59: <CS12> 7/22/97 djb Move all trace points to BTree.c file.
60: <CS11> 7/21/97 djb LogEndTime now takes an error code.
61: <CS10> 7/16/97 DSH FilesInternal.x -> FileMgrInternal.x to avoid name collision
62: <CS9> 7/15/97 msd Bug #1664103. OpenBTree is not propagating errors from
63: BTOpenPath.
64: <CS8> 7/9/97 djb Remove maxCNID check from ValidHFSRecord (radar #1649593).
65: <CS7> 6/13/97 djb In ValidHFSRecord HFSPlus threads names can be > 31 chars.
66: <CS6> 6/2/97 DSH Also flush AlternateVolumeHeader whenever Attributes or Startup
67: files change size.
68: <CS5> 5/28/97 msd In ValidHFSRecord, check for attribute keys.
69: <CS4> 5/19/97 djb Move summary traces from GetBTreeRecord to BTIterateRecord.
70: <CS3> 5/9/97 djb Get in sync with new FilesInternal.i.
71: <CS2> 5/7/97 djb Add summary traces to B-tree SPI.
72: <CS1> 4/24/97 djb first checked in
73: <HFS18> 4/16/97 djb Always use new B-tree code.
74: <HFS17> 4/4/97 djb Remove clumpSize test from ValidHFSRecord.
75: <HFS16> 4/4/97 djb Get in sync with volume format changes.
76: <HFS15> 3/17/97 DSH Casting for SC, BlockProcs are now not static.
77: <HFS14> 3/3/97 djb Call trash block after closing btree!
78: <HFS13> 2/19/97 djb Add support for accessing bigger B-tree nodes.
79: <HFS12> 2/6/97 msd In CheckBTreeKey, remove test and DebugStr for parent ID being
80: too big.
81: <HFS11> 1/23/97 DSH SetEndOfForkProc now calls through to update the Alternate MDB
82: or VolumeHeader.
83: <HFS10> 1/16/97 djb Switched to dynamic lengths for BufferDescriptor length field in
84: SearchBTreeRecord and GetBTreeRecord. Round up to clump size in
85: SetEndOfForkProc.
86: <HFS9> 1/15/97 djb Don't return errors for bad file ids in key.
87: <HFS8> 1/13/97 djb Adding support for getting current record. ValidHFSRecord now
88: supports variable sized thread records.
89: <HFS7> 1/9/97 djb Call CheckBTreeKey before using key length in a BlockMoveData
90: call.
91: <HFS6> 1/6/97 djb Implement SetEndOfForkProc.
92: <HFS5> 1/6/97 djb Added HFS Plus support to CheckBTreeKey and ValidHFSRecord.
93: <HFS4> 1/3/97 djb Added support for large keys. Integrated latest HFSVolumesPriv.h
94: changes.
95: <HFS3> 12/23/96 djb Fixed problem in SearchBTreeRecord (dataSize is an output so it
96: was undefined). Added some debugging code.
97: <HFS2> 12/20/96 msd Fix OpenBTree to use the real data type for the key compare proc
98: pointer (not void *). Fixed problem in SearchBTreeRecord that
99: assigns a pointer to a buffer size field (forgot to dereference
100: the pointer).
101: <HFS1> 12/19/96 djb first checked in
102:
103: */
104:
105: #include "../headers/BTreesPrivate.h"
106:
107:
108:
109:
110: // B-tree callbacks...
111: #if TARGET_API_MAC_OS8
112: OSStatus GetBlockProc ( FileReference fileRefNum, UInt32 blockNum, GetBlockOptions options, BlockDescriptor *block );
113: OSStatus ReleaseBlockProc ( FileReference fileRefNum, BlockDescPtr blockPtr, ReleaseBlockOptions options );
114: OSStatus SetBlockSizeProc ( FileReference fileRefNum, ByteCount blockSize, ItemCount minBlockCount );
115: #endif
116:
117:
118: // local routines
119: static OSErr CheckBTreeKey(const BTreeKey *key, const BTreeControlBlock *btcb);
120: static Boolean ValidHFSRecord(const void *record, const BTreeControlBlock *btcb, UInt16 recordSize);
121:
122:
123:
124:
125: OSErr SearchBTreeRecord(FileReference refNum, const void* key, UInt32 hint, void* foundKey, void* data, UInt16 *dataSize, UInt32 *newHint)
126: {
127: FSBufferDescriptor btRecord;
128: BTreeIterator searchIterator;
129: FCB *fcb;
130: BTreeControlBlock *btcb;
131: OSStatus result;
132:
133:
134: fcb = GetFileControlBlock(refNum);
135: btcb = (BTreeControlBlock*) fcb->fcbBTCBPtr;
136:
137: btRecord.bufferAddress = data;
138: btRecord.itemCount = 1;
139: if ( btcb->maxKeyLength == kHFSExtentKeyMaximumLength )
140: btRecord.itemSize = sizeof(HFSExtentRecord);
141: else if ( btcb->maxKeyLength == kHFSPlusExtentKeyMaximumLength )
142: btRecord.itemSize = sizeof(HFSPlusExtentRecord);
143: else
144: btRecord.itemSize = sizeof(CatalogRecord);
145:
146: searchIterator.hint.writeCount = 0; // clear these out for debugging...
147: searchIterator.hint.reserved1 = 0;
148: searchIterator.hint.reserved2 = 0;
149:
150: searchIterator.hint.nodeNum = hint;
151: searchIterator.hint.index = 0;
152:
153: result = CheckBTreeKey((BTreeKey *) key, btcb);
154: ExitOnError(result);
155:
156: BlockMoveData(key, &searchIterator.key, CalcKeySize(btcb, (BTreeKey *) key)); //�� should we range check against maxkeylen?
157:
158: // We only optimize for catalog records
159: if( btRecord.itemSize == sizeof(CatalogRecord) )
160: {
161: UInt32 heuristicHint;
162: UInt32 *cachedHint;
163: Ptr hintCachePtr = FCBTOVCB(fcb)->hintCachePtr;
164:
165: // We pass a 2nd hint/guess into BTSearchRecord. The heuristicHint is a mapping of
166: // dirID and nodeNumber, in hopes that the current search will be in the same node
167: // as the last search with the same parentID.
168: result = GetMRUCacheBlock( ((HFSCatalogKey *)key)->parentID, hintCachePtr, (Ptr *)&cachedHint );
169: heuristicHint = (result == noErr) ? *cachedHint : kInvalidMRUCacheKey;
170:
171: result = BTSearchRecord( fcb, &searchIterator, heuristicHint, &btRecord, dataSize, &searchIterator );
172:
173: InsertMRUCacheBlock( hintCachePtr, ((HFSCatalogKey *)key)->parentID, (Ptr) &(searchIterator.hint.nodeNum) );
174: }
175: else
176: {
177: result = BTSearchRecord( fcb, &searchIterator, kInvalidMRUCacheKey, &btRecord, dataSize, &searchIterator );
178: }
179:
180: if (result == noErr)
181: {
182: *newHint = searchIterator.hint.nodeNum;
183:
184: result = CheckBTreeKey(&searchIterator.key, btcb);
185: ExitOnError(result);
186:
187: BlockMoveData(&searchIterator.key, foundKey, CalcKeySize(btcb, &searchIterator.key)); //�� warning, this could overflow user's buffer!!!
188:
189: if ( DEBUG_BUILD && !ValidHFSRecord(data, btcb, *dataSize) )
190: DebugStr("\pSearchBTreeRecord: bad record?");
191: }
192:
193: ErrorExit:
194:
195: return result;
196: }
197:
198:
199:
200: OSErr InsertBTreeRecord(FileReference refNum, void* key, void* data, UInt16 dataSize, UInt32 *newHint)
201: {
202: FSBufferDescriptor btRecord;
203: BTreeIterator iterator;
204: FCB *fcb;
205: BTreeControlBlock *btcb;
206: OSStatus result;
207:
208:
209: fcb = GetFileControlBlock(refNum);
210: btcb = (BTreeControlBlock*) fcb->fcbBTCBPtr;
211:
212: btRecord.bufferAddress = data;
213: btRecord.itemSize = dataSize;
214: btRecord.itemCount = 1;
215:
216: iterator.hint.nodeNum = 0; // no hint
217:
218: result = CheckBTreeKey((BTreeKey *) key, btcb);
219: ExitOnError(result);
220:
221: BlockMoveData(key, &iterator.key, CalcKeySize(btcb, (BTreeKey *) key)); //�� should we range check against maxkeylen?
222:
223: if ( DEBUG_BUILD && !ValidHFSRecord(data, btcb, dataSize) )
224: DebugStr("\pInsertBTreeRecord: bad record?");
225:
226: result = BTInsertRecord( fcb, &iterator, &btRecord, dataSize );
227:
228: *newHint = iterator.hint.nodeNum;
229:
230: ErrorExit:
231:
232: return result;
233: }
234:
235:
236: OSErr DeleteBTreeRecord(FileReference refNum, void* key)
237: {
238: BTreeIterator iterator;
239: FCB *fcb;
240: BTreeControlBlock *btcb;
241: OSStatus result;
242:
243:
244: fcb = GetFileControlBlock(refNum);
245: btcb = (BTreeControlBlock*) fcb->fcbBTCBPtr;
246:
247: iterator.hint.nodeNum = 0; // no hint
248:
249: result = CheckBTreeKey((BTreeKey *) key, btcb);
250: ExitOnError(result);
251:
252: BlockMoveData(key, &iterator.key, CalcKeySize(btcb, (BTreeKey *) key)); //�� should we range check against maxkeylen?
253:
254: result = BTDeleteRecord( fcb, &iterator );
255:
256: ErrorExit:
257:
258: return result;
259: }
260:
261:
262: OSErr ReplaceBTreeRecord(FileReference refNum, const void* key, UInt32 hint, void *newData, UInt16 dataSize, UInt32 *newHint)
263: {
264: FSBufferDescriptor btRecord;
265: BTreeIterator iterator;
266: FCB *fcb;
267: BTreeControlBlock *btcb;
268: OSStatus result;
269:
270:
271: fcb = GetFileControlBlock(refNum);
272: btcb = (BTreeControlBlock*) fcb->fcbBTCBPtr;
273:
274: btRecord.bufferAddress = newData;
275: btRecord.itemSize = dataSize;
276: btRecord.itemCount = 1;
277:
278: iterator.hint.nodeNum = hint;
279:
280: result = CheckBTreeKey((BTreeKey *) key, btcb);
281: ExitOnError(result);
282:
283: BlockMoveData(key, &iterator.key, CalcKeySize(btcb, (BTreeKey *) key)); //�� should we range check against maxkeylen?
284:
285: if ( DEBUG_BUILD && !ValidHFSRecord(newData, btcb, dataSize) )
286: DebugStr("\pReplaceBTreeRecord: bad record?");
287:
288: result = BTReplaceRecord( fcb, &iterator, &btRecord, dataSize );
289:
290: *newHint = iterator.hint.nodeNum;
291:
292: //���do we need to invalidate the iterator?
293:
294: ErrorExit:
295:
296: return result;
297: }
298:
299:
300:
301: static OSErr CheckBTreeKey(const BTreeKey *key, const BTreeControlBlock *btcb)
302: {
303: UInt16 keyLen;
304:
305: if ( btcb->attributes & kBTBigKeysMask )
306: keyLen = key->length16;
307: else
308: keyLen = key->length8;
309:
310: if ( (keyLen < 6) || (keyLen > btcb->maxKeyLength) )
311: {
312: if ( DEBUG_BUILD )
313: DebugStr("\pCheckBTreeKey: bad key length!");
314: return fsBTInvalidKeyLengthErr;
315: }
316:
317: return noErr;
318: }
319:
320:
321: static Boolean ValidHFSRecord(const void *record, const BTreeControlBlock *btcb, UInt16 recordSize)
322: {
323: UInt32 cNodeID;
324:
325: if ( btcb->maxKeyLength == kHFSExtentKeyMaximumLength )
326: {
327: return ( recordSize == sizeof(HFSExtentRecord) );
328: }
329: else if (btcb->maxKeyLength == kHFSPlusExtentKeyMaximumLength )
330: {
331: return ( recordSize == sizeof(HFSPlusExtentRecord) );
332: }
333: else // Catalog record
334: {
335: CatalogRecord *catalogRecord = (CatalogRecord*) record;
336:
337: switch(catalogRecord->recordType)
338: {
339: case kHFSFolderRecord:
340: {
341: if ( recordSize != sizeof(HFSCatalogFolder) )
342: return false;
343: if ( catalogRecord->hfsFolder.flags != 0 )
344: return false;
345: if ( catalogRecord->hfsFolder.valence > 0x7FFF )
346: return false;
347:
348: cNodeID = catalogRecord->hfsFolder.folderID;
349:
350: if ( (cNodeID == 0) || (cNodeID < 16 && cNodeID > 2) )
351: return false;
352: }
353: break;
354:
355: case kHFSPlusFolderRecord:
356: {
357: if ( recordSize != sizeof(HFSPlusCatalogFolder) )
358: return false;
359: if ( catalogRecord->hfsPlusFolder.flags != 0 )
360: return false;
361: if ( catalogRecord->hfsPlusFolder.valence > 0x7FFF )
362: return false;
363:
364: cNodeID = catalogRecord->hfsPlusFolder.folderID;
365:
366: if ( (cNodeID == 0) || (cNodeID < 16 && cNodeID > 2) )
367: return false;
368: }
369: break;
370:
371: case kHFSFileRecord:
372: {
373: // UInt16 i;
374: HFSExtentDescriptor *dataExtent;
375: HFSExtentDescriptor *rsrcExtent;
376:
377: if ( recordSize != sizeof(HFSCatalogFile) )
378: return false;
379: if ( (catalogRecord->hfsFile.flags & ~(0x83)) != 0 )
380: return false;
381:
382: cNodeID = catalogRecord->hfsFile.fileID;
383:
384: if ( cNodeID < 16 )
385: return false;
386:
387: // make sure 0 � LEOF � PEOF for both forks
388:
389: if ( catalogRecord->hfsFile.dataLogicalSize < 0 )
390: return false;
391: if ( catalogRecord->hfsFile.dataPhysicalSize < catalogRecord->hfsFile.dataLogicalSize )
392: return false;
393: if ( catalogRecord->hfsFile.rsrcLogicalSize < 0 )
394: return false;
395: if ( catalogRecord->hfsFile.rsrcPhysicalSize < catalogRecord->hfsFile.rsrcLogicalSize )
396: return false;
397:
398: dataExtent = (HFSExtentDescriptor*) &catalogRecord->hfsFile.dataExtents;
399: rsrcExtent = (HFSExtentDescriptor*) &catalogRecord->hfsFile.rsrcExtents;
400:
401: #if 0
402: for (i = 0; i < kHFSExtentDensity; ++i)
403: {
404: if ( (dataExtent[i].blockCount > 0) && (dataExtent[i].startBlock == 0) )
405: return false;
406: if ( (rsrcExtent[i].blockCount > 0) && (rsrcExtent[i].startBlock == 0) )
407: return false;
408: }
409: #endif
410: }
411: break;
412:
413: case kHFSPlusFileRecord:
414: {
415: // UInt16 i;
416: HFSPlusExtentDescriptor *dataExtent;
417: HFSPlusExtentDescriptor *rsrcExtent;
418:
419: if ( recordSize != sizeof(HFSPlusCatalogFile) )
420: return false;
421: if ( (catalogRecord->hfsPlusFile.flags & ~(0x83)) != 0 )
422: return false;
423:
424: cNodeID = catalogRecord->hfsPlusFile.fileID;
425:
426: if ( cNodeID < 16 )
427: return false;
428:
429: // make sure 0 � LEOF � PEOF for both forks
430:
431: dataExtent = (HFSPlusExtentDescriptor*) &catalogRecord->hfsPlusFile.dataFork.extents;
432: rsrcExtent = (HFSPlusExtentDescriptor*) &catalogRecord->hfsPlusFile.resourceFork.extents;
433:
434: #if 0
435: for (i = 0; i < kHFSPlusExtentDensity; ++i)
436: {
437: if ( (dataExtent[i].blockCount > 0) && (dataExtent[i].startBlock == 0) )
438: return false;
439: if ( (rsrcExtent[i].blockCount > 0) && (rsrcExtent[i].startBlock == 0) )
440: return false;
441: }
442: #endif
443: }
444: break;
445:
446: case kHFSFolderThreadRecord:
447: case kHFSFileThreadRecord:
448: {
449: if ( recordSize != sizeof(HFSCatalogThread) )
450: return false;
451:
452: cNodeID = catalogRecord->hfsThread.parentID;
453: if ( (cNodeID == 0) || (cNodeID < 16 && cNodeID > 2) )
454: return false;
455:
456: if ( (catalogRecord->hfsThread.nodeName[0] == 0) ||
457: (catalogRecord->hfsThread.nodeName[0] > 31) )
458: return false;
459: }
460: break;
461:
462: case kHFSPlusFolderThreadRecord:
463: case kHFSPlusFileThreadRecord:
464: {
465: if ( recordSize > sizeof(HFSPlusCatalogThread) || recordSize < (sizeof(HFSPlusCatalogThread) - sizeof(HFSUniStr255)))
466: return false;
467:
468: cNodeID = catalogRecord->hfsPlusThread.parentID;
469: if ( (cNodeID == 0) || (cNodeID < 16 && cNodeID > 2) )
470: return false;
471:
472: if ( (catalogRecord->hfsPlusThread.nodeName.length == 0) ||
473: (catalogRecord->hfsPlusThread.nodeName.length > 255) )
474: return false;
475: }
476: break;
477:
478: default:
479: return false;
480: }
481: }
482:
483: return true; // record appears to be OK
484: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.