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 *)(uintptr_t) (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     UInt32          nlen;
780     const char		*names;
781     const char		*lastName;
782     bool			wild;
783     bool			matched;
784     const char		*result = 0;
785 
786     if( 0 == (prop = table->getProperty( propName )))
787 	return( 0 );
788 
789     if( (data = OSDynamicCast( OSData, prop ))) {
790         names = (const char *) data->getBytesNoCopy();
791         lastName = names + data->getLength();
792     } else if( (string = OSDynamicCast( OSString, prop ))) {
793         names = string->getCStringNoCopy();
794         lastName = names + string->getLength() + 1;
795     } else
796 		return( 0 );
797 
798     ckey = key->getCStringNoCopy();
799     keyLen = key->getLength();
800     wild = ('*' == key->getChar( keyLen - 1 ));
801 
802     do {
803         // for each name in the property
804         nlen = strnlen(names, lastName - names);
805         if( wild)
806             matched = ((nlen >= (keyLen - 1)) && (0 == strncmp(ckey, names, keyLen - 1)));
807         else
808             matched = (keyLen == nlen) && (0 == strncmp(ckey, names, keyLen));
809 
810         if( matched)
811             result = names;
812 
813         names = names + nlen + 1;
814 
815     } while( (names < lastName) && (false == matched));
816 
817     return( result);
818 }
819 
820 
821 bool IODTCompareNubName( const IORegistryEntry * regEntry,
822 			 OSString * name, OSString ** matchingName )
823 {
824     const char		*result;
825     bool			matched;
826 
827     matched =  (0 != (result = CompareKey( name, regEntry, gIODTNameKey)))
828 	    || (0 != (result = CompareKey( name, regEntry, gIODTCompatibleKey)))
829 	    || (0 != (result = CompareKey( name, regEntry, gIODTTypeKey)))
830 	    || (0 != (result = CompareKey( name, regEntry, gIODTModelKey)));
831 
832     if( result && matchingName)
833 	*matchingName = OSString::withCString( result );
834 
835     return( result != 0 );
836 }
837 
838 bool IODTMatchNubWithKeys( IORegistryEntry * regEntry,
839                                     const char * keys )
840 {
841     OSObject	*obj;
842     bool		result = false;
843 
844     obj = OSUnserialize( keys, 0 );
845 
846     if( obj) {
847         result = regEntry->compareNames( obj );
848 		obj->release();
849     }
850 #if DEBUG
851     else IOLog("Couldn't unserialize %s\n", keys );
852 #endif
853 
854     return( result );
855 }
856 
857 OSCollectionIterator * IODTFindMatchingEntries( IORegistryEntry * from,
858 			IOOptionBits options, const char * keys )
859 {
860     OSSet					*result = 0;
861     IORegistryEntry			*next;
862     IORegistryIterator		*iter;
863     OSCollectionIterator	*cIter;
864     bool					cmp;
865     bool					minus = options & kIODTExclusive;
866 
867 
868     iter = IORegistryIterator::iterateOver( from, gIODTPlane,
869 		(options & kIODTRecursive) ? kIORegistryIterateRecursively : 0 );
870     if( iter) {
871 
872         do {
873 
874             if( result)
875                 result->release();
876             result = OSSet::withCapacity( 3 );
877             if( !result)
878                 break;
879 
880             iter->reset();
881             while( (next = iter->getNextObject())) {
882 
883                 // Look for existence of a debug property to skip
884                 if( next->getProperty("AAPL,ignore"))
885                     continue;
886 
887                 if( keys) {
888                     cmp = IODTMatchNubWithKeys( next, keys );
889                     if( (minus && (false == cmp))
890                             || ((false == minus) && (false != cmp)) )
891                         result->setObject( next);
892                 } else
893                     result->setObject( next);
894             }
895         } while( !iter->isValid());
896 
897         iter->release();
898     }
899 
900     cIter = OSCollectionIterator::withCollection( result);
901     result->release();
902 
903     return( cIter);
904 }
905 
906 
907 struct IODTPersistent {
908     IODTCompareAddressCellFunc	compareFunc;
909     IODTNVLocationFunc		locationFunc;
910 };
911 
912 void IODTSetResolving( IORegistryEntry * 	regEntry,
913 		IODTCompareAddressCellFunc	compareFunc,
914 		IODTNVLocationFunc		locationFunc )
915 {
916     IODTPersistent	persist;
917     OSData			*prop;
918 
919     persist.compareFunc = compareFunc;
920     persist.locationFunc = locationFunc;
921     prop = OSData::withBytes( &persist, sizeof(persist));
922     if( !prop)
923         return;
924 
925     prop->setSerializable(false);
926     regEntry->setProperty( gIODTPersistKey, prop);
927     prop->release();
928     return;
929 }
930 
931 #if   defined(__arm__) || defined(__i386__) || defined(__x86_64__)
932 static SInt32 DefaultCompare( UInt32 cellCount, UInt32 left[], UInt32 right[] )
933 {
934 	cellCount--;
935 	return( left[ cellCount ] - right[ cellCount ] );
936 }
937 #else
938 #error Unknown architecture.
939 #endif
940 
941 static void AddLengthToCells( UInt32 numCells, UInt32 *cells, UInt64 offset)
942 {
943     if (numCells == 1)
944     {
945         cells[0] += (UInt32)offset;
946     }
947     else {
948         UInt64 sum = cells[numCells - 1] + offset;
949         cells[numCells - 1] = (UInt32)sum;
950         if (sum > UINT32_MAX) {
951             cells[numCells - 2] += (UInt32)(sum >> 32);
952         }
953     }
954 }
955 
956 static IOPhysicalAddress CellsValue( UInt32 numCells, UInt32 *cells)
957 {
958     if (numCells == 1) {
959         return IOPhysical32( 0, cells[0] );
960     } else {
961         return IOPhysical32( cells[numCells - 2], cells[numCells - 1] );
962     }
963 }
964 
965 void IODTGetCellCounts( IORegistryEntry * regEntry,
966 			    UInt32 * sizeCount, UInt32 * addressCount)
967 {
968     if( !GetUInt32( regEntry, gIODTSizeCellKey, sizeCount))
969         *sizeCount = 1;
970     if( !GetUInt32( regEntry, gIODTAddressCellKey, addressCount))
971         *addressCount = 2;
972     return;
973 }
974 
975 // Given addr & len cells from our child, find it in our ranges property, then
976 // look in our parent to resolve the base of the range for us.
977 
978 // Range[]: child-addr  our-addr  child-len
979 // #cells:    child       ours     child
980 
981 bool IODTResolveAddressCell( IORegistryEntry * regEntry,
982                              UInt32 cellsIn[],
983                              IOPhysicalAddress * phys, IOPhysicalLength * lenOut )
984 {
985     IORegistryEntry	*parent;
986     OSData		*prop;
987     // cells in addresses at regEntry
988     UInt32		sizeCells, addressCells;
989     // cells in addresses below regEntry
990     UInt32		childSizeCells, childAddressCells;
991     UInt32		childCells;
992     UInt32		cell[ 8 ], propLen;
993     UInt64		offset = 0;
994     UInt32		endCell[ 8 ];
995     UInt32		*range;
996     UInt32		*lookRange;
997     UInt32		*startRange;
998     UInt32		*endRanges;
999     bool		ok = true;
1000     SInt64		diff, diff2, endDiff;
1001     UInt64		len, rangeLen;
1002 
1003     IODTPersistent	*persist;
1004     IODTCompareAddressCellFunc	compare;
1005 
1006     IODTGetCellCounts( regEntry, &childSizeCells, &childAddressCells );
1007     childCells = childAddressCells + childSizeCells;
1008 
1009     if (childCells > sizeof(cell)/sizeof(cell[0]))
1010         panic("IODTResolveAddressCell: Invalid device tree (%u,%u)", (uint32_t)childAddressCells, (uint32_t)childSizeCells);
1011 
1012     bcopy( cellsIn, cell, sizeof(UInt32) * childCells );
1013     *lenOut = CellsValue( childSizeCells, cellsIn + childAddressCells );
1014 
1015     do
1016     {
1017         prop = OSDynamicCast( OSData, regEntry->getProperty( gIODTRangeKey ));
1018         if( 0 == prop) {
1019             /* end of the road */
1020             *phys = CellsValue( childAddressCells, cell );
1021             *phys += offset;
1022             break;
1023         }
1024 
1025         parent = regEntry->getParentEntry( gIODTPlane );
1026         IODTGetCellCounts( parent, &sizeCells, &addressCells );
1027 
1028         if( (propLen = prop->getLength())) {
1029             // search
1030             startRange = (UInt32 *) prop->getBytesNoCopy();
1031             range = startRange;
1032             endRanges = range + (propLen / sizeof(UInt32));
1033 
1034             prop = (OSData *) regEntry->getProperty( gIODTPersistKey );
1035             if( prop) {
1036                 persist = (IODTPersistent *) prop->getBytesNoCopy();
1037                 compare = persist->compareFunc;
1038             } else if (addressCells == childAddressCells) {
1039                 compare = DefaultCompare;
1040             } else {
1041                 panic("There is no mixed comparison function yet...");
1042             }
1043 
1044             for( ok = false;
1045                     range < endRanges;
1046                     range += (childCells + addressCells) ) {
1047 
1048                 // is cell start within range?
1049                 diff = (*compare)( childAddressCells, cell, range );
1050 
1051                 if (childAddressCells > sizeof(endCell)/sizeof(endCell[0]))
1052                     panic("IODTResolveAddressCell: Invalid device tree (%u)", (uint32_t)childAddressCells);
1053 
1054                 bcopy(range, endCell, childAddressCells * sizeof(UInt32));
1055 
1056                 rangeLen = CellsValue(childSizeCells, range + childAddressCells + addressCells);
1057                 AddLengthToCells(childAddressCells, endCell, rangeLen);
1058 
1059                 diff2 = (*compare)( childAddressCells, cell, endCell );
1060 
1061                 // if start of cell < start of range, or end of range >= start of cell, skip
1062                 if ((diff < 0) || (diff2 >= 0))
1063                     continue;
1064 
1065                 len = CellsValue(childSizeCells, cell + childAddressCells);
1066                 ok = (0 == len);
1067 
1068                 if (!ok)
1069                 {
1070                     // search for cell end
1071                     bcopy(cell, endCell, childAddressCells * sizeof(UInt32));
1072 
1073                     AddLengthToCells(childAddressCells, endCell, len - 1);
1074 
1075                     for( lookRange = startRange;
1076                             lookRange < endRanges;
1077                             lookRange += (childCells + addressCells) )
1078                     {
1079                         // make sure end of cell >= range start
1080                         endDiff = (*compare)( childAddressCells, endCell, lookRange );
1081                         if( endDiff < 0)
1082                             continue;
1083 
1084                         UInt64 rangeStart = CellsValue(addressCells, range + childAddressCells);
1085                         UInt64 lookRangeStart = CellsValue(addressCells, lookRange + childAddressCells);
1086                         if ((endDiff - len + 1 + lookRangeStart) == (diff + rangeStart))
1087                         {
1088                             ok = true;
1089                             break;
1090                         }
1091                     }
1092                     if (!ok)
1093                         continue;
1094                 }
1095                 offset += diff;
1096                 break;
1097             }
1098 
1099             if (addressCells + sizeCells > sizeof(cell)/sizeof(cell[0]))
1100                 panic("IODTResolveAddressCell: Invalid device tree (%u, %u)", (uint32_t)addressCells, (uint32_t)sizeCells);
1101 
1102             // Get the physical start of the range from our parent
1103             bcopy( range + childAddressCells, cell, sizeof(UInt32) * addressCells );
1104             bzero( cell + addressCells, sizeof(UInt32) * sizeCells );
1105 
1106         } /* else zero length range => pass thru to parent */
1107 
1108         regEntry		= parent;
1109         childSizeCells		= sizeCells;
1110         childAddressCells	= addressCells;
1111         childCells		= childAddressCells + childSizeCells;
1112     }
1113     while( ok && regEntry);
1114 
1115     return( ok);
1116 }
1117 
1118 
1119 OSArray * IODTResolveAddressing( IORegistryEntry * regEntry,
1120 			const char * addressPropertyName,
1121 			IODeviceMemory * parent )
1122 {
1123     IORegistryEntry		*parentEntry;
1124     OSData				*addressProperty;
1125     UInt32				sizeCells, addressCells, cells;
1126     int					i, num;
1127     UInt32				*reg;
1128     IOPhysicalAddress	phys;
1129     IOPhysicalLength	len;
1130     OSArray				*array;
1131     IODeviceMemory		*range;
1132 
1133     parentEntry = regEntry->getParentEntry( gIODTPlane );
1134     addressProperty = (OSData *) regEntry->getProperty( addressPropertyName );
1135     if( (0 == addressProperty) || (0 == parentEntry))
1136         return( 0);
1137 
1138     IODTGetCellCounts( parentEntry, &sizeCells, &addressCells );
1139     if( 0 == sizeCells)
1140         return( 0);
1141 
1142     cells = sizeCells + addressCells;
1143     reg = (UInt32 *) addressProperty->getBytesNoCopy();
1144     num = addressProperty->getLength() / (4 * cells);
1145 
1146     array = OSArray::withCapacity( 1 );
1147     if( 0 == array)
1148         return( 0);
1149 
1150     for( i = 0; i < num; i++) {
1151         if( IODTResolveAddressCell( parentEntry, reg, &phys, &len )) {
1152             range = 0;
1153             if( parent)
1154                 range = IODeviceMemory::withSubRange( parent,
1155                         phys - parent->getPhysicalSegment(0, 0, kIOMemoryMapperNone), len );
1156             if( 0 == range)
1157                 range = IODeviceMemory::withRange( phys, len );
1158             if( range)
1159                 array->setObject( range );
1160         }
1161         reg += cells;
1162     }
1163 
1164     regEntry->setProperty( gIODeviceMemoryKey, array);
1165     array->release();	/* ??? */
1166 
1167     return( array);
1168 }
1169 
1170 static void IODTGetNVLocation(
1171 	IORegistryEntry * parent,
1172 	IORegistryEntry * regEntry,
1173 	UInt8 * busNum, UInt8 * deviceNum, UInt8 * functionNum )
1174 {
1175 
1176     OSData			*prop;
1177     IODTPersistent	*persist;
1178     UInt32			*cell;
1179 
1180     prop = (OSData *) parent->getProperty( gIODTPersistKey );
1181     if( prop) {
1182         persist = (IODTPersistent *) prop->getBytesNoCopy();
1183         (*persist->locationFunc)( regEntry, busNum, deviceNum, functionNum );
1184     } else {
1185         prop = (OSData *) regEntry->getProperty( "reg" );
1186         *functionNum	= 0;
1187         if( prop) {
1188             cell = (UInt32 *) prop->getBytesNoCopy();
1189             *busNum 	= 3;
1190             *deviceNum 	= 0x1f & (cell[ 0 ] >> 24);
1191         } else {
1192             *busNum 	= 0;
1193             *deviceNum 	= 0;
1194         }
1195     }
1196     return;
1197 }
1198 
1199 /*
1200  * Try to make the same messed up descriptor as Mac OS
1201  */
1202 
1203 IOReturn IODTMakeNVDescriptor( IORegistryEntry * regEntry,
1204 				IONVRAMDescriptor * hdr )
1205 {
1206     IORegistryEntry		*parent;
1207     UInt32				level;
1208     UInt32				bridgeDevices;
1209     UInt8				busNum;
1210     UInt8				deviceNum;
1211     UInt8				functionNum;
1212 
1213     hdr->format 	= 1;
1214     hdr->marker 	= 0;
1215 
1216     for(level = 0, bridgeDevices = 0;
1217     	(parent = regEntry->getParentEntry( gIODTPlane )) && (level < 7); level++ ) {
1218 
1219         IODTGetNVLocation( parent, regEntry,
1220 			&busNum, &deviceNum, &functionNum );
1221         if( level)
1222             bridgeDevices |= ((deviceNum & 0x1f) << ((level - 1) * 5));
1223         else {
1224             hdr->busNum 	= busNum;
1225             hdr->deviceNum 	= deviceNum;
1226             hdr->functionNum 	= functionNum;
1227         }
1228         regEntry = parent;
1229     }
1230     hdr->bridgeCount 	= level - 2;
1231     hdr->bridgeDevices 	= bridgeDevices;
1232 
1233     return( kIOReturnSuccess );
1234 }
1235 
1236 OSData * IODTFindSlotName( IORegistryEntry * regEntry, UInt32 deviceNumber )
1237 {
1238     IORegistryEntry		*parent;
1239     OSData				*data;
1240     OSData				*ret = 0;
1241     UInt32				*bits;
1242     UInt32				i;
1243     size_t              nlen;
1244     char				*names;
1245     char				*lastName;
1246     UInt32				mask;
1247 
1248     data = (OSData *) regEntry->getProperty("AAPL,slot-name");
1249     if( data)
1250         return( data);
1251     parent = regEntry->getParentEntry( gIODTPlane );
1252     if( !parent)
1253         return( 0 );
1254     data = OSDynamicCast( OSData, parent->getProperty("slot-names"));
1255     if( !data)
1256         return( 0 );
1257     if( data->getLength() <= 4)
1258         return( 0 );
1259 
1260     bits = (UInt32 *) data->getBytesNoCopy();
1261     mask = *bits;
1262     if( (0 == (mask & (1 << deviceNumber))))
1263         return( 0 );
1264 
1265     names = (char *)(bits + 1);
1266     lastName = names + (data->getLength() - 4);
1267 
1268     for( i = 0; (i <= deviceNumber) && (names < lastName); i++ ) {
1269 
1270         if( mask & (1 << i)) {
1271             nlen = 1 + strnlen(names, lastName - names);
1272             if( i == deviceNumber) {
1273                 data = OSData::withBytesNoCopy(names, nlen);
1274                 if( data) {
1275                     regEntry->setProperty("AAPL,slot-name", data);
1276                     ret = data;
1277                     data->release();
1278                 }
1279             } else
1280                 names += nlen;
1281         }
1282     }
1283 
1284     return( ret );
1285 }
1286 
1287 extern "C" IOReturn IONDRVLibrariesInitialize( IOService * provider )
1288 {
1289     return( kIOReturnUnsupported );
1290 }
1291