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