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