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