IODeviceTreeSupport.cpp   [plain text]

/*
 * Copyright (c) 1998-2000 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * The contents of this file constitute Original Code as defined in and
 * are subject to the Apple Public Source License Version 1.1 (the
 * "License").  You may not use this file except in compliance with the
 * License.  Please obtain a copy of the License at
 * http://www.apple.com/publicsource and read it before using this file.
 * 
 * This Original Code and all software distributed under the License are
 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
 * License for the specific language governing rights and limitations
 * under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
/*
 * Copyright (c) 1998 Apple Computer, Inc.  All rights reserved. 
 *
 * HISTORY
 * 23 Nov 98 sdouglas, created from IODeviceTreeBus.m, & MacOS exp mgr.
 * 05 Apr 99 sdouglas, add interrupt mapping.
 *
 */

#include <IOKit/IODeviceTreeSupport.h>
#include <libkern/c++/OSContainers.h>
#include <IOKit/IODeviceMemory.h>
#include <IOKit/IOService.h>
#include <IOKit/IOCatalogue.h>

#include <IOKit/IOLib.h>
#include <IOKit/IOKitKeys.h>

#include <DeviceTree.h>
extern "C" {
#include <machine/machine_routines.h>
void DTInit( void * data );

int IODTGetLoaderInfo( char *key, void **infoAddr, int *infosize );
void IODTFreeLoaderInfo( char *key, void *infoAddr, int infoSize );
}

#include <IOKit/assert.h>


const IORegistryPlane * gIODTPlane;

static OSArray *	gIODTPHandles;
static OSArray *	gIODTPHandleMap;

const OSSymbol *	gIODTNameKey;
const OSSymbol *	gIODTUnitKey;
const OSSymbol *	gIODTCompatibleKey;
const OSSymbol * 	gIODTTypeKey;
const OSSymbol * 	gIODTModelKey;

const OSSymbol * 	gIODTSizeCellKey;
const OSSymbol * 	gIODTAddressCellKey;
const OSSymbol * 	gIODTRangeKey;

const OSSymbol *	gIODTPersistKey;

const OSSymbol *	gIODTDefaultInterruptController;
const OSSymbol *	gIODTAAPLInterruptsKey;
const OSSymbol *	gIODTPHandleKey;
const OSSymbol *	gIODTInterruptCellKey;
const OSSymbol *	gIODTInterruptParentKey;
const OSSymbol *	gIODTNWInterruptMappingKey;


static IORegistryEntry * MakeReferenceTable( DTEntry dtEntry, bool copy );
static void AddPHandle( IORegistryEntry * regEntry );
static void FreePhysicalMemory( vm_offset_t * range );

