iokit/Kernel/IODeviceTreeSupport.cpp

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