iokit/Kernel/IODeviceTreeSupport.cpp

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