IORegistryEntry *
IODeviceTreeAlloc( void * dtTop )
{
    IORegistryEntry *	parent;
    IORegistryEntry *	child;
    IORegistryIterator * regIter;
    DTEntryIterator 	iter;
    DTEntry		dtChild;
    DTEntry		mapEntry;
    OSArray *		stack;
    OSData *		prop;
    OSObject *		obj;
    vm_offset_t *	dtMap;
    int			propSize;
    bool		intMap;
    bool		freeDT;

    IOLog("IODeviceTreeSupport ");

    gIODTPlane = IORegistryEntry::makePlane( kIODeviceTreePlane );

    gIODTNameKey 	= OSSymbol::withCStringNoCopy( "name" );
    gIODTUnitKey 	= OSSymbol::withCStringNoCopy( "AAPL,unit-string" );
    gIODTCompatibleKey 	= OSSymbol::withCStringNoCopy( "compatible" );
    gIODTTypeKey 	= OSSymbol::withCStringNoCopy( "device_type" );
    gIODTModelKey 	= OSSymbol::withCStringNoCopy( "model" );
    gIODTSizeCellKey 	= OSSymbol::withCStringNoCopy( "#size-cells" );
    gIODTAddressCellKey = OSSymbol::withCStringNoCopy( "#address-cells" );
    gIODTRangeKey 	= OSSymbol::withCStringNoCopy( "ranges" );

    gIODTPersistKey = OSSymbol::withCStringNoCopy( "IODTPersist" );

    assert(    gIODTPlane && gIODTCompatibleKey
            && gIODTTypeKey && gIODTModelKey
            && gIODTSizeCellKey && gIODTAddressCellKey && gIODTRangeKey
            && gIODTPersistKey );

    gIODTDefaultInterruptController
	= OSSymbol::withCStringNoCopy("IOPrimaryInterruptController");
    gIODTNWInterruptMappingKey
	= OSSymbol::withCStringNoCopy("IONWInterrupts");

    gIODTAAPLInterruptsKey
	= OSSymbol::withCStringNoCopy("AAPL,interrupts");
    gIODTPHandleKey
	= OSSymbol::withCStringNoCopy("AAPL,phandle");

    gIODTInterruptParentKey
	= OSSymbol::withCStringNoCopy("interrupt-parent");

    gIODTPHandles	= OSArray::withCapacity( 1 );
    gIODTPHandleMap	= OSArray::withCapacity( 1 );

    gIODTInterruptCellKey
	= OSSymbol::withCStringNoCopy("#interrupt-cells");

    assert(    gIODTDefaultInterruptController && gIODTNWInterruptMappingKey 
	    && gIODTAAPLInterruptsKey
	    && gIODTPHandleKey && gIODTInterruptParentKey
	    && gIODTPHandles && gIODTPHandleMap
            && gIODTInterruptCellKey
	 );

    freeDT = (kSuccess == DTLookupEntry( 0, "/chosen/memory-map", &mapEntry ))
	  && (kSuccess == DTGetProperty( mapEntry,
                "DeviceTree", (void **) &dtMap, &propSize ))
	  && ((2 * sizeof( vm_offset_t)) == propSize);

    parent = MakeReferenceTable( (DTEntry)dtTop, freeDT );

    stack = OSArray::withObjects( & (const OSObject *) parent, 1, 10 );
    DTCreateEntryIterator( (DTEntry)dtTop, &iter );

    do {
        parent = (IORegistryEntry *)stack->getObject( stack->getCount() - 1);
	//parent->release();
        stack->removeObject( stack->getCount() - 1);

        while( kSuccess == DTIterateEntries( iter, &dtChild) ) {

            child = MakeReferenceTable( dtChild, freeDT );
            child->attachToParent( parent, gIODTPlane);

	    AddPHandle( child );

            if( kSuccess == DTEnterEntry( iter, dtChild)) {
                stack->setObject( parent);
                parent = child;
            }
	    // only registry holds retain
	    child->release();
        }

    } while( stack->getCount()
	  && (kSuccess == DTExitEntry( iter, &dtChild)));

    stack->release();
    DTDisposeEntryIterator( iter);

    // parent is now root of the created tree

    // make root name first compatible entry (purely cosmetic)
    if( (prop = (OSData *) parent->getProperty( gIODTCompatibleKey))) {
	parent->setName( parent->getName(), gIODTPlane );
	parent->setName( (const char *) prop->getBytesNoCopy() );
    }

    // attach tree to meta root
    parent->attachToParent( IORegistryEntry::getRegistryRoot(), gIODTPlane);
    parent->release();

    if( freeDT ) {
        // free original device tree
        DTInit(0);
        IODTFreeLoaderInfo( "DeviceTree",
                            (void *)dtMap[0], round_page(dtMap[1]) );
    }

    // adjust tree
    intMap = false;
    regIter = IORegistryIterator::iterateOver( gIODTPlane,
						kIORegistryIterateRecursively );
    assert( regIter );
    if( regIter) {
	while( (child = regIter->getNextObject())) {
	    IODTMapInterrupts( child );
	    if( !intMap && child->getProperty( gIODTInterruptParentKey))
		intMap = true;

	    // Look for a "driver,AAPL,MacOSX,PowerPC" property.
	    if( (obj = child->getProperty( "driver,AAPL,MacOSX,PowerPC"))) {
	      gIOCatalogue->addExtensionsFromArchive((OSData *)obj);

	      child->removeProperty( "driver,AAPL,MacOSX,PowerPC");
	    }

	    // some gross pruning
            child->removeProperty( "lanLib,AAPL,MacOS,PowerPC");

	    if( (obj = child->getProperty( "driver,AAPL,MacOS,PowerPC"))) {

		if( (0 == (prop = (OSData *)child->getProperty( gIODTTypeKey )))
		 || (strcmp( "display", (char *) prop->getBytesNoCopy())) ) {

                    child->removeProperty( "driver,AAPL,MacOS,PowerPC");
		}
	    }
	}
	regIter->release();
    }

    if( intMap)
	// set a key in the root to indicate we found NW interrupt mapping
	parent->setProperty( gIODTNWInterruptMappingKey,
                    (OSObject *) gIODTNWInterruptMappingKey );

    IOLog("done\n");

    return( parent);
}

