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