iokit/Kernel/IODeviceTreeSupport.cpp

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