int IODTGetLoaderInfo( char *key, void **infoAddr, int *infoSize )
{
    IORegistryEntry		*chosen;
    OSData			*propObj;
    unsigned int		*propPtr;
    unsigned int		propSize;

    chosen = IORegistryEntry::fromPath( "/chosen/memory-map", gIODTPlane );
    if ( chosen == 0 ) return -1;

    propObj = OSDynamicCast( OSData, chosen->getProperty(key) );
    if ( propObj == 0 ) return -1;

    propSize = propObj->getLength();
    if ( propSize != (2 * sizeof(UInt32)) ) return -1;
 
    propPtr = (unsigned int *)propObj->getBytesNoCopy();
    if ( propPtr == 0 ) return -1;

    *infoAddr = (void *)propPtr[0] ;
    *infoSize = (int)   propPtr[1]; 

    return 0;
}

void IODTFreeLoaderInfo( char *key, void *infoAddr, int infoSize )
{
    vm_offset_t			range[2];
    IORegistryEntry		*chosen;

    range[0] = (vm_offset_t)infoAddr;
    range[1] = (vm_offset_t)infoSize;
    FreePhysicalMemory( range );

    if ( key != 0 ) {
        chosen = IORegistryEntry::fromPath( "/chosen/memory-map", gIODTPlane );
        if ( chosen != 0 ) {
            chosen->removeProperty(key);
        }
    }
}

static void FreePhysicalMemory( vm_offset_t * range )
{
    vm_offset_t	virt;

    virt = ml_static_ptovirt( range[0] );
    if( virt) {
        ml_static_mfree( virt, range[1] );
    }
}

static IORegistryEntry *
MakeReferenceTable( DTEntry dtEntry, bool copy )
{
    IORegistryEntry *	regEntry;
    OSDictionary *	propTable;
    const OSSymbol *	nameKey;
    OSData *		data;
    const OSSymbol *	sym;
    DTPropertyIterator	dtIter;
    void *		prop;
    int			propSize;
    char *		name;
    char		location[ 32 ];
    bool		noLocation = true;

    regEntry = new IOService;

    if( regEntry && (false == regEntry->init())) {
	regEntry->release();
	regEntry = 0;
    }

    if( regEntry &&
	(kSuccess == DTCreatePropertyIterator( dtEntry, &dtIter))) {

        propTable = regEntry->getPropertyTable();

	while( kSuccess == DTIterateProperties( dtIter, &name)) {

	    if(  kSuccess != DTGetProperty( dtEntry, name, &prop, &propSize ))
		continue;

	    if( copy) {
                nameKey = OSSymbol::withCString(name);
                data = OSData::withBytes(prop, propSize);
	    } else {
                nameKey = OSSymbol::withCStringNoCopy(name);
                data = OSData::withBytesNoCopy(prop, propSize);
	    }
	    assert( nameKey && data );

            propTable->setObject( nameKey, data);
	    data->release();
            nameKey->release();

	    if( nameKey == gIODTNameKey ) {
		if( copy)
                    sym = OSSymbol::withCString( (const char *) prop);
		else
                    sym = OSSymbol::withCStringNoCopy( (const char *) prop);
                regEntry->setName( sym );
		sym->release();

	    } else if( nameKey == gIODTUnitKey ) {
		// all OF strings are null terminated... except this one
		if( propSize >= (int) sizeof( location))
		    propSize = sizeof( location) - 1;
		strncpy( location, (const char *) prop, propSize );
		location[ propSize ] = 0;
                regEntry->setLocation( location );
		propTable->removeObject( gIODTUnitKey );
		noLocation = false;

	    } else if( noLocation && (0 == strcmp( name, "reg"))) {
		// default location - override later
                sprintf( location, "%lX", *((UInt32 *) prop) );
                regEntry->setLocation( location );
	    }
	}
	DTDisposePropertyIterator( dtIter);
    }

    return( regEntry);
}

