iokit/Kernel/IODeviceTreeSupport.cpp

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