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