static void AddPHandle( IORegistryEntry * regEntry )
{
    OSData *	data;

    if( regEntry->getProperty( gIODTInterruptCellKey)
     && (data = OSDynamicCast( OSData, regEntry->getProperty( gIODTPHandleKey )))) {
	// a possible interrupt-parent
	gIODTPHandles->setObject( data );
	gIODTPHandleMap->setObject( regEntry );
    }
}

static IORegistryEntry * FindPHandle( UInt32 phandle )
{
    OSData *		data;
    IORegistryEntry *	regEntry = 0;
    int			i;

    for( i = 0;
       (data = (OSData *)gIODTPHandles->getObject( i ));
       i++ ) {
            if( phandle == *((UInt32 *)data->getBytesNoCopy())) {
		regEntry = (IORegistryEntry *)
				gIODTPHandleMap->getObject( i );
		break;
        }
    }

    return( regEntry );
}

static bool GetUInt32( IORegistryEntry * regEntry, const OSSymbol * name,
			UInt32 * value )
{
    OSData *	data;

    if( (data = OSDynamicCast( OSData, regEntry->getProperty( name )))
     && (4 == data->getLength())) {
        *value = *((UInt32 *) data->getBytesNoCopy());
	return( true );
    } else
	return( false );
}

IORegistryEntry * IODTFindInterruptParent( IORegistryEntry * regEntry )
{
    IORegistryEntry *	parent;
    UInt32		phandle;

    if( GetUInt32( regEntry, gIODTInterruptParentKey, &phandle))
	parent = FindPHandle( phandle );

    else if( 0 == regEntry->getProperty( "interrupt-controller"))
	parent = regEntry->getParentEntry( gIODTPlane);
    else
	parent = 0;

    return( parent );
}

const OSSymbol * IODTInterruptControllerName( IORegistryEntry * regEntry )
{
    const OSSymbol *	sym;
    UInt32		phandle;
    bool		ok;
    char 		buf[48];

    ok = GetUInt32( regEntry, gIODTPHandleKey, &phandle);
    assert( ok );

    if( ok) {
        sprintf( buf, "IOInterruptController%08lX", phandle);
        sym = OSSymbol::withCString( buf );
    } else
	sym = 0;

    return( sym );
}

#define unexpected(a) { kprintf("unexpected %s:%d\n", __FILE__, __LINE__); a; }

static void IODTGetICellCounts( IORegistryEntry * regEntry,
			    UInt32 * iCellCount, UInt32 * aCellCount)
{
    if( !GetUInt32( regEntry, gIODTInterruptCellKey, iCellCount))
        unexpected( *iCellCount = 1 );
    if( !GetUInt32( regEntry, gIODTAddressCellKey, aCellCount))
        *aCellCount = 0;
}

