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