iokit/Kernel/IODeviceTreeSupport.cpp

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