UInt32 IODTMapOneInterrupt( IORegistryEntry * regEntry, UInt32 * intSpec,
				OSData ** spec, const OSSymbol ** controller )
{
    IORegistryEntry *	parent = 0;
    OSData *		data;
    UInt32 *		addrCmp;
    UInt32 *		maskCmp;
    UInt32 *		map;
    UInt32 *		endMap;
    UInt32		acells, icells, pacells, picells, cell;
    UInt32		i, skip = 0;
    bool		cmp, ok = false;

    do {
	if( parent && (data = OSDynamicCast( OSData,
				regEntry->getProperty( "interrupt-controller")))) {
	    // found a controller - don't want to follow cascaded controllers
            parent = 0;
            *spec = OSData::withBytesNoCopy( (void *) intSpec,
                                            icells * sizeof( UInt32));
            *controller = IODTInterruptControllerName( regEntry );
	    ok = (*spec && *controller);

	} else if( parent && (data = OSDynamicCast( OSData,
				regEntry->getProperty( "interrupt-map")))) {
            // interrupt-map
            map = (UInt32 *) data->getBytesNoCopy();
            endMap = map + (data->getLength() / sizeof(UInt32));
            data = OSDynamicCast( OSData, regEntry->getProperty( "interrupt-map-mask" ));
            if( data && (data->getLength() >= ((acells + icells) * sizeof( UInt32))))
                maskCmp = (UInt32 *) data->getBytesNoCopy();
	    else
		maskCmp = 0;

            do {
                for( i = 0, cmp = true;
                  cmp && (i < (acells + icells));
                  i++) {
                    cell = (i < acells) ? addrCmp[i] : intSpec[ i - acells ];
                    if( maskCmp)
                        cell &= maskCmp[i];
                    cmp = (cell == map[i]);
                }

                map += acells + icells;
                if( 0 == (parent = FindPHandle( *(map++) )))
                    unexpected(break);

                if( cmp)
                    intSpec = map;
		else {
		    IODTGetICellCounts( parent, &picells, &pacells );
                    map += pacells + picells;
                    parent = 0;
		}
            } while( !cmp && (map < endMap) );

	} else
            // first time (usually)
            parent = IODTFindInterruptParent( regEntry );

	if( parent) {
            IODTGetICellCounts( parent, &icells, &acells );
	    addrCmp = 0;
	    if( acells) {
                data = OSDynamicCast( OSData, regEntry->getProperty( "reg" ));
                if( data && (data->getLength() >= (acells * sizeof( UInt32))))
                    addrCmp = (UInt32 *) data->getBytesNoCopy();
	    }
	    regEntry = parent;
	    if( !skip)
		skip = icells;
	}
    } while( parent);

    if( ok)
        return( skip );
    else
        return( 0 );
}

bool IODTMapInterrupts( IORegistryEntry * regEntry )
{
    IORegistryEntry *	parent;
    OSData *		local;
    OSData *		local2;
    UInt32 *		localBits;
    UInt32 *		localEnd;
    OSData *		map;
    OSArray *		mapped;
    const OSSymbol *	controller;
    OSArray *		controllers;
    UInt32		skip = 1;
    bool		ok, nw;

    nw = (0 == (local = OSDynamicCast( OSData,
                              regEntry->getProperty( gIODTAAPLInterruptsKey))));
    if( nw
      && (0 == (local = OSDynamicCast( OSData,
                              regEntry->getProperty( "interrupts")))))
	return( true );		// nothing to see here

    if( nw && (parent = regEntry->getParentEntry( gIODTPlane))) {
	// check for bridges on old world
	if( (local2 = OSDynamicCast( OSData,
                              parent->getProperty( gIODTAAPLInterruptsKey)))) {
	    local = local2;
	    nw = false;
	}
    }

    localBits = (UInt32 *) local->getBytesNoCopy();
    localEnd = localBits + (local->getLength() / sizeof( UInt32));
    mapped = OSArray::withCapacity( 1 );
    controllers = OSArray::withCapacity( 1 );

    ok = (mapped && controllers);

    if( ok) do {
        if( nw) {
            skip = IODTMapOneInterrupt( regEntry, localBits, &map, &controller );
            if( 0 == skip) {
                IOLog("%s: error mapping interrupt[%d]\n",
                        regEntry->getName(), mapped->getCount());
                break;
            }
        } else {
            map = OSData::withData( local, mapped->getCount() * sizeof( UInt32),
                                    sizeof( UInt32));
            controller = gIODTDefaultInterruptController;
        }

        localBits += skip;
        mapped->setObject( map );
        map->release();
        controllers->setObject( (OSObject *) controller );
        controller->release();

    } while( localBits < localEnd);

    ok &= (localBits == localEnd);

    if( ok ) {
	// store results
        ok  = regEntry->setProperty( gIOInterruptControllersKey, controllers);
        ok &= regEntry->setProperty( gIOInterruptSpecifiersKey, mapped);
    }

    if( controllers)
        controllers->release();
    if( mapped)
        mapped->release();

    return( ok );
}

/*
 */

