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