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