static const char *
CompareKey( OSString * key,
		const IORegistryEntry * table, const OSSymbol * propName )
{
    OSObject *		prop;
    OSData *		data;
    OSString *		string;
    const char *	ckey;
    UInt32		keyLen;
    const char *	names;
    const char *	lastName;
    bool		wild;
    bool		matched;
    const char *	result = 0;

    if( 0 == (prop = table->getProperty( propName )))
	return( 0 );

    if( (data = OSDynamicCast( OSData, prop ))) {
        names = (const char *) data->getBytesNoCopy();
        lastName = names + data->getLength();

    } else if( (string = OSDynamicCast( OSString, prop ))) {
        names = string->getCStringNoCopy();
        lastName = names + string->getLength() + 1;

    } else
	return( 0 );

    ckey = key->getCStringNoCopy();
    keyLen = key->getLength();
    wild = ('*' == key->getChar( keyLen - 1 ));

    do {
        // for each name in the property
        if( wild)
            matched = (0 == strncmp( ckey, names, keyLen - 1 ));
        else
            matched = (keyLen == strlen( names ))
                    && (0 == strncmp( ckey, names, keyLen ));

        if( matched)
            result = names;

        names = names + strlen( names) + 1;

    } while( (names < lastName) && (false == matched));

    return( result);
}


bool IODTCompareNubName( const IORegistryEntry * regEntry,
			 OSString * name, OSString ** matchingName )
{
    const char *	result;
    bool		matched;

    matched =  (0 != (result = CompareKey( name, regEntry, gIODTNameKey)))
	    || (0 != (result = CompareKey( name, regEntry, gIODTCompatibleKey)))
	    || (0 != (result = CompareKey( name, regEntry, gIODTTypeKey)))
	    || (0 != (result = CompareKey( name, regEntry, gIODTModelKey)));

    if( result && matchingName)
	*matchingName = OSString::withCString( result );

    return( result != 0 );
}

bool IODTMatchNubWithKeys( IORegistryEntry * regEntry,
                                    const char * keys )
{
    OSObject *		obj;
    bool		result = false;

    obj = OSUnserialize( keys, 0 );

    if( obj) {
        result = regEntry->compareNames( obj );
	obj->release();
    }
#ifdef DEBUG
    else IOLog("Couldn't unserialize %s\n", keys );
#endif

    return( result );
}

OSCollectionIterator * IODTFindMatchingEntries( IORegistryEntry * from,
			IOOptionBits options, const char * keys )
{
    OSSet *			result;
    IORegistryEntry *		next;
    IORegistryIterator *	iter;
    OSCollectionIterator *	cIter;
    bool			cmp;
    bool			minus = options & kIODTExclusive;

    result = OSSet::withCapacity( 3 );
    if( !result)
	return( 0);

    iter = IORegistryIterator::iterateOver( from, gIODTPlane,
	(options & kIODTRecursive) ? kIORegistryIterateRecursively : 0 );
    if( iter) {
        while( (next = iter->getNextObject())) {

            // Look for existence of a debug property to skip
            if( next->getProperty("AAPL,ignore"))
		continue;

	    if( keys) {
                cmp = IODTMatchNubWithKeys( next, keys );
                if( (minus && (false == cmp))
                || ((false == minus) && (false != cmp)) )
                    result->setObject( next);
	    } else
                result->setObject( next);
        }
        iter->release();
    }

    cIter = OSCollectionIterator::withCollection( result);
    result->release();

    return( cIter);
}


struct IODTPersistent {
    IODTCompareAddressCellFunc	compareFunc;
    IODTNVLocationFunc		locationFunc;
};

void IODTSetResolving( IORegistryEntry * 	regEntry,
		IODTCompareAddressCellFunc	compareFunc,
		IODTNVLocationFunc		locationFunc )
{
    IODTPersistent	persist;
    OSData	*	prop;

    persist.compareFunc = compareFunc;
    persist.locationFunc = locationFunc;
    prop = OSData::withBytes( &persist, sizeof( persist));
    if( !prop)
	return;

    regEntry->setProperty( gIODTPersistKey, prop);
    prop->release();
}

static SInt32 DefaultCompare( UInt32 cellCount, UInt32 left[], UInt32 right[] )
{
    cellCount--;
    return( left[ cellCount ] - right[ cellCount ] );
}


void IODTGetCellCounts( IORegistryEntry * regEntry,
			    UInt32 * sizeCount, UInt32 * addressCount)
{
    if( !GetUInt32( regEntry, gIODTSizeCellKey, sizeCount))
        *sizeCount = 1;
    if( !GetUInt32( regEntry, gIODTAddressCellKey, addressCount))
        *addressCount = 2;
}

