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 #if defined (__i386__)
 306     virt = ml_boot_ptovirt( range[0] );
 307 #else
 308     virt = ml_static_ptovirt( range[0] );
 309 #endif
 310     if( virt) {
 311         ml_static_mfree( virt, range[1] );
 312     }
 313 }
 314
 315 static IORegistryEntry *
 316 MakeReferenceTable( DTEntry dtEntry, bool copy )
 317 {
 318     IORegistryEntry             *regEntry;
 319     OSDictionary                *propTable;
 320     const OSSymbol              *nameKey;
 321     OSData                              *data;
 322     const OSSymbol              *sym;
 323     DTPropertyIterator  dtIter;
 324     void                                *prop;
 325     int                                 propSize;
 326     char                                *name;
 327     char                                location[ 32 ];
 328     bool                                noLocation = true;
 329
 330     regEntry = new IOService;
 331
 332     if( regEntry && (false == regEntry->init())) {
 333         regEntry->release();
 334         regEntry = 0;
 335     }
 336
 337     if( regEntry &&
 338       (kSuccess == DTCreatePropertyIterator( dtEntry, &dtIter))) {
 339
 340         propTable = regEntry->getPropertyTable();
 341
 342         while( kSuccess == DTIterateProperties( dtIter, &name)) {
 343
 344             if(  kSuccess != DTGetProperty( dtEntry, name, &prop, &propSize ))
 345                 continue;
 346
 347             if( copy) {
 348                 nameKey = OSSymbol::withCString(name);
 349                 data = OSData::withBytes(prop, propSize);
 350             } else {
 351                 nameKey = OSSymbol::withCStringNoCopy(name);
 352                 data = OSData::withBytesNoCopy(prop, propSize);
 353             }
 354             assert( nameKey && data );
 355
 356             propTable->setObject( nameKey, data);
 357             data->release();
 358             nameKey->release();
 359
 360             if( nameKey == gIODTNameKey ) {
 361                 if( copy)
 362                     sym = OSSymbol::withCString( (const char *) prop);
 363                 else
 364                     sym = OSSymbol::withCStringNoCopy( (const char *) prop);
 365                 regEntry->setName( sym );
 366                 sym->release();
 367
 368             } else if( nameKey == gIODTUnitKey ) {
 369                 // all OF strings are null terminated... except this one
 370                 if( propSize >= (int) sizeof( location))
 371                     propSize = sizeof( location) - 1;
 372                 strncpy( location, (const char *) prop, propSize );
 373                 location[ propSize ] = 0;
 374                 regEntry->setLocation( location );
 375                 propTable->removeObject( gIODTUnitKey );
 376                 noLocation = false;
 377
 378             } else if( noLocation && (0 == strcmp( name, "reg"))) {
 379                 // default location - override later
 380                 sprintf( location, "%lX", *((UInt32 *) prop) );
 381                 regEntry->setLocation( location );
 382             }
 383         }
 384         DTDisposePropertyIterator( dtIter);
 385     }
 386
 387     return( regEntry);
 388 }
 389
 390 static void AddPHandle( IORegistryEntry * regEntry )
 391 {
 392     OSData *    data;
 393
 394     if( regEntry->getProperty( gIODTInterruptCellKey)
 395       && (data = OSDynamicCast( OSData, regEntry->getProperty( gIODTPHandleKey )))) {
 396         // a possible interrupt-parent
 397         gIODTPHandles->setObject( data );
 398         gIODTPHandleMap->setObject( regEntry );
 399     }
 400 }
 401
 402 static IORegistryEntry * FindPHandle( UInt32 phandle )
 403 {
 404     OSData                      *data;
 405     IORegistryEntry *regEntry = 0;
 406     int                         i;
 407
 408     for( i = 0; (data = (OSData *)gIODTPHandles->getObject( i )); i++ ) {
 409         if( phandle == *((UInt32 *)data->getBytesNoCopy())) {
 410             regEntry = (IORegistryEntry *)
 411             gIODTPHandleMap->getObject( i );
 412             break;
 413         }
 414     }
 415
 416     return( regEntry );
 417 }
 418
 419 static bool GetUInt32( IORegistryEntry * regEntry, const OSSymbol * name,
 420                         UInt32 * value )
 421 {
 422     OSData      *data;
 423
 424     if( (data = OSDynamicCast( OSData, regEntry->getProperty( name )))
 425       && (4 == data->getLength())) {
 426         *value = *((UInt32 *) data->getBytesNoCopy());
 427         return( true );
 428     } else
 429         return( false );
 430 }
 431
 432 IORegistryEntry * IODTFindInterruptParent( IORegistryEntry * regEntry )
 433 {
 434     IORegistryEntry *   parent;
 435     UInt32              phandle;
 436
 437     if( GetUInt32( regEntry, gIODTInterruptParentKey, &phandle))
 438         parent = FindPHandle( phandle );
 439
 440     else if( 0 == regEntry->getProperty( "interrupt-controller"))
 441         parent = regEntry->getParentEntry( gIODTPlane);
 442     else
 443         parent = 0;
 444
 445     return( parent );
 446 }
 447
 448 const OSSymbol * IODTInterruptControllerName( IORegistryEntry * regEntry )
 449 {
 450     const OSSymbol      *sym;
 451     UInt32              phandle;
 452     bool                ok;
 453     char                buf[48];
 454
 455     ok = GetUInt32( regEntry, gIODTPHandleKey, &phandle);
 456     assert( ok );
 457
 458     if( ok) {
 459         sprintf( buf, "IOInterruptController%08lX", phandle);
 460         sym = OSSymbol::withCString( buf );
 461     } else
 462         sym = 0;
 463
 464     return( sym );
 465 }
 466
 467 #define unexpected(a) { kprintf("unexpected %s:%d\n", __FILE__, __LINE__); a; }
 468
 469 static void IODTGetICellCounts( IORegistryEntry * regEntry,
 470                             UInt32 * iCellCount, UInt32 * aCellCount)
 471 {
 472     if( !GetUInt32( regEntry, gIODTInterruptCellKey, iCellCount))
 473         unexpected( *iCellCount = 1 );
 474     if( !GetUInt32( regEntry, gIODTAddressCellKey, aCellCount))
 475         *aCellCount = 0;
 476 }
 477
 478 UInt32 IODTMapOneInterrupt( IORegistryEntry * regEntry, UInt32 * intSpec,
 479                                 OSData ** spec, const OSSymbol ** controller )
 480 {
 481     IORegistryEntry *parent = 0;
 482     OSData                      *data;
 483     UInt32                      *addrCmp;
 484     UInt32                      *maskCmp;
 485     UInt32                      *map;
 486     UInt32                      *endMap;
 487     UInt32                      acells, icells, pacells, picells, cell;
 488     UInt32                      i, original_icells;
 489     bool                        cmp, ok = false;
 490
 491     parent = IODTFindInterruptParent( regEntry );
 492     IODTGetICellCounts( parent, &icells, &acells );
 493     addrCmp = 0;
 494     if( acells) {
 495         data = OSDynamicCast( OSData, regEntry->getProperty( "reg" ));
 496         if( data && (data->getLength() >= (acells * sizeof( UInt32))))
 497             addrCmp = (UInt32 *) data->getBytesNoCopy();
 498     }
 499     original_icells = icells;
 500     regEntry = parent;
 501
 502     do {
 503 #if IODTSUPPORTDEBUG
 504         kprintf ("IODTMapOneInterrupt: current regEntry name %s\n", regEntry->getName());
 505         kprintf ("acells - icells: ");
 506         for (i = 0; i < acells; i++) kprintf ("0x%08X ", addrCmp[i]);
 507         kprintf ("- ");
 508         for (i = 0; i < icells; i++) kprintf ("0x%08X ", intSpec[i]);
 509         kprintf ("\n");
 510 #endif
 511
 512         if( parent && (data = OSDynamicCast( OSData,
 513             regEntry->getProperty( "interrupt-controller")))) {
 514             // found a controller - don't want to follow cascaded controllers
 515             parent = 0;
 516             *spec = OSData::withBytesNoCopy( (void *) intSpec,
 517                                             icells * sizeof( UInt32));
 518             *controller = IODTInterruptControllerName( regEntry );
 519             ok = (*spec && *controller);
 520         } else if( parent && (data = OSDynamicCast( OSData,
 521                     regEntry->getProperty( "interrupt-map")))) {
 522             // interrupt-map
 523             map = (UInt32 *) data->getBytesNoCopy();
 524             endMap = map + (data->getLength() / sizeof(UInt32));
 525             data = OSDynamicCast( OSData, regEntry->getProperty( "interrupt-map-mask" ));
 526             if( data && (data->getLength() >= ((acells + icells) * sizeof( UInt32))))
 527                 maskCmp = (UInt32 *) data->getBytesNoCopy();
 528             else
 529                 maskCmp = 0;
 530
 531 #if IODTSUPPORTDEBUG
 532             if (maskCmp) {
 533                 kprintf ("        maskCmp: ");
 534                 for (i = 0; i < acells + icells; i++) {
 535                     if (i == acells)
 536                         kprintf ("- ");
 537                     kprintf ("0x%08X ", maskCmp[i]);
 538                 }
 539                 kprintf ("\n");
 540                 kprintf ("         masked: ");
 541                 for (i = 0; i < acells + icells; i++) {
 542                     if (i == acells)
 543                         kprintf ("- ");
 544                     kprintf ("0x%08X ", ((i < acells) ? addrCmp[i] : intSpec[i-acells]) & maskCmp[i]);
 545                 }
 546                 kprintf ("\n");
 547             } else
 548                 kprintf ("no maskCmp\n");
 549 #endif
 550             do {
 551 #if IODTSUPPORTDEBUG
 552                 kprintf ("            map: ");
 553                 for (i = 0; i < acells + icells; i++) {
 554                     if (i == acells)
 555                         kprintf ("- ");
 556                     kprintf ("0x%08X ", map[i]);
 557                 }
 558                 kprintf ("\n");
 559 #endif
 560                 for( i = 0, cmp = true; cmp && (i < (acells + icells)); i++) {
 561                     cell = (i < acells) ? addrCmp[i] : intSpec[ i - acells ];
 562                     if( maskCmp)
 563                         cell &= maskCmp[i];
 564                     cmp = (cell == map[i]);
 565                 }
 566
 567                 map += acells + icells;
 568                 if( 0 == (parent = FindPHandle( *(map++) )))
 569                     unexpected(break);
 570
 571                 IODTGetICellCounts( parent, &picells, &pacells );
 572                 if( cmp) {
 573                     addrCmp = map;
 574                     intSpec = map + pacells;
 575                     regEntry = parent;
 576                 } else {
 577                     map += pacells + picells;
 578                 }
 579             } while( !cmp && (map < endMap) );
 580             if (!cmp)
 581                 parent = 0;
 582         }
 583
 584         if( parent) {
 585             IODTGetICellCounts( parent, &icells, &acells );
 586             regEntry = parent;
 587         }
 588
 589     } while( parent);
 590
 591     return( ok ? original_icells : 0 );
 592 }
 593
 594 IOReturn IODTGetInterruptOptions( IORegistryEntry * regEntry, int source, IOOptionBits * options )
 595 {
 596     OSArray *   controllers;
 597     OSArray *   specifiers;
 598     OSArray *   shared;
 599     OSObject *  spec;
 600     OSObject *  oneSpec;
 601
 602     *options = 0;
 603
 604     controllers = OSDynamicCast(OSArray, regEntry->getProperty(gIOInterruptControllersKey));
 605     specifiers  = OSDynamicCast(OSArray, regEntry->getProperty(gIOInterruptSpecifiersKey));
 606
 607     if( !controllers || !specifiers)
 608         return (kIOReturnNoInterrupt);
 609
 610     shared = (OSArray *) gIODTSharedInterrupts->getObject(
 611                         (const OSSymbol *) controllers->getObject(source) );
 612     if (!shared)
 613         return (kIOReturnSuccess);
 614
 615     spec = specifiers->getObject(source);
 616     if (!spec)
 617         return (kIOReturnNoInterrupt);
 618
 619     for (unsigned int i = 0;
 620             (oneSpec = shared->getObject(i))
 621             && (!oneSpec->isEqualTo(spec));
 622             i++ )       {}
 623
 624     if (oneSpec)
 625         *options = kIODTInterruptShared;
 626
 627     return (kIOReturnSuccess);
 628 }
 629
 630 static bool IODTMapInterruptsSharing( IORegistryEntry * regEntry, OSDictionary * allInts )
 631 {
 632     IORegistryEntry *   parent;
 633     OSData *            local;
 634     OSData *            local2;
 635     UInt32 *            localBits;
 636     UInt32 *            localEnd;
 637     OSData *            map;
 638     OSObject *          oneMap;
 639     OSArray *           mapped;
 640     OSArray *           controllerInts;
 641     const OSSymbol *    controller;
 642     OSArray *           controllers;
 643     UInt32              skip = 1;
 644     bool                ok, nw;
 645
 646     nw = (0 == (local = OSDynamicCast( OSData,
 647         regEntry->getProperty( gIODTAAPLInterruptsKey))));
 648     if( nw && (0 == (local = OSDynamicCast( OSData,
 649         regEntry->getProperty( "interrupts")))))
 650         return( true );         // nothing to see here
 651
 652     if( nw && (parent = regEntry->getParentEntry( gIODTPlane))) {
 653         // check for bridges on old world
 654         if( (local2 = OSDynamicCast( OSData,
 655                 parent->getProperty( gIODTAAPLInterruptsKey)))) {
 656             local = local2;
 657             nw = false;
 658         }
 659     }
 660
 661     localBits = (UInt32 *) local->getBytesNoCopy();
 662     localEnd = localBits + (local->getLength() / sizeof( UInt32));
 663     mapped = OSArray::withCapacity( 1 );
 664     controllers = OSArray::withCapacity( 1 );
 665
 666     ok = (mapped && controllers);
 667
 668     if( ok) do {
 669         if( nw) {
 670             skip = IODTMapOneInterrupt( regEntry, localBits, &map, &controller );
 671             if( 0 == skip) {
 672                 IOLog("%s: error mapping interrupt[%d]\n",
 673                         regEntry->getName(), mapped->getCount());
 674                 break;
 675             }
 676         } else {
 677             map = OSData::withData( local, mapped->getCount() * sizeof( UInt32),
 678                                 sizeof( UInt32));
 679             controller = gIODTDefaultInterruptController;
 680             controller->retain();
 681         }
 682
 683         localBits += skip;
 684         mapped->setObject( map );
 685         controllers->setObject( controller );
 686
 687         if (allInts)
 688         {
 689             controllerInts = (OSArray *) allInts->getObject( controller );
 690             if (controllerInts)
 691             {
 692                 for (unsigned int i = 0; (oneMap = controllerInts->getObject(i)); i++)
 693                 {
 694                     if (map->isEqualTo(oneMap))
 695                     {
 696                         controllerInts = (OSArray *) gIODTSharedInterrupts->getObject( controller );
 697                         if (controllerInts)
 698                             controllerInts->setObject(map);
 699                         else
 700                         {
 701                             controllerInts = OSArray::withObjects( (const OSObject **) &map, 1, 4 );
 702                             if (controllerInts)
 703                             {
 704                                 gIODTSharedInterrupts->setObject( controller, controllerInts );
 705                                 controllerInts->release();
 706                             }
 707                         }
 708                         break;
 709                     }
 710                 }
 711                 if (!oneMap)
 712                     controllerInts->setObject(map);
 713             }
 714             else
 715             {
 716                 controllerInts = OSArray::withObjects( (const OSObject **) &map, 1, 16 );
 717                 if (controllerInts)
 718                 {
 719                     allInts->setObject( controller, controllerInts );
 720                     controllerInts->release();
 721                 }
 722             }
 723         }
 724
 725         map->release();
 726         controller->release();
 727
 728     } while( localBits < localEnd);
 729
 730     ok &= (localBits == localEnd);
 731
 732     if( ok ) {
 733         // store results
 734         ok  = regEntry->setProperty( gIOInterruptControllersKey, controllers);
 735         ok &= regEntry->setProperty( gIOInterruptSpecifiersKey, mapped);
 736     }
 737
 738     if( controllers)
 739         controllers->release();
 740     if( mapped)
 741         mapped->release();
 742
 743     return( ok );
 744 }
 745
 746 bool IODTMapInterrupts( IORegistryEntry * regEntry )
 747 {
 748     return( IODTMapInterruptsSharing( regEntry, 0 ));
 749 }
 750
 751 /*
 752  */
 753
 754 static const char *
 755 CompareKey( OSString * key,
 756                 const IORegistryEntry * table, const OSSymbol * propName )
 757 {
 758     OSObject            *prop;
 759     OSData                      *data;
 760     OSString            *string;
 761     const char          *ckey;
 762     UInt32                      keyLen;
 763     const char          *names;
 764     const char          *lastName;
 765     bool                        wild;
 766     bool                        matched;
 767     const char          *result = 0;
 768
 769     if( 0 == (prop = table->getProperty( propName )))
 770         return( 0 );
 771
 772     if( (data = OSDynamicCast( OSData, prop ))) {
 773         names = (const char *) data->getBytesNoCopy();
 774         lastName = names + data->getLength();
 775     } else if( (string = OSDynamicCast( OSString, prop ))) {
 776         names = string->getCStringNoCopy();
 777         lastName = names + string->getLength() + 1;
 778     } else
 779                 return( 0 );
 780
 781     ckey = key->getCStringNoCopy();
 782     keyLen = key->getLength();
 783     wild = ('*' == key->getChar( keyLen - 1 ));
 784
 785     do {
 786         // for each name in the property
 787         if( wild)
 788             matched = (0 == strncmp( ckey, names, keyLen - 1 ));
 789         else
 790             matched = (keyLen == strlen( names ))
 791                     && (0 == strncmp( ckey, names, keyLen ));
 792
 793         if( matched)
 794             result = names;
 795
 796         names = names + strlen( names) + 1;
 797
 798     } while( (names < lastName) && (false == matched));
 799
 800     return( result);
 801 }
 802
 803
 804 bool IODTCompareNubName( const IORegistryEntry * regEntry,
 805                          OSString * name, OSString ** matchingName )
 806 {
 807     const char          *result;
 808     bool                        matched;
 809
 810     matched =  (0 != (result = CompareKey( name, regEntry, gIODTNameKey)))
 811             || (0 != (result = CompareKey( name, regEntry, gIODTCompatibleKey)))
 812             || (0 != (result = CompareKey( name, regEntry, gIODTTypeKey)))
 813             || (0 != (result = CompareKey( name, regEntry, gIODTModelKey)));
 814
 815     if( result && matchingName)
 816         *matchingName = OSString::withCString( result );
 817
 818     return( result != 0 );
 819 }
 820
 821 bool IODTMatchNubWithKeys( IORegistryEntry * regEntry,
 822                                     const char * keys )
 823 {
 824     OSObject    *obj;
 825     bool                result = false;
 826
 827     obj = OSUnserialize( keys, 0 );
 828
 829     if( obj) {
 830         result = regEntry->compareNames( obj );
 831                 obj->release();
 832     }
 833 #ifdef DEBUG
 834     else IOLog("Couldn't unserialize %s\n", keys );
 835 #endif
 836
 837     return( result );
 838 }
 839
 840 OSCollectionIterator * IODTFindMatchingEntries( IORegistryEntry * from,
 841                         IOOptionBits options, const char * keys )
 842 {
 843     OSSet                                       *result = 0;
 844     IORegistryEntry                     *next;
 845     IORegistryIterator          *iter;
 846     OSCollectionIterator        *cIter;
 847     bool                                        cmp;
 848     bool                                        minus = options & kIODTExclusive;
 849
 850
 851     iter = IORegistryIterator::iterateOver( from, gIODTPlane,
 852                 (options & kIODTRecursive) ? kIORegistryIterateRecursively : 0 );
 853     if( iter) {
 854
 855         do {
 856
 857             if( result)
 858                 result->release();
 859             result = OSSet::withCapacity( 3 );
 860             if( !result)
 861                 break;
 862
 863             iter->reset();
 864             while( (next = iter->getNextObject())) {
 865
 866                 // Look for existence of a debug property to skip
 867                 if( next->getProperty("AAPL,ignore"))
 868                     continue;
 869
 870                 if( keys) {
 871                     cmp = IODTMatchNubWithKeys( next, keys );
 872                     if( (minus && (false == cmp))
 873                             || ((false == minus) && (false != cmp)) )
 874                         result->setObject( next);
 875                 } else
 876                     result->setObject( next);
 877             }
 878         } while( !iter->isValid());
 879
 880         iter->release();
 881     }
 882
 883     cIter = OSCollectionIterator::withCollection( result);
 884     result->release();
 885
 886     return( cIter);
 887 }
 888
 889
 890 struct IODTPersistent {
 891     IODTCompareAddressCellFunc  compareFunc;
 892     IODTNVLocationFunc          locationFunc;
 893 };
 894
 895 void IODTSetResolving( IORegistryEntry *        regEntry,
 896                 IODTCompareAddressCellFunc      compareFunc,
 897                 IODTNVLocationFunc              locationFunc )
 898 {
 899     IODTPersistent      persist;
 900     OSData                      *prop;
 901
 902     persist.compareFunc = compareFunc;
 903     persist.locationFunc = locationFunc;
 904     prop = OSData::withBytes( &persist, sizeof( persist));
 905     if( !prop)
 906         return;
 907
 908     regEntry->setProperty( gIODTPersistKey, prop);
 909     prop->release();
 910     return;
 911 }
 912
 913 static SInt32 DefaultCompare( UInt32 cellCount, UInt32 left[], UInt32 right[] )
 914 {
 915     cellCount--;
 916     return( left[ cellCount ] - right[ cellCount ] );
 917 }
 918
 919 void IODTGetCellCounts( IORegistryEntry * regEntry,
 920                             UInt32 * sizeCount, UInt32 * addressCount)
 921 {
 922     if( !GetUInt32( regEntry, gIODTSizeCellKey, sizeCount))
 923         *sizeCount = 1;
 924     if( !GetUInt32( regEntry, gIODTAddressCellKey, addressCount))
 925         *addressCount = 2;
 926     return;
 927 }
 928
 929 // Given addr & len cells from our child, find it in our ranges property, then
 930 // look in our parent to resolve the base of the range for us.
 931
 932 // Range[]: child-addr  our-addr  child-len
 933 // #cells:    child       ours     child
 934
 935 bool IODTResolveAddressCell( IORegistryEntry * regEntry,
 936                              UInt32 cellsIn[],
 937                              IOPhysicalAddress * phys, IOPhysicalLength * len )
 938 {
 939     IORegistryEntry     *parent;
 940     OSData              *prop;
 941     // cells in addresses at regEntry
 942     UInt32              sizeCells, addressCells;
 943     // cells in addresses below regEntry
 944     UInt32              childSizeCells, childAddressCells;
 945     UInt32              childCells;
 946     UInt32              cell[ 5 ], offset = 0, length;
 947     UInt32              endCell[ 5 ];
 948     UInt32              *range;
 949     UInt32              *lookRange;
 950     UInt32              *startRange;
 951     UInt32              *endRanges;
 952     bool                ok = true;
 953     SInt32              diff, endDiff;
 954
 955     IODTPersistent      *persist;
 956     IODTCompareAddressCellFunc  compare;
 957
 958     IODTGetCellCounts( regEntry, &childSizeCells, &childAddressCells );
 959     childCells = childAddressCells + childSizeCells;
 960
 961     bcopy( cellsIn, cell, 4 * childCells );
 962     if( childSizeCells > 1)
 963         *len = IOPhysical32( cellsIn[ childAddressCells ],
 964                              cellsIn[ childAddressCells + 1 ] );
 965     else
 966         *len = IOPhysical32( 0, cellsIn[ childAddressCells ] );
 967
 968     do
 969     {
 970         prop = OSDynamicCast( OSData, regEntry->getProperty( gIODTRangeKey ));
 971         if( 0 == prop) {
 972             /* end of the road */
 973             *phys = IOPhysical32( 0,  cell[ childAddressCells - 1 ] + offset);
 974             break;
 975         }
 976
 977         parent = regEntry->getParentEntry( gIODTPlane );
 978         IODTGetCellCounts( parent, &sizeCells, &addressCells );
 979
 980         if( (length = prop->getLength())) {
 981             // search
 982             startRange = (UInt32 *) prop->getBytesNoCopy();
 983             range = startRange;
 984             endRanges = range + (length / 4);
 985
 986             prop = (OSData *) regEntry->getProperty( gIODTPersistKey );
 987             if( prop) {
 988                 persist = (IODTPersistent *) prop->getBytesNoCopy();
 989                 compare = persist->compareFunc;
 990             } else
 991                 compare = DefaultCompare;
 992
 993             for( ok = false;
 994                  range < endRanges;
 995                  range += (childCells + addressCells) ) {
 996
 997                 // is cell start >= range start?
 998                 diff = (*compare)( childAddressCells, cell, range );
 999                 if( diff < 0)
1000                     continue;
1001
1002                 ok = (0 == cell[childCells - 1]);
1003                 if (!ok)
1004                 {
1005                     // search for cell end
1006                     bcopy(cell, endCell, childAddressCells * sizeof(UInt32));
1007                     endCell[childAddressCells - 1] += cell[childCells - 1] - 1;
1008                     lookRange = startRange;
1009                     for( ;
1010                          lookRange < endRanges;
1011                          lookRange += (childCells + addressCells) )
1012                      {
1013                         // is cell >= range start?
1014                         endDiff = (*compare)( childAddressCells, endCell, lookRange );
1015                         if( endDiff < 0)
1016                             continue;
1017                         if ((endDiff - cell[childCells - 1] + 1 + lookRange[childAddressCells + addressCells - 1])
1018                             == (diff + range[childAddressCells + addressCells - 1]))
1019                         {
1020                             ok = true;
1021                             break;
1022                         }
1023                     }
1024                     if (!ok)
1025                         continue;
1026                 }
1027                 offset += diff;
1028                 break;
1029             }
1030
1031             // Get the physical start of the range from our parent
1032             bcopy( range + childAddressCells, cell, 4 * addressCells );
1033             bzero( cell + addressCells, 4 * sizeCells );
1034
1035         } /* else zero length range => pass thru to parent */
1036
1037         regEntry                = parent;
1038         childSizeCells          = sizeCells;
1039         childAddressCells       = addressCells;
1040         childCells              = childAddressCells + childSizeCells;
1041     }
1042     while( ok && regEntry);
1043
1044     return( ok);
1045 }
1046
1047
1048 OSArray * IODTResolveAddressing( IORegistryEntry * regEntry,
1049                         const char * addressPropertyName,
1050                         IODeviceMemory * parent )
1051 {
1052     IORegistryEntry             *parentEntry;
1053     OSData                              *addressProperty;
1054     UInt32                              sizeCells, addressCells, cells;
1055     int                                 i, num;
1056     UInt32                              *reg;
1057     IOPhysicalAddress   phys;
1058     IOPhysicalLength    len;
1059     OSArray                             *array;
1060     IODeviceMemory              *range;
1061
1062     parentEntry = regEntry->getParentEntry( gIODTPlane );
1063     addressProperty = (OSData *) regEntry->getProperty( addressPropertyName );
1064     if( (0 == addressProperty) || (0 == parentEntry))
1065         return( 0);
1066
1067     IODTGetCellCounts( parentEntry, &sizeCells, &addressCells );
1068     if( 0 == sizeCells)
1069         return( 0);
1070
1071     cells = sizeCells + addressCells;
1072     reg = (UInt32 *) addressProperty->getBytesNoCopy();
1073     num = addressProperty->getLength() / (4 * cells);
1074
1075     array = OSArray::withCapacity( 1 );
1076     if( 0 == array)
1077         return( 0);
1078
1079     for( i = 0; i < num; i++) {
1080         if( IODTResolveAddressCell( parentEntry, reg, &phys, &len )) {
1081             range = 0;
1082             if( parent)
1083                 range = IODeviceMemory::withSubRange( parent,
1084                         phys - parent->getPhysicalAddress(), len );
1085             if( 0 == range)
1086                 range = IODeviceMemory::withRange( phys, len );
1087             if( range)
1088                 array->setObject( range );
1089         }
1090         reg += cells;
1091     }
1092
1093     regEntry->setProperty( gIODeviceMemoryKey, array);
1094     array->release();   /* ??? */
1095
1096     return( array);
1097 }
1098
1099 static void IODTGetNVLocation(
1100         IORegistryEntry * parent,
1101         IORegistryEntry * regEntry,
1102         UInt8 * busNum, UInt8 * deviceNum, UInt8 * functionNum )
1103 {
1104
1105     OSData                      *prop;
1106     IODTPersistent      *persist;
1107     UInt32                      *cell;
1108
1109     prop = (OSData *) parent->getProperty( gIODTPersistKey );
1110     if( prop) {
1111         persist = (IODTPersistent *) prop->getBytesNoCopy();
1112         (*persist->locationFunc)( regEntry, busNum, deviceNum, functionNum );
1113     } else {
1114         prop = (OSData *) regEntry->getProperty( "reg" );
1115         *functionNum    = 0;
1116         if( prop) {
1117             cell = (UInt32 *) prop->getBytesNoCopy();
1118             *busNum     = 3;
1119             *deviceNum  = 0x1f & (cell[ 0 ] >> 24);
1120         } else {
1121             *busNum     = 0;
1122             *deviceNum  = 0;
1123         }
1124     }
1125     return;
1126 }
1127
1128 /*
1129  * Try to make the same messed up descriptor as Mac OS
1130  */
1131
1132 IOReturn IODTMakeNVDescriptor( IORegistryEntry * regEntry,
1133                                 IONVRAMDescriptor * hdr )
1134 {
1135     IORegistryEntry             *parent;
1136     UInt32                              level;
1137     UInt32                              bridgeDevices;
1138     UInt8                               busNum;
1139     UInt8                               deviceNum;
1140     UInt8                               functionNum;
1141
1142     hdr->format         = 1;
1143     hdr->marker         = 0;
1144
1145     for(level = 0, bridgeDevices = 0;
1146         (parent = regEntry->getParentEntry( gIODTPlane )) && (level < 7); level++ ) {
1147
1148         IODTGetNVLocation( parent, regEntry,
1149                         &busNum, &deviceNum, &functionNum );
1150         if( level)
1151             bridgeDevices |= ((deviceNum & 0x1f) << ((level - 1) * 5));
1152         else {
1153             hdr->busNum         = busNum;
1154             hdr->deviceNum      = deviceNum;
1155             hdr->functionNum    = functionNum;
1156         }
1157         regEntry = parent;
1158     }
1159     hdr->bridgeCount    = level - 2;
1160     hdr->bridgeDevices  = bridgeDevices;
1161
1162     return( kIOReturnSuccess );
1163 }
1164
1165 OSData * IODTFindSlotName( IORegistryEntry * regEntry, UInt32 deviceNumber )
1166 {
1167     IORegistryEntry             *parent;
1168     OSData                              *data;
1169     OSData                              *ret = 0;
1170     UInt32                              *bits;
1171     UInt32                              i;
1172     char                                *names;
1173     char                                *lastName;
1174     UInt32                              mask;
1175
1176     data = (OSData *) regEntry->getProperty("AAPL,slot-name");
1177     if( data)
1178         return( data);
1179     parent = regEntry->getParentEntry( gIODTPlane );
1180     if( !parent)
1181         return( 0 );
1182     data = OSDynamicCast( OSData, parent->getProperty("slot-names"));
1183     if( !data)
1184         return( 0 );
1185     if( data->getLength() <= 4)
1186         return( 0 );
1187
1188     bits = (UInt32 *) data->getBytesNoCopy();
1189     mask = *bits;
1190     if( (0 == (mask & (1 << deviceNumber))))
1191         return( 0 );
1192
1193     names = (char *)(bits + 1);
1194     lastName = names + (data->getLength() - 4);
1195
1196     for( i = 0; (i <= deviceNumber) && (names < lastName); i++ ) {
1197
1198         if( mask & (1 << i)) {
1199             if( i == deviceNumber) {
1200                 data = OSData::withBytesNoCopy( names, 1 + strlen( names));
1201                 if( data) {
1202                     regEntry->setProperty("AAPL,slot-name", data);
1203                     ret = data;
1204                     data->release();
1205                 }
1206             } else
1207                 names += 1 + strlen( names);
1208         }
1209     }
1210
1211     return( ret );
1212 }
1213
1214 extern "C" IOReturn IONDRVLibrariesInitialize( IOService * provider )
1215 {
1216     return( kIOReturnUnsupported );
1217 }