git.saurik.com Git - apple/xnu.git/blame_incremental - iokit/Kernel/IODeviceTreeSupport.cpp

... / ...

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