// Given addr & len cells from our child, find it in our ranges property, then
// look in our parent to resolve the base of the range for us.

// Range[]: child-addr  our-addr  child-len
// #cells:    child       ours     child

bool IODTResolveAddressCell( IORegistryEntry * regEntry,
                             UInt32 cellsIn[],
                             IOPhysicalAddress * phys, IOPhysicalLength * len )
{
    IORegistryEntry *	parent;
    OSData *	prop;
    // cells in addresses at regEntry
    UInt32	sizeCells, addressCells;
    // cells in addresses below regEntry
    UInt32	childSizeCells, childAddressCells;
    UInt32	childCells;
    UInt32	cell[ 5 ], offset = 0, length;
    UInt32 *	range;
    UInt32 *	endRanges;
    bool	ok = true;
    SInt32	diff;

    IODTPersistent *		persist;
    IODTCompareAddressCellFunc	compare;

    IODTGetCellCounts( regEntry, &childSizeCells, &childAddressCells );
    childCells = childAddressCells + childSizeCells;

    bcopy( cellsIn, cell, 4 * childCells );
    if( childSizeCells > 1)
        *len = IOPhysical32( cellsIn[ childAddressCells ],
			     cellsIn[ childAddressCells + 1 ] );
    else
        *len = IOPhysical32( 0, cellsIn[ childAddressCells ] );

    do {
        prop = OSDynamicCast( OSData, regEntry->getProperty( gIODTRangeKey ));
        if( 0 == prop) {
	    /* end of the road */
            *phys = IOPhysical32( 0,  cell[ childAddressCells - 1 ] + offset);
            break;
        }

        parent = regEntry->getParentEntry( gIODTPlane );
	IODTGetCellCounts( parent, &sizeCells, &addressCells );

        if( (length = prop->getLength())) {
            // search
            range = (UInt32 *) prop->getBytesNoCopy();
            endRanges = range + (length / 4);

            prop = (OSData *) regEntry->getProperty( gIODTPersistKey );
            if( prop) {
                persist = (IODTPersistent *) prop->getBytesNoCopy();
                compare = persist->compareFunc;
            } else
                compare = DefaultCompare;

            for( ok = false;
                 range < endRanges;
                 range += (childCells + addressCells) ) {

                // is cell >= range start?
                diff = (*compare)( childAddressCells, cell, range );
                if( diff < 0)
                    continue;
                // is cell + size <= range end?
                if( (diff + cell[ childCells - 1 ])
                        > range[ childCells + addressCells - 1 ])
                    continue;

                offset += diff;
                ok = true;
                break;
            }

            // Get the physical start of the range from our parent
            bcopy( range + childAddressCells, cell, 4 * addressCells );
            bzero( cell + addressCells, 4 * sizeCells );

        } /* else zero length range => pass thru to parent */

	regEntry		= parent;
	childSizeCells		= sizeCells;
	childAddressCells	= addressCells;
	childCells		= childAddressCells + childSizeCells;

    } while( ok && regEntry);

    return( ok);
}


OSArray * IODTResolveAddressing( IORegistryEntry * regEntry,
			const char * addressPropertyName,
			IODeviceMemory * parent )
{
    IORegistryEntry *	parentEntry;
    OSData *		addressProperty;
    UInt32		sizeCells, addressCells, cells;
    int			i, num;
    UInt32 *		reg;
    IOPhysicalAddress	phys;
    IOPhysicalLength	len;
    OSArray *		array;
    IODeviceMemory *	range;

    parentEntry = regEntry->getParentEntry( gIODTPlane );
    addressProperty = (OSData *) regEntry->getProperty( addressPropertyName );
    if( (0 == addressProperty) || (0 == parentEntry))
	return( 0);

    IODTGetCellCounts( parentEntry, &sizeCells, &addressCells );
    if( 0 == sizeCells)
	return( 0);

    cells = sizeCells + addressCells;
    reg = (UInt32 *) addressProperty->getBytesNoCopy();
    num = addressProperty->getLength() / (4 * cells);

    array = OSArray::withCapacity( 1 );
    if( 0 == array)
	return( 0);

    for( i = 0; i < num; i++) {

	if( IODTResolveAddressCell( parentEntry, reg, &phys, &len )) {

	    range = 0;
	    if( parent)
		range = IODeviceMemory::withSubRange( parent,
                                phys - parent->getPhysicalAddress(), len );
	    if( 0 == range)
		range = IODeviceMemory::withRange( phys, len );
	    if( range)
                array->setObject( range );
	}
        reg += cells;
    }

    regEntry->setProperty( gIODeviceMemoryKey, array);
    array->release();	/* ??? */

    return( array);
}

