1 /*
2  * Copyright (c) 1998-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  * Copyright (c) 1998 Apple Computer, Inc.  All rights reserved.
24  *
25  * HISTORY
26  * 23 Nov 98 sdouglas, created from IODeviceTreeBus.m, & MacOS exp mgr.
27  * 05 Apr 99 sdouglas, add interrupt mapping.
28  *
29  */
30 
31 #include <IOKit/IODeviceTreeSupport.h>
32 #include <libkern/c++/OSContainers.h>
33 #include <IOKit/IODeviceMemory.h>
34 #include <IOKit/IOService.h>
35 #include <IOKit/IOCatalogue.h>
36 
37 #include <IOKit/IOLib.h>
38 #include <IOKit/IOKitKeys.h>
39 
40 #include <DeviceTree.h>
41 extern "C" {
42 	#include <machine/machine_routines.h>
43 	void DTInit( void * data );
44 
45 	int IODTGetLoaderInfo( char *key, void **infoAddr, int *infosize );
46 	void IODTFreeLoaderInfo( char *key, void *infoAddr, int infoSize );
47 }
48 
49 #include <IOKit/assert.h>
50 
51 #define IODTSUPPORTDEBUG 0
52 
53 const IORegistryPlane * gIODTPlane;
54 
55 static OSArray *	gIODTPHandles;
56 static OSArray *	gIODTPHandleMap;
57 
58 const OSSymbol *	gIODTNameKey;
59 const OSSymbol *	gIODTUnitKey;
60 const OSSymbol *	gIODTCompatibleKey;
61 const OSSymbol * 	gIODTTypeKey;
62 const OSSymbol * 	gIODTModelKey;
63 
64 const OSSymbol * 	gIODTSizeCellKey;
65 const OSSymbol * 	gIODTAddressCellKey;
66 const OSSymbol * 	gIODTRangeKey;
67 
68 const OSSymbol *	gIODTPersistKey;
69 
70 const OSSymbol *	gIODTDefaultInterruptController;
71 const OSSymbol *	gIODTAAPLInterruptsKey;
72 const OSSymbol *	gIODTPHandleKey;
73 const OSSymbol *	gIODTInterruptCellKey;
74 const OSSymbol *	gIODTInterruptParentKey;
75 const OSSymbol *	gIODTNWInterruptMappingKey;
76 
77 
78 static IORegistryEntry * MakeReferenceTable( DTEntry dtEntry, bool copy );
79 static void AddPHandle( IORegistryEntry * regEntry );
80 static void FreePhysicalMemory( vm_offset_t * range );
81 
82 IORegistryEntry *
83 IODeviceTreeAlloc( void * dtTop )
84 {
85     IORegistryEntry 	*parent;
86     IORegistryEntry		*child;
87     IORegistryIterator	*regIter;
88     DTEntryIterator		iter;
89     DTEntry				dtChild;
90     DTEntry				mapEntry;
91     OSArray				*stack;
92     OSData				*prop;
93     OSObject			*obj;
94     vm_offset_t			*dtMap;
95     int					propSize;
96     bool				intMap;
97     bool				freeDT;
98 
99     IOLog("IODeviceTreeSupport ");
100 
101     gIODTPlane = IORegistryEntry::makePlane( kIODeviceTreePlane );
102 
103     gIODTNameKey 		= OSSymbol::withCStringNoCopy( "name" );
104     gIODTUnitKey 		= OSSymbol::withCStringNoCopy( "AAPL,unit-string" );
105     gIODTCompatibleKey 	= OSSymbol::withCStringNoCopy( "compatible" );
106     gIODTTypeKey 		= OSSymbol::withCStringNoCopy( "device_type" );
107     gIODTModelKey 		= OSSymbol::withCStringNoCopy( "model" );
108     gIODTSizeCellKey 	= OSSymbol::withCStringNoCopy( "#size-cells" );
109     gIODTAddressCellKey = OSSymbol::withCStringNoCopy( "#address-cells" );
110     gIODTRangeKey 		= OSSymbol::withCStringNoCopy( "ranges" );
111     gIODTPersistKey		= OSSymbol::withCStringNoCopy( "IODTPersist" );
112 
113     assert(    gIODTPlane && gIODTCompatibleKey
114             && gIODTTypeKey && gIODTModelKey
115             && gIODTSizeCellKey && gIODTAddressCellKey && gIODTRangeKey
116             && gIODTPersistKey );
117 
118     gIODTDefaultInterruptController
119 		= OSSymbol::withCStringNoCopy("IOPrimaryInterruptController");
120     gIODTNWInterruptMappingKey
121 		= OSSymbol::withCStringNoCopy("IONWInterrupts");
122 
123     gIODTAAPLInterruptsKey
124 		= OSSymbol::withCStringNoCopy("AAPL,interrupts");
125     gIODTPHandleKey
126 		= OSSymbol::withCStringNoCopy("AAPL,phandle");
127 
128     gIODTInterruptParentKey
129 		= OSSymbol::withCStringNoCopy("interrupt-parent");
130 
131     gIODTPHandles	= OSArray::withCapacity( 1 );
132     gIODTPHandleMap	= OSArray::withCapacity( 1 );
133 
134     gIODTInterruptCellKey
135 		= OSSymbol::withCStringNoCopy("#interrupt-cells");
136 
137     assert(    gIODTDefaultInterruptController && gIODTNWInterruptMappingKey
138 	    && gIODTAAPLInterruptsKey
139 	    && gIODTPHandleKey && gIODTInterruptParentKey
140 	    && gIODTPHandles && gIODTPHandleMap
141             && gIODTInterruptCellKey
142 	 );
143 
144     freeDT = (kSuccess == DTLookupEntry( 0, "/chosen/memory-map", &mapEntry ))
145 	  && (kSuccess == DTGetProperty( mapEntry,
146                 "DeviceTree", (void **) &dtMap, &propSize ))
147 	  && ((2 * sizeof( vm_offset_t)) == propSize);
148 
149     parent = MakeReferenceTable( (DTEntry)dtTop, freeDT );
150 
151     stack = OSArray::withObjects( & (const OSObject *) parent, 1, 10 );
152     DTCreateEntryIterator( (DTEntry)dtTop, &iter );
153 
154     do {
155         parent = (IORegistryEntry *)stack->getObject( stack->getCount() - 1);
156 		//parent->release();
157         stack->removeObject( stack->getCount() - 1);
158 
159         while( kSuccess == DTIterateEntries( iter, &dtChild) ) {
160 
161             child = MakeReferenceTable( dtChild, freeDT );
162             child->attachToParent( parent, gIODTPlane);
163 
164 			AddPHandle( child );
165 
166             if( kSuccess == DTEnterEntry( iter, dtChild)) {
167                 stack->setObject( parent);
168                 parent = child;
169             }
170 	    	// only registry holds retain
171 	    	child->release();
172         }
173 
174     } while( stack->getCount()
175 		&& (kSuccess == DTExitEntry( iter, &dtChild)));
176 
177     stack->release();
178     DTDisposeEntryIterator( iter);
179 
180     // parent is now root of the created tree
181 
182     // make root name first compatible entry (purely cosmetic)
183     if( (prop = (OSData *) parent->getProperty( gIODTCompatibleKey))) {
184 		parent->setName( parent->getName(), gIODTPlane );
185 		parent->setName( (const char *) prop->getBytesNoCopy() );
186     }
187 
188     // attach tree to meta root
189     parent->attachToParent( IORegistryEntry::getRegistryRoot(), gIODTPlane);
190     parent->release();
191 
192     if( freeDT ) {
193 		// free original device tree
194         DTInit(0);
195         IODTFreeLoaderInfo( "DeviceTree",
196 			(void *)dtMap[0], round_page(dtMap[1]) );
197     }
198 
199     // adjust tree
200     intMap = false;
201     regIter = IORegistryIterator::iterateOver( gIODTPlane,
202 						kIORegistryIterateRecursively );
203     assert( regIter );
204     if( regIter) {
205 		while( (child = regIter->getNextObject())) {
206 			IODTMapInterrupts( child );
207 			if( !intMap && child->getProperty( gIODTInterruptParentKey))
208 				intMap = true;
209 
210 			// Look for a "driver,AAPL,MacOSX,PowerPC" property.
211 			if( (obj = child->getProperty( "driver,AAPL,MacOSX,PowerPC"))) {
212 				gIOCatalogue->addExtensionsFromArchive((OSData *)obj);
213 
214 				child->removeProperty( "driver,AAPL,MacOSX,PowerPC");
215 			}
216 
217 			// some gross pruning
218 			child->removeProperty( "lanLib,AAPL,MacOS,PowerPC");
219 
220 			if( (obj = child->getProperty( "driver,AAPL,MacOS,PowerPC"))) {
221 
222 				if( (0 == (prop = (OSData *)child->getProperty( gIODTTypeKey )))
223 					|| (strcmp( "display", (char *) prop->getBytesNoCopy())) ) {
224 					child->removeProperty( "driver,AAPL,MacOS,PowerPC");
225 				}
226 			}
227 		}
228 		regIter->release();
229     }
230 
231     if( intMap)
232 		// set a key in the root to indicate we found NW interrupt mapping
233 		parent->setProperty( gIODTNWInterruptMappingKey,
234 			(OSObject *) gIODTNWInterruptMappingKey );
235 
236     IOLog("done\n");
237 
238     return( parent);
239 }
240 
241 int IODTGetLoaderInfo( char *key, void **infoAddr, int *infoSize )
242 {
243     IORegistryEntry		*chosen;
244     OSData				*propObj;
245     unsigned int		*propPtr;
246     unsigned int		propSize;
247 
248     chosen = IORegistryEntry::fromPath( "/chosen/memory-map", gIODTPlane );
249     if ( chosen == 0 ) return -1;
250 
251     propObj = OSDynamicCast( OSData, chosen->getProperty(key) );
252     if ( propObj == 0 ) return -1;
253 
254     propSize = propObj->getLength();
255     if ( propSize != (2 * sizeof(UInt32)) ) return -1;
256 
257     propPtr = (unsigned int *)propObj->getBytesNoCopy();
258     if ( propPtr == 0 ) return -1;
259 
260     *infoAddr = (void *)propPtr[0] ;
261     *infoSize = (int)   propPtr[1];
262 
263     return 0;
264 }
265 
266 void IODTFreeLoaderInfo( char *key, void *infoAddr, int infoSize )
267 {
268     vm_offset_t			range[2];
269     IORegistryEntry		*chosen;
270 
271     range[0] = (vm_offset_t)infoAddr;
272     range[1] = (vm_offset_t)infoSize;
273     FreePhysicalMemory( range );
274 
275     if ( key != 0 ) {
276         chosen = IORegistryEntry::fromPath( "/chosen/memory-map", gIODTPlane );
277         if ( chosen != 0 ) {
278             chosen->removeProperty(key);
279         }
280     }
281 }
282 
283 static void FreePhysicalMemory( vm_offset_t * range )
284 {
285     vm_offset_t	virt;
286 
287     virt = ml_static_ptovirt( range[0] );
288     if( virt) {
289         ml_static_mfree( virt, range[1] );
290     }
291 }
292 
293 static IORegistryEntry *
294 MakeReferenceTable( DTEntry dtEntry, bool copy )
295 {
296     IORegistryEntry		*regEntry;
297     OSDictionary		*propTable;
298     const OSSymbol		*nameKey;
299     OSData				*data;
300     const OSSymbol		*sym;
301     DTPropertyIterator	dtIter;
302     void				*prop;
303     int					propSize;
304     char				*name;
305     char				location[ 32 ];
306     bool				noLocation = true;
307 
308     regEntry = new IOService;
309 
310     if( regEntry && (false == regEntry->init())) {
311 		regEntry->release();
312 		regEntry = 0;
313     }
314 
315     if( regEntry &&
316 		(kSuccess == DTCreatePropertyIterator( dtEntry, &dtIter))) {
317 
318         propTable = regEntry->getPropertyTable();
319 
320 		while( kSuccess == DTIterateProperties( dtIter, &name)) {
321 
322 			if(  kSuccess != DTGetProperty( dtEntry, name, &prop, &propSize ))
323 				continue;
324 
325 			if( copy) {
326 				nameKey = OSSymbol::withCString(name);
327 				data = OSData::withBytes(prop, propSize);
328 			} else {
329 				nameKey = OSSymbol::withCStringNoCopy(name);
330 				data = OSData::withBytesNoCopy(prop, propSize);
331 			}
332 			assert( nameKey && data );
333 
334 			propTable->setObject( nameKey, data);
335 			data->release();
336 			nameKey->release();
337 
338 			if( nameKey == gIODTNameKey ) {
339 				if( copy)
340 					sym = OSSymbol::withCString( (const char *) prop);
341 				else
342 					sym = OSSymbol::withCStringNoCopy( (const char *) prop);
343 				regEntry->setName( sym );
344 				sym->release();
345 			} else if( nameKey == gIODTUnitKey ) {
346 				// all OF strings are null terminated... except this one
347 				if( propSize >= (int) sizeof( location))
348 					propSize = sizeof( location) - 1;
349 				strncpy( location, (const char *) prop, propSize );
350 				location[ propSize ] = 0;
351 				regEntry->setLocation( location );
352 				propTable->removeObject( gIODTUnitKey );
353 				noLocation = false;
354 
355 			} else if( noLocation && (0 == strcmp( name, "reg"))) {
356 				// default location - override later
357 				sprintf( location, "%lX", *((UInt32 *) prop) );
358 				regEntry->setLocation( location );
359 			}
360 		}
361 		DTDisposePropertyIterator( dtIter);
362     }
363 
364     return( regEntry);
365 }
366 
367 static void AddPHandle( IORegistryEntry * regEntry )
368 {
369     OSData *	data;
370 
371     if( regEntry->getProperty( gIODTInterruptCellKey)
372      	&& (data = OSDynamicCast( OSData, regEntry->getProperty( gIODTPHandleKey )))) {
373 		// a possible interrupt-parent
374 		gIODTPHandles->setObject( data );
375 		gIODTPHandleMap->setObject( regEntry );
376     }
377 }
378 
379 static IORegistryEntry * FindPHandle( UInt32 phandle )
380 {
381     OSData			*data;
382     IORegistryEntry *regEntry = 0;
383     int				i;
384 
385     for( i = 0; (data = (OSData *)gIODTPHandles->getObject( i )); i++ ) {
386 		if( phandle == *((UInt32 *)data->getBytesNoCopy())) {
387 			regEntry = (IORegistryEntry *)
388 			gIODTPHandleMap->getObject( i );
389 			break;
390         }
391     }
392 
393     return( regEntry );
394 }
395 
396 static bool GetUInt32( IORegistryEntry * regEntry, const OSSymbol * name,
397 			UInt32 * value )
398 {
399     OSData	*data;
400 
401     if( (data = OSDynamicCast( OSData, regEntry->getProperty( name )))
402 		&& (4 == data->getLength())) {
403         *value = *((UInt32 *) data->getBytesNoCopy());
404 		return( true );
405     } else
406 		return( false );
407 }
408 
409 IORegistryEntry * IODTFindInterruptParent( IORegistryEntry * regEntry )
410 {
411     IORegistryEntry *	parent;
412     UInt32		phandle;
413 
414     if( GetUInt32( regEntry, gIODTInterruptParentKey, &phandle))
415 		parent = FindPHandle( phandle );
416 
417     else if( 0 == regEntry->getProperty( "interrupt-controller"))
418 		parent = regEntry->getParentEntry( gIODTPlane);
419     else
420 		parent = 0;
421 
422     return( parent );
423 }
424 
425 const OSSymbol * IODTInterruptControllerName( IORegistryEntry * regEntry )
426 {
427     const OSSymbol	*sym;
428     UInt32			phandle;
429     bool			ok;
430     char 			buf[48];
431 
432     ok = GetUInt32( regEntry, gIODTPHandleKey, &phandle);
433     assert( ok );
434 
435     if( ok) {
436         sprintf( buf, "IOInterruptController%08lX", phandle);
437         sym = OSSymbol::withCString( buf );
438     } else
439 		sym = 0;
440 
441     return( sym );
442 }
443 
444 #define unexpected(a) { kprintf("unexpected %s:%d\n", __FILE__, __LINE__); a; }
445 
446 static void IODTGetICellCounts( IORegistryEntry * regEntry,
447 			    UInt32 * iCellCount, UInt32 * aCellCount)
448 {
449     if( !GetUInt32( regEntry, gIODTInterruptCellKey, iCellCount))
450         unexpected( *iCellCount = 1 );
451     if( !GetUInt32( regEntry, gIODTAddressCellKey, aCellCount))
452         *aCellCount = 0;
453 }
454 
455 UInt32 IODTMapOneInterrupt( IORegistryEntry * regEntry, UInt32 * intSpec,
456 				OSData ** spec, const OSSymbol ** controller )
457 {
458     IORegistryEntry *parent = 0;
459     OSData			*data;
460     UInt32			*addrCmp;
461     UInt32			*maskCmp;
462     UInt32			*map;
463     UInt32			*endMap;
464     UInt32			acells, icells, pacells, picells, cell;
465     UInt32			i, original_icells;
466     bool			cmp, ok = false;
467 
468 
469     parent = IODTFindInterruptParent( regEntry );
470     IODTGetICellCounts( parent, &icells, &acells );
471     addrCmp = 0;
472     if( acells) {
473 		data = OSDynamicCast( OSData, regEntry->getProperty( "reg" ));
474 		if( data && (data->getLength() >= (acells * sizeof( UInt32))))
475 	    	addrCmp = (UInt32 *) data->getBytesNoCopy();
476     }
477     original_icells = icells;
478     regEntry = parent;
479 
480 	do {
481 #if IODTSUPPORTDEBUG
482 		kprintf ("IODTMapOneInterrupt: current regEntry name %s\n", regEntry->getName());
483 		kprintf ("acells - icells: ");
484 		for (i = 0; i < acells; i++) kprintf ("0x%08X ", addrCmp[i]);
485 		kprintf ("- ");
486 		for (i = 0; i < icells; i++) kprintf ("0x%08X ", intSpec[i]);
487  		kprintf ("\n");
488 #endif
489 
490 		if( parent && (data = OSDynamicCast( OSData,
491 			regEntry->getProperty( "interrupt-controller")))) {
492 	    	// found a controller - don't want to follow cascaded controllers
493             parent = 0;
494             *spec = OSData::withBytesNoCopy( (void *) intSpec,
495                                             icells * sizeof( UInt32));
496             *controller = IODTInterruptControllerName( regEntry );
497 	    	ok = (*spec && *controller);
498 		} else if( parent && (data = OSDynamicCast( OSData,
499 			regEntry->getProperty( "interrupt-map")))) {
500             // interrupt-map
501             map = (UInt32 *) data->getBytesNoCopy();
502             endMap = map + (data->getLength() / sizeof(UInt32));
503             data = OSDynamicCast( OSData, regEntry->getProperty( "interrupt-map-mask" ));
504             if( data && (data->getLength() >= ((acells + icells) * sizeof( UInt32))))
505                 maskCmp = (UInt32 *) data->getBytesNoCopy();
506 	   		else
507 				maskCmp = 0;
508 
509 #if IODTSUPPORTDEBUG
510  			if (maskCmp) {
511 				kprintf ("        maskCmp: ");
512 				for (i = 0; i < acells + icells; i++) {
513 					if (i == acells)
514 						kprintf ("- ");
515 					kprintf ("0x%08X ", maskCmp[i]);
516 				}
517  				kprintf ("\n");
518 				kprintf ("         masked: ");
519 				for (i = 0; i < acells + icells; i++) {
520 					if (i == acells)
521 						kprintf ("- ");
522 					kprintf ("0x%08X ", ((i < acells) ? addrCmp[i] : intSpec[i-acells]) & maskCmp[i]);
523 				}
524  				kprintf ("\n");
525  			} else
526  				kprintf ("no maskCmp\n");
527 #endif
528 			do {
529 #if IODTSUPPORTDEBUG
530 				kprintf ("            map: ");
531 				for (i = 0; i < acells + icells; i++) {
532 					if (i == acells)
533 						kprintf ("- ");
534 					kprintf ("0x%08X ", map[i]);
535 				}
536  				kprintf ("\n");
537 #endif
538 				for( i = 0, cmp = true; cmp && (i < (acells + icells)); i++) {
539                     cell = (i < acells) ? addrCmp[i] : intSpec[ i - acells ];
540                     if( maskCmp)
541                         cell &= maskCmp[i];
542                     cmp = (cell == map[i]);
543                 }
544 
545                 map += acells + icells;
546                 if( 0 == (parent = FindPHandle( *(map++) )))
547                     unexpected(break);
548 
549 				IODTGetICellCounts( parent, &picells, &pacells );
550                 if( cmp) {
551                     addrCmp = map;
552                     intSpec = map + pacells;
553                     regEntry = parent;
554 				} else {
555                     map += pacells + picells;
556 				}
557             } while( !cmp && (map < endMap) );
558             if (!cmp)
559             	parent = 0;
560 		}
561 
562 		if( parent) {
563             IODTGetICellCounts( parent, &icells, &acells );
564 	    	regEntry = parent;
565 		}
566 	} while( parent);
567 
568     return( ok ? original_icells : 0 );
569 }
570 
571 bool IODTMapInterrupts( IORegistryEntry * regEntry )
572 {
573     IORegistryEntry *parent;
574     OSData			*local;
575     OSData			*local2;
576     UInt32			*localBits;
577     UInt32			*localEnd;
578     OSData			*map;
579     OSArray			*mapped;
580     const OSSymbol	*controller;
581     OSArray			*controllers;
582     UInt32			skip = 1;
583     bool			ok, nw;
584 
585     nw = (0 == (local = OSDynamicCast( OSData,
586 		regEntry->getProperty( gIODTAAPLInterruptsKey))));
587     if( nw && (0 == (local = OSDynamicCast( OSData,
588 		regEntry->getProperty( "interrupts")))))
589 		return( true );		// nothing to see here
590 
591     if( nw && (parent = regEntry->getParentEntry( gIODTPlane))) {
592 		// check for bridges on old world
593 		if( (local2 = OSDynamicCast( OSData,
594  			parent->getProperty( gIODTAAPLInterruptsKey)))) {
595 	    	local = local2;
596 	    	nw = false;
597 		}
598     }
599 
600     localBits = (UInt32 *) local->getBytesNoCopy();
601     localEnd = localBits + (local->getLength() / sizeof( UInt32));
602     mapped = OSArray::withCapacity( 1 );
603     controllers = OSArray::withCapacity( 1 );
604 
605     ok = (mapped && controllers);
606 
607     if( ok) do {
608         if( nw) {
609             skip = IODTMapOneInterrupt( regEntry, localBits, &map, &controller );
610             if( 0 == skip) {
611                 IOLog("%s: error mapping interrupt[%d]\n",
612 					regEntry->getName(), mapped->getCount());
613                 break;
614             }
615         } else {
616             map = OSData::withData( local, mapped->getCount() * sizeof( UInt32),
617 				sizeof( UInt32));
618             controller = gIODTDefaultInterruptController;
619         }
620 
621         localBits += skip;
622         mapped->setObject( map );
623         map->release();
624         controllers->setObject( (OSObject *) controller );
625         controller->release();
626 
627     } while( localBits < localEnd);
628 
629     ok &= (localBits == localEnd);
630 
631     if( ok ) {
632 		// store results
633         ok  = regEntry->setProperty( gIOInterruptControllersKey, controllers);
634         ok &= regEntry->setProperty( gIOInterruptSpecifiersKey, mapped);
635     }
636 
637     if( controllers)
638         controllers->release();
639     if( mapped)
640         mapped->release();
641 
642     return( ok );
643 }
644 
645 /*
646  */
647 
648 static const char *
649 CompareKey( OSString * key,
650 		const IORegistryEntry * table, const OSSymbol * propName )
651 {
652     OSObject		*prop;
653     OSData			*data;
654     OSString		*string;
655     const char		*ckey;
656     UInt32			keyLen;
657     const char		*names;
658     const char		*lastName;
659     bool			wild;
660     bool			matched;
661     const char		*result = 0;
662 
663     if( 0 == (prop = table->getProperty( propName )))
664 	return( 0 );
665 
666     if( (data = OSDynamicCast( OSData, prop ))) {
667         names = (const char *) data->getBytesNoCopy();
668         lastName = names + data->getLength();
669     } else if( (string = OSDynamicCast( OSString, prop ))) {
670         names = string->getCStringNoCopy();
671         lastName = names + string->getLength() + 1;
672     } else
673 		return( 0 );
674 
675     ckey = key->getCStringNoCopy();
676     keyLen = key->getLength();
677     wild = ('*' == key->getChar( keyLen - 1 ));
678 
679     do {
680         // for each name in the property
681         if( wild)
682             matched = (0 == strncmp( ckey, names, keyLen - 1 ));
683         else
684             matched = (keyLen == strlen( names ))
685                     && (0 == strncmp( ckey, names, keyLen ));
686 
687         if( matched)
688             result = names;
689 
690         names = names + strlen( names) + 1;
691 
692     } while( (names < lastName) && (false == matched));
693 
694     return( result);
695 }
696 
697 
698 bool IODTCompareNubName( const IORegistryEntry * regEntry,
699 			 OSString * name, OSString ** matchingName )
700 {
701     const char		*result;
702     bool			matched;
703 
704     matched =  (0 != (result = CompareKey( name, regEntry, gIODTNameKey)))
705 	    || (0 != (result = CompareKey( name, regEntry, gIODTCompatibleKey)))
706 	    || (0 != (result = CompareKey( name, regEntry, gIODTTypeKey)))
707 	    || (0 != (result = CompareKey( name, regEntry, gIODTModelKey)));
708 
709     if( result && matchingName)
710 	*matchingName = OSString::withCString( result );
711 
712     return( result != 0 );
713 }
714 
715 bool IODTMatchNubWithKeys( IORegistryEntry * regEntry,
716                                     const char * keys )
717 {
718     OSObject	*obj;
719     bool		result = false;
720 
721     obj = OSUnserialize( keys, 0 );
722 
723     if( obj) {
724         result = regEntry->compareNames( obj );
725 		obj->release();
726     }
727 #ifdef DEBUG
728     	else IOLog("Couldn't unserialize %s\n", keys );
729 #endif
730 
731     return( result );
732 }
733 
734 OSCollectionIterator * IODTFindMatchingEntries( IORegistryEntry * from,
735 			IOOptionBits options, const char * keys )
736 {
737     OSSet					*result;
738     IORegistryEntry			*next;
739     IORegistryIterator		*iter;
740     OSCollectionIterator	*cIter;
741     bool					cmp;
742     bool					minus = options & kIODTExclusive;
743 
744     result = OSSet::withCapacity( 3 );
745     if( !result)
746 		return( 0);
747 
748     iter = IORegistryIterator::iterateOver( from, gIODTPlane,
749 		(options & kIODTRecursive) ? kIORegistryIterateRecursively : 0 );
750     if( iter) {
751         while( (next = iter->getNextObject())) {
752 
753             // Look for existence of a debug property to skip
754             if( next->getProperty("AAPL,ignore"))
755 				continue;
756 
757 	    	if( keys) {
758                 cmp = IODTMatchNubWithKeys( next, keys );
759                 if( (minus && (false == cmp))
760                 	|| ((false == minus) && (false != cmp)) )
761                     result->setObject( next);
762 	    	} else
763                 result->setObject( next);
764         }
765         iter->release();
766     }
767 
768     cIter = OSCollectionIterator::withCollection( result);
769     result->release();
770 
771     return( cIter);
772 }
773 
774 
775 struct IODTPersistent {
776     IODTCompareAddressCellFunc	compareFunc;
777     IODTNVLocationFunc		locationFunc;
778 };
779 
780 void IODTSetResolving( IORegistryEntry * 	regEntry,
781 		IODTCompareAddressCellFunc	compareFunc,
782 		IODTNVLocationFunc		locationFunc )
783 {
784     IODTPersistent	persist;
785     OSData			*prop;
786 
787     persist.compareFunc = compareFunc;
788     persist.locationFunc = locationFunc;
789     prop = OSData::withBytes( &persist, sizeof( persist));
790     if( !prop)
791 		return;
792 
793     regEntry->setProperty( gIODTPersistKey, prop);
794     prop->release();
795     return;
796 }
797 
798 static SInt32 DefaultCompare( UInt32 cellCount, UInt32 left[], UInt32 right[] )
799 {
800     cellCount--;
801     return( left[ cellCount ] - right[ cellCount ] );
802 }
803 
804 
805 void IODTGetCellCounts( IORegistryEntry * regEntry,
806 			    UInt32 * sizeCount, UInt32 * addressCount)
807 {
808     if( !GetUInt32( regEntry, gIODTSizeCellKey, sizeCount))
809         *sizeCount = 1;
810     if( !GetUInt32( regEntry, gIODTAddressCellKey, addressCount))
811         *addressCount = 2;
812 	return;
813 }
814 
815 // Given addr & len cells from our child, find it in our ranges property, then
816 // look in our parent to resolve the base of the range for us.
817 
818 // Range[]: child-addr  our-addr  child-len
819 // #cells:    child       ours     child
820 
821 bool IODTResolveAddressCell( IORegistryEntry * regEntry,
822                              UInt32 cellsIn[],
823                              IOPhysicalAddress * phys, IOPhysicalLength * len )
824 {
825     IORegistryEntry		*parent;
826     OSData				*prop;
827     // cells in addresses at regEntry
828     UInt32				sizeCells, addressCells;
829     // cells in addresses below regEntry
830     UInt32				childSizeCells, childAddressCells;
831     UInt32				childCells;
832     UInt32				cell[ 5 ], offset = 0, length;
833     UInt32				*range;
834     UInt32				*endRanges;
835     bool				ok = true;
836     SInt32				diff;
837 
838     IODTPersistent				*persist;
839     IODTCompareAddressCellFunc	compare;
840 
841     IODTGetCellCounts( regEntry, &childSizeCells, &childAddressCells );
842     childCells = childAddressCells + childSizeCells;
843 
844     bcopy( cellsIn, cell, 4 * childCells );
845     if( childSizeCells > 1)
846         *len = IOPhysical32( cellsIn[ childAddressCells ],
847 			cellsIn[ childAddressCells + 1 ] );
848     else
849         *len = IOPhysical32( 0, cellsIn[ childAddressCells ] );
850 
851     do {
852         prop = OSDynamicCast( OSData, regEntry->getProperty( gIODTRangeKey ));
853         if( 0 == prop) {
854 	    	/* end of the road */
855             *phys = IOPhysical32( 0,  cell[ childAddressCells - 1 ] + offset);
856             break;
857         }
858 
859         parent = regEntry->getParentEntry( gIODTPlane );
860 		IODTGetCellCounts( parent, &sizeCells, &addressCells );
861 
862         if( (length = prop->getLength())) {
863             // search
864             range = (UInt32 *) prop->getBytesNoCopy();
865             endRanges = range + (length / 4);
866 
867             prop = (OSData *) regEntry->getProperty( gIODTPersistKey );
868             if( prop) {
869                 persist = (IODTPersistent *) prop->getBytesNoCopy();
870                 compare = persist->compareFunc;
871             } else
872                 compare = DefaultCompare;
873 
874             for( ok = false;
875                  range < endRanges;
876                  range += (childCells + addressCells) ) {
877 
878                 // is cell >= range start?
879                 diff = (*compare)( childAddressCells, cell, range );
880                 if( diff < 0)
881                     continue;
882 
883                 // is cell + size <= range end?
884                 if( (diff + cell[ childCells - 1 ])
885                         > range[ childCells + addressCells - 1 ])
886                     continue;
887 
888                 offset += diff;
889                 ok = true;
890                 break;
891             }
892 
893             // Get the physical start of the range from our parent
894             bcopy( range + childAddressCells, cell, 4 * addressCells );
895             bzero( cell + addressCells, 4 * sizeCells );
896 
897         } /* else zero length range => pass thru to parent */
898 
899 	regEntry			= parent;
900 	childSizeCells		= sizeCells;
901 	childAddressCells	= addressCells;
902 	childCells			= childAddressCells + childSizeCells;
903 
904     } while( ok && regEntry);
905 
906     return( ok);
907 }
908 
909 
910 OSArray * IODTResolveAddressing( IORegistryEntry * regEntry,
911 			const char * addressPropertyName,
912 			IODeviceMemory * parent )
913 {
914     IORegistryEntry		*parentEntry;
915     OSData				*addressProperty;
916     UInt32				sizeCells, addressCells, cells;
917     int					i, num;
918     UInt32				*reg;
919     IOPhysicalAddress	phys;
920     IOPhysicalLength	len;
921     OSArray				*array;
922     IODeviceMemory		*range;
923 
924     parentEntry = regEntry->getParentEntry( gIODTPlane );
925     addressProperty = (OSData *) regEntry->getProperty( addressPropertyName );
926     if( (0 == addressProperty) || (0 == parentEntry))
927 		return( 0);
928 
929     IODTGetCellCounts( parentEntry, &sizeCells, &addressCells );
930     if( 0 == sizeCells)
931 		return( 0);
932 
933     cells = sizeCells + addressCells;
934     reg = (UInt32 *) addressProperty->getBytesNoCopy();
935     num = addressProperty->getLength() / (4 * cells);
936 
937     array = OSArray::withCapacity( 1 );
938     if( 0 == array)
939 		return( 0);
940 
941     for( i = 0; i < num; i++) {
942 		if( IODTResolveAddressCell( parentEntry, reg, &phys, &len )) {
943 			range = 0;
944 			if( parent)
945 				range = IODeviceMemory::withSubRange( parent,
946 					phys - parent->getPhysicalAddress(), len );
947 			if( 0 == range)
948 				range = IODeviceMemory::withRange( phys, len );
949 			if( range)
950 				array->setObject( range );
951 		}
952 		reg += cells;
953     }
954 
955     regEntry->setProperty( gIODeviceMemoryKey, array);
956     array->release();	/* ??? */
957 
958     return( array);
959 }
960 
961 static void IODTGetNVLocation(
962 	IORegistryEntry * parent,
963 	IORegistryEntry * regEntry,
964 	UInt8 * busNum, UInt8 * deviceNum, UInt8 * functionNum )
965 {
966 
967     OSData			*prop;
968     IODTPersistent	*persist;
969     UInt32			*cell;
970 
971     prop = (OSData *) parent->getProperty( gIODTPersistKey );
972     if( prop) {
973         persist = (IODTPersistent *) prop->getBytesNoCopy();
974 		(*persist->locationFunc)( regEntry, busNum, deviceNum, functionNum );
975     } else {
976         prop = (OSData *) regEntry->getProperty( "reg" );
977         *functionNum	= 0;
978         if( prop) {
979             cell = (UInt32 *) prop->getBytesNoCopy();
980             *busNum 	= 3;
981             *deviceNum 	= 0x1f & (cell[ 0 ] >> 24);
982         } else {
983             *busNum 	= 0;
984             *deviceNum 	= 0;
985 		}
986     }
987     return;
988 }
989 
990 /*
991  * Try to make the same messed up descriptor as Mac OS
992  */
993 
994 IOReturn IODTMakeNVDescriptor( IORegistryEntry * regEntry,
995 				IONVRAMDescriptor * hdr )
996 {
997     IORegistryEntry		*parent;
998     UInt32				level;
999     UInt32				bridgeDevices;
1000     UInt8				busNum;
1001     UInt8				deviceNum;
1002     UInt8				functionNum;
1003 
1004     hdr->format 	= 1;
1005     hdr->marker 	= 0;
1006 
1007     for(level = 0, bridgeDevices = 0;
1008     	(parent = regEntry->getParentEntry( gIODTPlane )) && (level < 7); level++ ) {
1009 
1010         IODTGetNVLocation( parent, regEntry,
1011 			&busNum, &deviceNum, &functionNum );
1012 		if( level)
1013 			bridgeDevices |= ((deviceNum & 0x1f) << ((level - 1) * 5));
1014 		else {
1015             hdr->busNum 	= busNum;
1016             hdr->deviceNum 	= deviceNum;
1017             hdr->functionNum 	= functionNum;
1018 		}
1019 		regEntry = parent;
1020     }
1021     hdr->bridgeCount 	= level - 2;
1022     hdr->bridgeDevices 	= bridgeDevices;
1023 
1024     return( kIOReturnSuccess );
1025 }
1026 
1027 OSData * IODTFindSlotName( IORegistryEntry * regEntry, UInt32 deviceNumber )
1028 {
1029     IORegistryEntry		*parent;
1030     OSData				*data;
1031     OSData				*ret = 0;
1032     UInt32				*bits;
1033     UInt32				i;
1034     char				*names;
1035     char				*lastName;
1036     UInt32				mask;
1037 
1038     data = (OSData *) regEntry->getProperty("AAPL,slot-name");
1039     if( data)
1040 		return( data);
1041     parent = regEntry->getParentEntry( gIODTPlane );
1042     if( !parent)
1043 		return( 0 );
1044     data = OSDynamicCast( OSData, parent->getProperty("slot-names"));
1045     if( !data)
1046 		return( 0 );
1047     if( data->getLength() <= 4)
1048 		return( 0 );
1049 
1050     bits = (UInt32 *) data->getBytesNoCopy();
1051     mask = *bits;
1052     if( (0 == (mask & (1 << deviceNumber))))
1053 		return( 0 );
1054 
1055     names = (char *)(bits + 1);
1056     lastName = names + (data->getLength() - 4);
1057 
1058     for( i = 0; (i <= deviceNumber) && (names < lastName); i++ ) {
1059 
1060 		if( mask & (1 << i)) {
1061             if( i == deviceNumber) {
1062 				data = OSData::withBytesNoCopy( names, 1 + strlen( names));
1063 				if( data) {
1064 					regEntry->setProperty("AAPL,slot-name", data);
1065 					ret = data;
1066 					data->release();
1067 				}
1068             } else
1069 				names += 1 + strlen( names);
1070         }
1071     }
1072 
1073     return( ret );
1074 }
1075