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