static void IODTGetNVLocation(
	IORegistryEntry * parent,
	IORegistryEntry * regEntry,
	UInt8 * busNum, UInt8 * deviceNum, UInt8 * functionNum )
{

    OSData	*	prop;
    IODTPersistent *	persist;
    UInt32	*	cell;

    prop = (OSData *) parent->getProperty( gIODTPersistKey );
    if( prop) {
        persist = (IODTPersistent *) prop->getBytesNoCopy();
	(*persist->locationFunc)( regEntry, busNum, deviceNum, functionNum );

    } else {
        prop = (OSData *) regEntry->getProperty( "reg" );
        *functionNum	= 0;
        if( prop) {
            cell = (UInt32 *) prop->getBytesNoCopy();
#if 0
            if( (regHi & 0xf0000000) != 0xf0000000) {
                *bus 		= 0x03 & (regHi >> 16);
                *function 	= 0x07 & (regHi >> 8);
                *device 	= 0x1f & (regHi >> 11);
#endif
            *busNum 	= 3;
            *deviceNum 	= 0x1f & (cell[ 0 ] >> 24);
        } else {
            *busNum 	= 0;
            *deviceNum 	= 0;
	}
    }
}

/*
 * Try to make the same messed up descriptor as Mac OS
 */

IOReturn IODTMakeNVDescriptor( IORegistryEntry * regEntry,
				IONVRAMDescriptor * hdr )
{
    IORegistryEntry *	parent;
    UInt32		level;
    UInt32		bridgeDevices;
    UInt8		busNum;
    UInt8		deviceNum;
    UInt8		functionNum;

    hdr->format 	= 1;
    hdr->marker 	= 0;

    for(
	level = 0, bridgeDevices = 0;
	(parent = regEntry->getParentEntry( gIODTPlane ))
	&& (level < 7);
	level++ ) {

        IODTGetNVLocation( parent, regEntry,
                            &busNum, &deviceNum, &functionNum );
	if( level)
	    bridgeDevices |= ((deviceNum & 0x1f) << ((level - 1) * 5));
	else {
            hdr->busNum 	= busNum;
            hdr->deviceNum 	= deviceNum;
            hdr->functionNum 	= functionNum;
	}
	regEntry = parent;
    }
    hdr->bridgeCount 	= level - 2;
    hdr->bridgeDevices 	= bridgeDevices;

    return( kIOReturnSuccess );
}

OSData * IODTFindSlotName( IORegistryEntry * regEntry, UInt32 deviceNumber )
{
    IORegistryEntry *	parent;
    OSData *		data;
    OSData *		ret = 0;
    UInt32 *		bits;
    UInt32		i;
    char *		names;
    char *		lastName;
    UInt32		mask;

    data = (OSData *) regEntry->getProperty("AAPL,slot-name");
    if( data)
	return( data);
    parent = regEntry->getParentEntry( gIODTPlane );
    if( !parent)
	return( 0 );
    data = OSDynamicCast( OSData, parent->getProperty("slot-names"));
    if( !data)
	return( 0 );
    if( data->getLength() <= 4)
	return( 0 );

    bits = (UInt32 *) data->getBytesNoCopy();
    mask = *bits;
    if( (0 == (mask & (1 << deviceNumber))))
	return( 0 );

    names = (char *)(bits + 1);
    lastName = names + (data->getLength() - 4);

    for( i = 0;
        (i <= deviceNumber) && (names < lastName);
        i++ ) {

	if( mask & (1 << i)) {
            if( i == deviceNumber) {
		data = OSData::withBytesNoCopy( names, 1 + strlen( names));
		if( data) {
                    regEntry->setProperty("AAPL,slot-name", data);
                    ret = data;
		    data->release();
		}
            } else
                names += 1 + strlen( names);
        }
    }

    return( ret );
}