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