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     OSObject * obj;
 434     OSData   * data;
 435     bool       result;
 436
 437     if (!(obj = regEntry->copyProperty(name))) return (false);
 438
 439     result = ((data = OSDynamicCast(OSData, obj)) && (sizeof(UInt32) == data->getLength()));
 440     if (result) *value = *((UInt32 *) data->getBytesNoCopy());
 441
 442     obj->release();
 443     return(result);
 444 }
 445
 446 static IORegistryEntry * IODTFindInterruptParent( IORegistryEntry * regEntry, IOItemCount index )
 447 {
 448     IORegistryEntry *   parent;
 449     UInt32              phandle;
 450     OSData          *   data;
 451     unsigned int        len;
 452
 453     if( (data = OSDynamicCast( OSData, regEntry->getProperty( gIODTInterruptParentKey )))
 454       && (sizeof(UInt32) <= (len = data->getLength()))) {
 455         if (((index + 1) * sizeof(UInt32)) > len)
 456             index = 0;
 457         phandle = ((UInt32 *) data->getBytesNoCopy())[index];
 458         parent = FindPHandle( phandle );
 459
 460     } else if( 0 == regEntry->getProperty( "interrupt-controller"))
 461         parent = regEntry->getParentEntry( gIODTPlane);
 462     else
 463         parent = 0;
 464
 465     return( parent );
 466 }
 467
 468 const OSSymbol * IODTInterruptControllerName( IORegistryEntry * regEntry )
 469 {
 470     const OSSymbol      *sym;
 471     UInt32              phandle;
 472     bool                ok;
 473     char                buf[48];
 474
 475     ok = GetUInt32( regEntry, gIODTPHandleKey, &phandle);
 476     assert( ok );
 477
 478     if( ok) {
 479         snprintf(buf, sizeof(buf), "IOInterruptController%08X", (uint32_t)phandle);
 480         sym = OSSymbol::withCString( buf );
 481     } else
 482         sym = 0;
 483
 484     return( sym );
 485 }
 486
 487 #define unexpected(a) { kprintf("unexpected %s:%d\n", __FILE__, __LINE__); a; }
 488
 489 static void IODTGetICellCounts( IORegistryEntry * regEntry,
 490                             UInt32 * iCellCount, UInt32 * aCellCount)
 491 {
 492     if( !GetUInt32( regEntry, gIODTInterruptCellKey, iCellCount))
 493         unexpected( *iCellCount = 1 );
 494     if( !GetUInt32( regEntry, gIODTAddressCellKey, aCellCount))
 495         *aCellCount = 0;
 496 }
 497
 498 static UInt32 IODTMapOneInterrupt( IORegistryEntry * regEntry, UInt32 * intSpec, UInt32 index,
 499                                     OSData ** spec, const OSSymbol ** controller )
 500 {
 501     IORegistryEntry *parent = 0;
 502     OSData                      *data;
 503     UInt32                      *addrCmp;
 504     UInt32                      *maskCmp;
 505     UInt32                      *map;
 506     UInt32                      *endMap;
 507     UInt32                      acells, icells, pacells, picells, cell;
 508     UInt32                      i, original_icells;
 509     bool                        cmp, ok = false;
 510
 511     parent = IODTFindInterruptParent( regEntry, index );
 512     IODTGetICellCounts( parent, &icells, &acells );
 513     addrCmp = 0;
 514     if( acells) {
 515         data = OSDynamicCast( OSData, regEntry->getProperty( "reg" ));
 516         if( data && (data->getLength() >= (acells * sizeof(UInt32))))
 517             addrCmp = (UInt32 *) data->getBytesNoCopy();
 518     }
 519     original_icells = icells;
 520     regEntry = parent;
 521
 522     do {
 523 #if IODTSUPPORTDEBUG
 524         kprintf ("IODTMapOneInterrupt: current regEntry name %s\n", regEntry->getName());
 525         kprintf ("acells - icells: ");
 526         for (i = 0; i < acells; i++) kprintf ("0x%08X ", addrCmp[i]);
 527         kprintf ("- ");
 528         for (i = 0; i < icells; i++) kprintf ("0x%08X ", intSpec[i]);
 529         kprintf ("\n");
 530 #endif
 531
 532         if( parent && (data = OSDynamicCast( OSData,
 533             regEntry->getProperty( "interrupt-controller")))) {
 534             // found a controller - don't want to follow cascaded controllers
 535             parent = 0;
 536             *spec = OSData::withBytesNoCopy( (void *) intSpec,
 537                                             icells * sizeof(UInt32));
 538             *controller = IODTInterruptControllerName( regEntry );
 539             ok = (*spec && *controller);
 540         } else if( parent && (data = OSDynamicCast( OSData,
 541                     regEntry->getProperty( "interrupt-map")))) {
 542             // interrupt-map
 543             map = (UInt32 *) data->getBytesNoCopy();
 544             endMap = map + (data->getLength() / sizeof(UInt32));
 545             data = OSDynamicCast( OSData, regEntry->getProperty( "interrupt-map-mask" ));
 546             if( data && (data->getLength() >= ((acells + icells) * sizeof(UInt32))))
 547                 maskCmp = (UInt32 *) data->getBytesNoCopy();
 548             else
 549                 maskCmp = 0;
 550
 551 #if IODTSUPPORTDEBUG
 552             if (maskCmp) {
 553                 kprintf ("        maskCmp: ");
 554                 for (i = 0; i < acells + icells; i++) {
 555                     if (i == acells)
 556                         kprintf ("- ");
 557                     kprintf ("0x%08X ", maskCmp[i]);
 558                 }
 559                 kprintf ("\n");
 560                 kprintf ("         masked: ");
 561                 for (i = 0; i < acells + icells; i++) {
 562                     if (i == acells)
 563                         kprintf ("- ");
 564                     kprintf ("0x%08X ", ((i < acells) ? addrCmp[i] : intSpec[i-acells]) & maskCmp[i]);
 565                 }
 566                 kprintf ("\n");
 567             } else
 568                 kprintf ("no maskCmp\n");
 569 #endif
 570             do {
 571 #if IODTSUPPORTDEBUG
 572                 kprintf ("            map: ");
 573                 for (i = 0; i < acells + icells; i++) {
 574                     if (i == acells)
 575                         kprintf ("- ");
 576                     kprintf ("0x%08X ", map[i]);
 577                 }
 578                 kprintf ("\n");
 579 #endif
 580                 for( i = 0, cmp = true; cmp && (i < (acells + icells)); i++) {
 581                     cell = (i < acells) ? addrCmp[i] : intSpec[ i - acells ];
 582                     if( maskCmp)
 583                         cell &= maskCmp[i];
 584                     cmp = (cell == map[i]);
 585                 }
 586
 587                 map += acells + icells;
 588                 if( 0 == (parent = FindPHandle( *(map++) )))
 589                     unexpected(break);
 590
 591                 IODTGetICellCounts( parent, &picells, &pacells );
 592                 if( cmp) {
 593                     addrCmp = map;
 594                     intSpec = map + pacells;
 595                     regEntry = parent;
 596                 } else {
 597                     map += pacells + picells;
 598                 }
 599             } while( !cmp && (map < endMap) );
 600             if (!cmp)
 601                 parent = 0;
 602         }
 603
 604         if( parent) {
 605             IODTGetICellCounts( parent, &icells, &acells );
 606             regEntry = parent;
 607         }
 608
 609     } while( parent);
 610
 611     return( ok ? original_icells : 0 );
 612 }
 613
 614 IOReturn IODTGetInterruptOptions( IORegistryEntry * regEntry, int source, IOOptionBits * options )
 615 {
 616     OSArray *   controllers;
 617     OSArray *   specifiers;
 618     OSArray *   shared;
 619     OSObject *  spec;
 620     OSObject *  oneSpec;
 621
 622     *options = 0;
 623
 624     controllers = OSDynamicCast(OSArray, regEntry->getProperty(gIOInterruptControllersKey));
 625     specifiers  = OSDynamicCast(OSArray, regEntry->getProperty(gIOInterruptSpecifiersKey));
 626
 627     if( !controllers || !specifiers)
 628         return (kIOReturnNoInterrupt);
 629
 630     shared = (OSArray *) gIODTSharedInterrupts->getObject(
 631                         (const OSSymbol *) controllers->getObject(source) );
 632     if (!shared)
 633         return (kIOReturnSuccess);
 634
 635     spec = specifiers->getObject(source);
 636     if (!spec)
 637         return (kIOReturnNoInterrupt);
 638
 639     for (unsigned int i = 0;
 640             (oneSpec = shared->getObject(i))
 641             && (!oneSpec->isEqualTo(spec));
 642             i++ )       {}
 643
 644     if (oneSpec)
 645         *options = kIODTInterruptShared;
 646
 647     return (kIOReturnSuccess);
 648 }
 649
 650 static bool IODTMapInterruptsSharing( IORegistryEntry * regEntry, OSDictionary * allInts )
 651 {
 652     IORegistryEntry *   parent;
 653     OSData *            local;
 654     OSData *            local2;
 655     UInt32 *            localBits;
 656     UInt32 *            localEnd;
 657     IOItemCount         index;
 658     OSData *            map;
 659     OSObject *          oneMap;
 660     OSArray *           mapped;
 661     OSArray *           controllerInts;
 662     const OSSymbol *    controller = 0;
 663     OSArray *           controllers;
 664     UInt32              skip = 1;
 665     bool                ok, nw;
 666
 667     nw = (0 == (local = OSDynamicCast( OSData,
 668         regEntry->getProperty( gIODTAAPLInterruptsKey))));
 669     if( nw && (0 == (local = OSDynamicCast( OSData,
 670         regEntry->getProperty( "interrupts")))))
 671         return( true );         // nothing to see here
 672
 673     if( nw && (parent = regEntry->getParentEntry( gIODTPlane))) {
 674         // check for bridges on old world
 675         if( (local2 = OSDynamicCast( OSData,
 676                 parent->getProperty( gIODTAAPLInterruptsKey)))) {
 677             local = local2;
 678             nw = false;
 679         }
 680     }
 681
 682     localBits = (UInt32 *) local->getBytesNoCopy();
 683     localEnd = localBits + (local->getLength() / sizeof(UInt32));
 684     index = 0;
 685     mapped = OSArray::withCapacity( 1 );
 686     controllers = OSArray::withCapacity( 1 );
 687
 688     ok = (mapped && controllers);
 689
 690     if( ok) do {
 691         if( nw) {
 692             skip = IODTMapOneInterrupt( regEntry, localBits, index, &map, &controller );
 693             if( 0 == skip) {
 694                 IOLog("%s: error mapping interrupt[%d]\n",
 695                         regEntry->getName(), mapped->getCount());
 696                 break;
 697             }
 698         } else {
 699             map = OSData::withData( local, mapped->getCount() * sizeof(UInt32),
 700                                 sizeof(UInt32));
 701             controller = gIODTDefaultInterruptController;
 702             controller->retain();
 703         }
 704
 705         index++;
 706         localBits += skip;
 707         mapped->setObject( map );
 708         controllers->setObject( controller );
 709
 710         if (allInts)
 711         {
 712             controllerInts = (OSArray *) allInts->getObject( controller );
 713             if (controllerInts)
 714             {
 715                 for (unsigned int i = 0; (oneMap = controllerInts->getObject(i)); i++)
 716                 {
 717                     if (map->isEqualTo(oneMap))
 718                     {
 719                         controllerInts = (OSArray *) gIODTSharedInterrupts->getObject( controller );
 720                         if (controllerInts)
 721                             controllerInts->setObject(map);
 722                         else
 723                         {
 724                             controllerInts = OSArray::withObjects( (const OSObject **) &map, 1, 4 );
 725                             if (controllerInts)
 726                             {
 727                                 gIODTSharedInterrupts->setObject( controller, controllerInts );
 728                                 controllerInts->release();
 729                             }
 730                         }
 731                         break;
 732                     }
 733                 }
 734                 if (!oneMap)
 735                     controllerInts->setObject(map);
 736             }
 737             else
 738             {
 739                 controllerInts = OSArray::withObjects( (const OSObject **) &map, 1, 16 );
 740                 if (controllerInts)
 741                 {
 742                     allInts->setObject( controller, controllerInts );
 743                     controllerInts->release();
 744                 }
 745             }
 746         }
 747
 748         map->release();
 749         controller->release();
 750
 751     } while( localBits < localEnd);
 752
 753     ok &= (localBits == localEnd);
 754
 755     if( ok ) {
 756         // store results
 757         ok  = regEntry->setProperty( gIOInterruptControllersKey, controllers);
 758         ok &= regEntry->setProperty( gIOInterruptSpecifiersKey, mapped);
 759     }
 760
 761     if( controllers)
 762         controllers->release();
 763     if( mapped)
 764         mapped->release();
 765
 766     return( ok );
 767 }
 768
 769 bool IODTMapInterrupts( IORegistryEntry * regEntry )
 770 {
 771     return( IODTMapInterruptsSharing( regEntry, 0 ));
 772 }
 773
 774 /*
 775  */
 776
 777 static bool
 778 CompareKey( OSString * key,
 779                 const IORegistryEntry * table, const OSSymbol * propName,
 780                 OSString ** matchingName )
 781 {
 782     OSObject            *prop;
 783     OSData                      *data;
 784     OSString            *string;
 785     const char          *ckey;
 786     UInt32                      keyLen;
 787     UInt32          nlen;
 788     const char          *names;
 789     const char          *lastName;
 790     bool                        wild;
 791     bool                        matched;
 792     const char          *result = 0;
 793
 794     if( 0 == (prop = table->copyProperty( propName ))) return( 0 );
 795
 796     if( (data = OSDynamicCast( OSData, prop ))) {
 797         names = (const char *) data->getBytesNoCopy();
 798         lastName = names + data->getLength();
 799     } else if( (string = OSDynamicCast( OSString, prop ))) {
 800         names = string->getCStringNoCopy();
 801         lastName = names + string->getLength() + 1;
 802     } else names = 0;
 803
 804         if (names) {
 805                 ckey = key->getCStringNoCopy();
 806                 keyLen = key->getLength();
 807                 wild = ('*' == key->getChar( keyLen - 1 ));
 808
 809                 do {
 810                         // for each name in the property
 811                         nlen = strnlen(names, lastName - names);
 812                         if( wild)
 813                                 matched = ((nlen >= (keyLen - 1)) && (0 == strncmp(ckey, names, keyLen - 1)));
 814                         else
 815                                 matched = (keyLen == nlen) && (0 == strncmp(ckey, names, keyLen));
 816
 817                         if( matched)
 818                                 result = names;
 819
 820                         names = names + nlen + 1;
 821
 822                 } while( (names < lastName) && (false == matched));
 823         }
 824
 825     if (result && matchingName) *matchingName = OSString::withCString( result );
 826
 827         if (prop) prop->release();
 828
 829     return (result != 0);
 830 }
 831
 832
 833 bool IODTCompareNubName( const IORegistryEntry * regEntry,
 834                          OSString * name, OSString ** matchingName )
 835 {
 836     bool matched;
 837
 838     matched = CompareKey( name, regEntry, gIODTNameKey,       matchingName)
 839                    || CompareKey( name, regEntry, gIODTCompatibleKey, matchingName)
 840                    || CompareKey( name, regEntry, gIODTTypeKey,       matchingName)
 841                    || CompareKey( name, regEntry, gIODTModelKey,      matchingName);
 842
 843     return (matched);
 844 }
 845
 846 bool IODTMatchNubWithKeys( IORegistryEntry * regEntry,
 847                                     const char * keys )
 848 {
 849     OSObject    *obj;
 850     bool                result = false;
 851
 852     obj = OSUnserialize( keys, 0 );
 853
 854     if( obj) {
 855         result = regEntry->compareNames( obj );
 856                 obj->release();
 857     }
 858 #if DEBUG
 859     else IOLog("Couldn't unserialize %s\n", keys );
 860 #endif
 861
 862     return( result );
 863 }
 864
 865 OSCollectionIterator * IODTFindMatchingEntries( IORegistryEntry * from,
 866                         IOOptionBits options, const char * keys )
 867 {
 868     OSSet                                       *result = 0;
 869     IORegistryEntry                     *next;
 870     IORegistryIterator          *iter;
 871     OSCollectionIterator        *cIter;
 872     bool                                        cmp;
 873     bool                                        minus = options & kIODTExclusive;
 874
 875
 876     iter = IORegistryIterator::iterateOver( from, gIODTPlane,
 877                 (options & kIODTRecursive) ? kIORegistryIterateRecursively : 0 );
 878     if( iter) {
 879
 880         do {
 881
 882             if( result)
 883                 result->release();
 884             result = OSSet::withCapacity( 3 );
 885             if( !result)
 886                 break;
 887
 888             iter->reset();
 889             while( (next = iter->getNextObject())) {
 890
 891                 // Look for existence of a debug property to skip
 892                 if( next->getProperty("AAPL,ignore"))
 893                     continue;
 894
 895                 if( keys) {
 896                     cmp = IODTMatchNubWithKeys( next, keys );
 897                     if( (minus && (false == cmp))
 898                             || ((false == minus) && (false != cmp)) )
 899                         result->setObject( next);
 900                 } else
 901                     result->setObject( next);
 902             }
 903         } while( !iter->isValid());
 904
 905         iter->release();
 906     }
 907
 908     cIter = OSCollectionIterator::withCollection( result);
 909     if (result) result->release();
 910
 911     return( cIter);
 912 }
 913
 914
 915 struct IODTPersistent {
 916     IODTCompareAddressCellFunc  compareFunc;
 917     IODTNVLocationFunc          locationFunc;
 918 };
 919
 920 void IODTSetResolving( IORegistryEntry *        regEntry,
 921                 IODTCompareAddressCellFunc      compareFunc,
 922                 IODTNVLocationFunc              locationFunc )
 923 {
 924     IODTPersistent      persist;
 925     OSData                      *prop;
 926
 927     persist.compareFunc = compareFunc;
 928     persist.locationFunc = locationFunc;
 929     prop = OSData::withBytes( &persist, sizeof(persist));
 930     if( !prop)
 931         return;
 932
 933     prop->setSerializable(false);
 934     regEntry->setProperty( gIODTPersistKey, prop);
 935     prop->release();
 936     return;
 937 }
 938
 939 #if   defined(__arm__) || defined(__i386__) || defined(__x86_64__)
 940 static SInt32 DefaultCompare( UInt32 cellCount, UInt32 left[], UInt32 right[] )
 941 {
 942         cellCount--;
 943         return( left[ cellCount ] - right[ cellCount ] );
 944 }
 945 #else
 946 #error Unknown architecture.
 947 #endif
 948
 949 static void AddLengthToCells( UInt32 numCells, UInt32 *cells, UInt64 offset)
 950 {
 951     if (numCells == 1)
 952     {
 953         cells[0] += (UInt32)offset;
 954     }
 955     else {
 956         UInt64 sum = cells[numCells - 1] + offset;
 957         cells[numCells - 1] = (UInt32)sum;
 958         if (sum > UINT32_MAX) {
 959             cells[numCells - 2] += (UInt32)(sum >> 32);
 960         }
 961     }
 962 }
 963
 964 static IOPhysicalAddress CellsValue( UInt32 numCells, UInt32 *cells)
 965 {
 966     if (numCells == 1) {
 967         return IOPhysical32( 0, cells[0] );
 968     } else {
 969         return IOPhysical32( cells[numCells - 2], cells[numCells - 1] );
 970     }
 971 }
 972
 973 void IODTGetCellCounts( IORegistryEntry * regEntry,
 974                             UInt32 * sizeCount, UInt32 * addressCount)
 975 {
 976     if( !GetUInt32( regEntry, gIODTSizeCellKey, sizeCount))
 977         *sizeCount = 1;
 978     if( !GetUInt32( regEntry, gIODTAddressCellKey, addressCount))
 979         *addressCount = 2;
 980     return;
 981 }
 982
 983 // Given addr & len cells from our child, find it in our ranges property, then
 984 // look in our parent to resolve the base of the range for us.
 985
 986 // Range[]: child-addr  our-addr  child-len
 987 // #cells:    child       ours     child
 988
 989 bool IODTResolveAddressCell( IORegistryEntry * regEntry,
 990                              UInt32 cellsIn[],
 991                              IOPhysicalAddress * phys, IOPhysicalLength * lenOut )
 992 {
 993     IORegistryEntry     *parent;
 994     OSData              *prop;
 995     // cells in addresses at regEntry
 996     UInt32              sizeCells, addressCells;
 997     // cells in addresses below regEntry
 998     UInt32              childSizeCells, childAddressCells;
 999     UInt32              childCells;
1000     UInt32              cell[ 8 ], propLen;
1001     UInt64              offset = 0;
1002     UInt32              endCell[ 8 ];
1003     UInt32              *range;
1004     UInt32              *lookRange;
1005     UInt32              *startRange;
1006     UInt32              *endRanges;
1007     bool                ok = true;
1008     SInt64              diff, diff2, endDiff;
1009     UInt64              len, rangeLen;
1010
1011     IODTPersistent      *persist;
1012     IODTCompareAddressCellFunc  compare;
1013
1014     IODTGetCellCounts( regEntry, &childSizeCells, &childAddressCells );
1015     childCells = childAddressCells + childSizeCells;
1016
1017     if (childCells > sizeof(cell)/sizeof(cell[0]))
1018         panic("IODTResolveAddressCell: Invalid device tree (%u,%u)", (uint32_t)childAddressCells, (uint32_t)childSizeCells);
1019
1020     bcopy( cellsIn, cell, sizeof(UInt32) * childCells );
1021     *lenOut = CellsValue( childSizeCells, cellsIn + childAddressCells );
1022
1023     do
1024     {
1025         prop = OSDynamicCast( OSData, regEntry->getProperty( gIODTRangeKey ));
1026         if( 0 == prop) {
1027             /* end of the road */
1028             *phys = CellsValue( childAddressCells, cell );
1029             *phys += offset;
1030             break;
1031         }
1032
1033         parent = regEntry->getParentEntry( gIODTPlane );
1034         IODTGetCellCounts( parent, &sizeCells, &addressCells );
1035
1036         if( (propLen = prop->getLength())) {
1037             // search
1038             startRange = (UInt32 *) prop->getBytesNoCopy();
1039             range = startRange;
1040             endRanges = range + (propLen / sizeof(UInt32));
1041
1042             prop = (OSData *) regEntry->getProperty( gIODTPersistKey );
1043             if( prop) {
1044                 persist = (IODTPersistent *) prop->getBytesNoCopy();
1045                 compare = persist->compareFunc;
1046             } else if (addressCells == childAddressCells) {
1047                 compare = DefaultCompare;
1048             } else {
1049                 panic("There is no mixed comparison function yet...");
1050             }
1051
1052             for( ok = false;
1053                     range < endRanges;
1054                     range += (childCells + addressCells) ) {
1055
1056                 // is cell start within range?
1057                 diff = (*compare)( childAddressCells, cell, range );
1058
1059                 if (childAddressCells > sizeof(endCell)/sizeof(endCell[0]))
1060                     panic("IODTResolveAddressCell: Invalid device tree (%u)", (uint32_t)childAddressCells);
1061
1062                 bcopy(range, endCell, childAddressCells * sizeof(UInt32));
1063
1064                 rangeLen = CellsValue(childSizeCells, range + childAddressCells + addressCells);
1065                 AddLengthToCells(childAddressCells, endCell, rangeLen);
1066
1067                 diff2 = (*compare)( childAddressCells, cell, endCell );
1068
1069                 // if start of cell < start of range, or end of range >= start of cell, skip
1070                 if ((diff < 0) || (diff2 >= 0))
1071                     continue;
1072
1073                 len = CellsValue(childSizeCells, cell + childAddressCells);
1074                 ok = (0 == len);
1075
1076                 if (!ok)
1077                 {
1078                     // search for cell end
1079                     bcopy(cell, endCell, childAddressCells * sizeof(UInt32));
1080
1081                     AddLengthToCells(childAddressCells, endCell, len - 1);
1082
1083                     for( lookRange = startRange;
1084                             lookRange < endRanges;
1085                             lookRange += (childCells + addressCells) )
1086                     {
1087                         // make sure end of cell >= range start
1088                         endDiff = (*compare)( childAddressCells, endCell, lookRange );
1089                         if( endDiff < 0)
1090                             continue;
1091
1092                         UInt64 rangeStart = CellsValue(addressCells, range + childAddressCells);
1093                         UInt64 lookRangeStart = CellsValue(addressCells, lookRange + childAddressCells);
1094                         if ((endDiff - len + 1 + lookRangeStart) == (diff + rangeStart))
1095                         {
1096                             ok = true;
1097                             break;
1098                         }
1099                     }
1100                     if (!ok)
1101                         continue;
1102                 }
1103                 offset += diff;
1104                 break;
1105             }
1106
1107             if (addressCells + sizeCells > sizeof(cell)/sizeof(cell[0]))
1108                 panic("IODTResolveAddressCell: Invalid device tree (%u, %u)", (uint32_t)addressCells, (uint32_t)sizeCells);
1109
1110             // Get the physical start of the range from our parent
1111             bcopy( range + childAddressCells, cell, sizeof(UInt32) * addressCells );
1112             bzero( cell + addressCells, sizeof(UInt32) * sizeCells );
1113
1114         } /* else zero length range => pass thru to parent */
1115
1116         regEntry                = parent;
1117         childSizeCells          = sizeCells;
1118         childAddressCells       = addressCells;
1119         childCells              = childAddressCells + childSizeCells;
1120     }
1121     while( ok && regEntry);
1122
1123     return( ok);
1124 }
1125
1126
1127 OSArray * IODTResolveAddressing( IORegistryEntry * regEntry,
1128                         const char * addressPropertyName,
1129                         IODeviceMemory * parent )
1130 {
1131     IORegistryEntry             *parentEntry;
1132     OSData                              *addressProperty;
1133     UInt32                              sizeCells, addressCells, cells;
1134     int                                 i, num;
1135     UInt32                              *reg;
1136     IOPhysicalAddress   phys;
1137     IOPhysicalLength    len;
1138     OSArray                             *array;
1139     IODeviceMemory              *range;
1140
1141     parentEntry = regEntry->getParentEntry( gIODTPlane );
1142     addressProperty = (OSData *) regEntry->getProperty( addressPropertyName );
1143     if( (0 == addressProperty) || (0 == parentEntry))
1144         return( 0);
1145
1146     IODTGetCellCounts( parentEntry, &sizeCells, &addressCells );
1147     if( 0 == sizeCells)
1148         return( 0);
1149
1150     cells = sizeCells + addressCells;
1151     reg = (UInt32 *) addressProperty->getBytesNoCopy();
1152     num = addressProperty->getLength() / (4 * cells);
1153
1154     array = OSArray::withCapacity( 1 );
1155     if( 0 == array)
1156         return( 0);
1157
1158     for( i = 0; i < num; i++) {
1159         if( IODTResolveAddressCell( parentEntry, reg, &phys, &len )) {
1160             range = 0;
1161             if( parent)
1162                 range = IODeviceMemory::withSubRange( parent,
1163                         phys - parent->getPhysicalSegment(0, 0, kIOMemoryMapperNone), len );
1164             if( 0 == range)
1165                 range = IODeviceMemory::withRange( phys, len );
1166             if( range)
1167                 array->setObject( range );
1168         }
1169         reg += cells;
1170     }
1171
1172     regEntry->setProperty( gIODeviceMemoryKey, array);
1173     array->release();   /* ??? */
1174
1175     return( array);
1176 }
1177
1178 static void IODTGetNVLocation(
1179         IORegistryEntry * parent,
1180         IORegistryEntry * regEntry,
1181         UInt8 * busNum, UInt8 * deviceNum, UInt8 * functionNum )
1182 {
1183
1184     OSData                      *prop;
1185     IODTPersistent      *persist;
1186     UInt32                      *cell;
1187
1188     prop = (OSData *) parent->getProperty( gIODTPersistKey );
1189     if( prop) {
1190         persist = (IODTPersistent *) prop->getBytesNoCopy();
1191         (*persist->locationFunc)( regEntry, busNum, deviceNum, functionNum );
1192     } else {
1193         prop = (OSData *) regEntry->getProperty( "reg" );
1194         *functionNum    = 0;
1195         if( prop) {
1196             cell = (UInt32 *) prop->getBytesNoCopy();
1197             *busNum     = 3;
1198             *deviceNum  = 0x1f & (cell[ 0 ] >> 24);
1199         } else {
1200             *busNum     = 0;
1201             *deviceNum  = 0;
1202         }
1203     }
1204     return;
1205 }
1206
1207 /*
1208  * Try to make the same messed up descriptor as Mac OS
1209  */
1210
1211 IOReturn IODTMakeNVDescriptor( IORegistryEntry * regEntry,
1212                                 IONVRAMDescriptor * hdr )
1213 {
1214     IORegistryEntry             *parent;
1215     UInt32                              level;
1216     UInt32                              bridgeDevices;
1217     UInt8                               busNum;
1218     UInt8                               deviceNum;
1219     UInt8                               functionNum;
1220
1221     hdr->format         = 1;
1222     hdr->marker         = 0;
1223
1224     for(level = 0, bridgeDevices = 0;
1225         (parent = regEntry->getParentEntry( gIODTPlane )) && (level < 7); level++ ) {
1226
1227         IODTGetNVLocation( parent, regEntry,
1228                         &busNum, &deviceNum, &functionNum );
1229         if( level)
1230             bridgeDevices |= ((deviceNum & 0x1f) << ((level - 1) * 5));
1231         else {
1232             hdr->busNum         = busNum;
1233             hdr->deviceNum      = deviceNum;
1234             hdr->functionNum    = functionNum;
1235         }
1236         regEntry = parent;
1237     }
1238     hdr->bridgeCount    = level - 2;
1239     hdr->bridgeDevices  = bridgeDevices;
1240
1241     return( kIOReturnSuccess );
1242 }
1243
1244 OSData * IODTFindSlotName( IORegistryEntry * regEntry, UInt32 deviceNumber )
1245 {
1246     IORegistryEntry             *parent;
1247     OSData                              *data;
1248     OSData                              *ret = 0;
1249     UInt32                              *bits;
1250     UInt32                              i;
1251     size_t              nlen;
1252     char                                *names;
1253     char                                *lastName;
1254     UInt32                              mask;
1255
1256     data = (OSData *) regEntry->getProperty("AAPL,slot-name");
1257     if( data)
1258         return( data);
1259     parent = regEntry->getParentEntry( gIODTPlane );
1260     if( !parent)
1261         return( 0 );
1262     data = OSDynamicCast( OSData, parent->getProperty("slot-names"));
1263     if( !data)
1264         return( 0 );
1265     if( data->getLength() <= 4)
1266         return( 0 );
1267
1268     bits = (UInt32 *) data->getBytesNoCopy();
1269     mask = *bits;
1270     if( (0 == (mask & (1 << deviceNumber))))
1271         return( 0 );
1272
1273     names = (char *)(bits + 1);
1274     lastName = names + (data->getLength() - 4);
1275
1276     for( i = 0; (i <= deviceNumber) && (names < lastName); i++ ) {
1277
1278         if( mask & (1 << i)) {
1279             nlen = 1 + strnlen(names, lastName - names);
1280             if( i == deviceNumber) {
1281                 data = OSData::withBytesNoCopy(names, nlen);
1282                 if( data) {
1283                     regEntry->setProperty("AAPL,slot-name", data);
1284                     ret = data;
1285                     data->release();
1286                 }
1287             } else
1288                 names += nlen;
1289         }
1290     }
1291
1292     return( ret );
1293 }
1294
1295 extern "C" IOReturn IONDRVLibrariesInitialize( IOService * provider )
1296 {
1297     return( kIOReturnUnsupported );
1298 }