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 * HISTORY
30 *
31 * 17-Apr-91   Portions from libIO.m, Doug Mitchell at NeXT.
32 * 17-Nov-98   cpp
33 *
34 */
35
36#include <IOKit/system.h>
37#include <mach/sync_policy.h>
38#include <machine/machine_routines.h>
39#include <vm/vm_kern.h>
40#include <libkern/c++/OSCPPDebug.h>
41
42#include <IOKit/assert.h>
43
44#include <IOKit/IOReturn.h>
45#include <IOKit/IOLib.h>
46#include <IOKit/IOLocks.h>
47#include <IOKit/IOMapper.h>
48#include <IOKit/IOBufferMemoryDescriptor.h>
49#include <IOKit/IOKitDebug.h>
50
51#include "IOKitKernelInternal.h"
52
53#ifdef IOALLOCDEBUG
54#include <libkern/OSDebug.h>
55#include <sys/sysctl.h>
56#endif
57
58#include "libkern/OSAtomic.h"
59#include <libkern/c++/OSKext.h>
60#include <IOKit/IOStatisticsPrivate.h>
61#include <sys/msgbuf.h>
62
63#if IOKITSTATS
64
65#define IOStatisticsAlloc(type, size) \
66do { \
67	IOStatistics::countAlloc(type, size); \
68} while (0)
69
70#else
71
72#define IOStatisticsAlloc(type, size)
73
74#endif /* IOKITSTATS */
75
76extern "C"
77{
78
79
80mach_timespec_t IOZeroTvalspec = { 0, 0 };
81
82extern ppnum_t pmap_find_phys(pmap_t pmap, addr64_t va);
83
84extern int
85__doprnt(
86	const char		*fmt,
87	va_list			argp,
88	void			(*putc)(int, void *),
89	void                    *arg,
90	int			radix);
91
92extern void cons_putc_locked(char);
93extern void bsd_log_lock(void);
94extern void bsd_log_unlock(void);
95extern void logwakeup();
96
97
98/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
99
100lck_grp_t	*IOLockGroup;
101
102/*
103 * Global variables for use by iLogger
104 * These symbols are for use only by Apple diagnostic code.
105 * Binary compatibility is not guaranteed for kexts that reference these symbols.
106 */
107
108void *_giDebugLogInternal	= NULL;
109void *_giDebugLogDataInternal	= NULL;
110void *_giDebugReserved1		= NULL;
111void *_giDebugReserved2		= NULL;
112
113iopa_t gIOBMDPageAllocator;
114
115/*
116 * Static variables for this module.
117 */
118
119static queue_head_t gIOMallocContiguousEntries;
120static lck_mtx_t *  gIOMallocContiguousEntriesLock;
121
122#if __x86_64__
123enum { kIOMaxPageableMaps    = 8 };
124enum { kIOPageableMapSize    = 512 * 1024 * 1024 };
125enum { kIOPageableMaxMapSize = 512 * 1024 * 1024 };
126#else
127enum { kIOMaxPageableMaps    = 16 };
128enum { kIOPageableMapSize    = 96 * 1024 * 1024 };
129enum { kIOPageableMaxMapSize = 96 * 1024 * 1024 };
130#endif
131
132typedef struct {
133    vm_map_t		map;
134    vm_offset_t	address;
135    vm_offset_t	end;
136} IOMapData;
137
138static struct {
139    UInt32	count;
140    UInt32	hint;
141    IOMapData	maps[ kIOMaxPageableMaps ];
142    lck_mtx_t *	lock;
143} gIOKitPageableSpace;
144
145static iopa_t gIOPageablePageAllocator;
146
147uint32_t  gIOPageAllocChunkBytes;
148
149/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
150
151void IOLibInit(void)
152{
153    kern_return_t ret;
154
155    static bool libInitialized;
156
157    if(libInitialized)
158        return;
159
160    gIOKitPageableSpace.maps[0].address = 0;
161    ret = kmem_suballoc(kernel_map,
162                    &gIOKitPageableSpace.maps[0].address,
163                    kIOPageableMapSize,
164                    TRUE,
165                    VM_FLAGS_ANYWHERE,
166                    &gIOKitPageableSpace.maps[0].map);
167    if (ret != KERN_SUCCESS)
168        panic("failed to allocate iokit pageable map\n");
169
170    IOLockGroup = lck_grp_alloc_init("IOKit", LCK_GRP_ATTR_NULL);
171
172    gIOKitPageableSpace.lock 		= lck_mtx_alloc_init(IOLockGroup, LCK_ATTR_NULL);
173    gIOKitPageableSpace.maps[0].end	= gIOKitPageableSpace.maps[0].address + kIOPageableMapSize;
174    gIOKitPageableSpace.hint		= 0;
175    gIOKitPageableSpace.count		= 1;
176
177    gIOMallocContiguousEntriesLock 	= lck_mtx_alloc_init(IOLockGroup, LCK_ATTR_NULL);
178    queue_init( &gIOMallocContiguousEntries );
179
180    gIOPageAllocChunkBytes = PAGE_SIZE/64;
181    assert(sizeof(iopa_page_t) <= gIOPageAllocChunkBytes);
182    iopa_init(&gIOBMDPageAllocator);
183    iopa_init(&gIOPageablePageAllocator);
184
185    libInitialized = true;
186}
187
188/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
189
190IOThread IOCreateThread(IOThreadFunc fcn, void *arg)
191{
192	kern_return_t	result;
193	thread_t		thread;
194
195	result = kernel_thread_start((thread_continue_t)fcn, arg, &thread);
196	if (result != KERN_SUCCESS)
197		return (NULL);
198
199	thread_deallocate(thread);
200
201	return (thread);
202}
203
204
205void IOExitThread(void)
206{
207    (void) thread_terminate(current_thread());
208}
209
210/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
211
212
213void * IOMalloc(vm_size_t size)
214{
215    void * address;
216
217    address = (void *)kalloc(size);
218    if ( address ) {
219#if IOALLOCDEBUG
220		debug_iomalloc_size += size;
221#endif
222		IOStatisticsAlloc(kIOStatisticsMalloc, size);
223    }
224
225    return address;
226}
227
228void IOFree(void * address, vm_size_t size)
229{
230    if (address) {
231		kfree(address, size);
232#if IOALLOCDEBUG
233		debug_iomalloc_size -= size;
234#endif
235		IOStatisticsAlloc(kIOStatisticsFree, size);
236    }
237}
238
239/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
240
241void * IOMallocAligned(vm_size_t size, vm_size_t alignment)
242{
243    kern_return_t	kr;
244    vm_offset_t		address;
245    vm_offset_t		allocationAddress;
246    vm_size_t		adjustedSize;
247    uintptr_t		alignMask;
248
249    if (size == 0)
250        return 0;
251    if (alignment == 0)
252        alignment = 1;
253
254    alignMask = alignment - 1;
255    adjustedSize = size + sizeof(vm_size_t) + sizeof(vm_address_t);
256
257    if (size > adjustedSize) {
258	    address = 0;    /* overflow detected */
259    }
260    else if (adjustedSize >= page_size) {
261
262        kr = kernel_memory_allocate(kernel_map, &address,
263					size, alignMask, 0);
264	if (KERN_SUCCESS != kr)
265	    address = 0;
266
267    } else {
268
269	adjustedSize += alignMask;
270
271	if (adjustedSize >= page_size) {
272
273	    kr = kernel_memory_allocate(kernel_map, &allocationAddress,
274					    adjustedSize, 0, 0);
275	    if (KERN_SUCCESS != kr)
276		allocationAddress = 0;
277
278	} else
279	    allocationAddress = (vm_address_t) kalloc(adjustedSize);
280
281        if (allocationAddress) {
282            address = (allocationAddress + alignMask
283                    + (sizeof(vm_size_t) + sizeof(vm_address_t)))
284                    & (~alignMask);
285
286            *((vm_size_t *)(address - sizeof(vm_size_t) - sizeof(vm_address_t)))
287			    = adjustedSize;
288            *((vm_address_t *)(address - sizeof(vm_address_t)))
289                            = allocationAddress;
290	} else
291	    address = 0;
292    }
293
294    assert(0 == (address & alignMask));
295
296    if( address) {
297#if IOALLOCDEBUG
298		debug_iomalloc_size += size;
299#endif
300    	IOStatisticsAlloc(kIOStatisticsMallocAligned, size);
301	}
302
303    return (void *) address;
304}
305
306void IOFreeAligned(void * address, vm_size_t size)
307{
308    vm_address_t	allocationAddress;
309    vm_size_t	adjustedSize;
310
311    if( !address)
312	return;
313
314    assert(size);
315
316    adjustedSize = size + sizeof(vm_size_t) + sizeof(vm_address_t);
317    if (adjustedSize >= page_size) {
318
319        kmem_free( kernel_map, (vm_offset_t) address, size);
320
321    } else {
322      	adjustedSize = *((vm_size_t *)( (vm_address_t) address
323                                - sizeof(vm_address_t) - sizeof(vm_size_t)));
324        allocationAddress = *((vm_address_t *)( (vm_address_t) address
325				- sizeof(vm_address_t) ));
326
327	if (adjustedSize >= page_size)
328	    kmem_free( kernel_map, allocationAddress, adjustedSize);
329	else
330	  kfree((void *)allocationAddress, adjustedSize);
331    }
332
333#if IOALLOCDEBUG
334    debug_iomalloc_size -= size;
335#endif
336
337    IOStatisticsAlloc(kIOStatisticsFreeAligned, size);
338}
339
340/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
341
342void
343IOKernelFreePhysical(mach_vm_address_t address, mach_vm_size_t size)
344{
345    mach_vm_address_t allocationAddress;
346    mach_vm_size_t    adjustedSize;
347
348    if (!address)
349	return;
350
351    assert(size);
352
353    adjustedSize = (2 * size) + sizeof(mach_vm_size_t) + sizeof(mach_vm_address_t);
354    if (adjustedSize >= page_size) {
355
356	kmem_free( kernel_map, (vm_offset_t) address, size);
357
358    } else {
359
360	adjustedSize = *((mach_vm_size_t *)
361			(address - sizeof(mach_vm_address_t) - sizeof(mach_vm_size_t)));
362	allocationAddress = *((mach_vm_address_t *)
363			(address - sizeof(mach_vm_address_t) ));
364	kfree((void *)allocationAddress, adjustedSize);
365    }
366
367    IOStatisticsAlloc(kIOStatisticsFreeContiguous, size);
368#if IOALLOCDEBUG
369    debug_iomalloc_size -= size;
370#endif
371}
372
373
374mach_vm_address_t
375IOKernelAllocateWithPhysicalRestrict(mach_vm_size_t size, mach_vm_address_t maxPhys,
376			                mach_vm_size_t alignment, bool contiguous)
377{
378    kern_return_t	kr;
379    mach_vm_address_t	address;
380    mach_vm_address_t	allocationAddress;
381    mach_vm_size_t	adjustedSize;
382    mach_vm_address_t	alignMask;
383
384    if (size == 0)
385	return (0);
386    if (alignment == 0)
387        alignment = 1;
388
389    alignMask = alignment - 1;
390    adjustedSize = (2 * size) + sizeof(mach_vm_size_t) + sizeof(mach_vm_address_t);
391
392    contiguous = (contiguous && (adjustedSize > page_size))
393                   || (alignment > page_size);
394
395    if (contiguous || maxPhys)
396    {
397        int options = 0;
398	vm_offset_t virt;
399
400	adjustedSize = size;
401        contiguous = (contiguous && (adjustedSize > page_size))
402                           || (alignment > page_size);
403
404	if (!contiguous)
405	{
406	    if (maxPhys <= 0xFFFFFFFF)
407	    {
408		maxPhys = 0;
409		options |= KMA_LOMEM;
410	    }
411	    else if (gIOLastPage && (atop_64(maxPhys) > gIOLastPage))
412	    {
413		maxPhys = 0;
414	    }
415	}
416	if (contiguous || maxPhys)
417	{
418	    kr = kmem_alloc_contig(kernel_map, &virt, size,
419				   alignMask, atop(maxPhys), atop(alignMask), 0);
420	}
421	else
422	{
423	    kr = kernel_memory_allocate(kernel_map, &virt,
424					size, alignMask, options);
425	}
426	if (KERN_SUCCESS == kr)
427	    address = virt;
428	else
429	    address = 0;
430    }
431    else
432    {
433	adjustedSize += alignMask;
434        allocationAddress = (mach_vm_address_t) kalloc(adjustedSize);
435
436        if (allocationAddress) {
437
438            address = (allocationAddress + alignMask
439                    + (sizeof(mach_vm_size_t) + sizeof(mach_vm_address_t)))
440                    & (~alignMask);
441
442            if (atop_32(address) != atop_32(address + size - 1))
443                address = round_page(address);
444
445            *((mach_vm_size_t *)(address - sizeof(mach_vm_size_t)
446                            - sizeof(mach_vm_address_t))) = adjustedSize;
447            *((mach_vm_address_t *)(address - sizeof(mach_vm_address_t)))
448                            = allocationAddress;
449	} else
450	    address = 0;
451    }
452
453    if (address) {
454    IOStatisticsAlloc(kIOStatisticsMallocContiguous, size);
455#if IOALLOCDEBUG
456	debug_iomalloc_size += size;
457#endif
458    }
459
460    return (address);
461}
462
463
464/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
465
466struct _IOMallocContiguousEntry
467{
468    mach_vm_address_t	       virtualAddr;
469    IOBufferMemoryDescriptor * md;
470    queue_chain_t	       link;
471};
472typedef struct _IOMallocContiguousEntry _IOMallocContiguousEntry;
473
474void * IOMallocContiguous(vm_size_t size, vm_size_t alignment,
475			   IOPhysicalAddress * physicalAddress)
476{
477    mach_vm_address_t	address = 0;
478
479    if (size == 0)
480	return 0;
481    if (alignment == 0)
482	alignment = 1;
483
484    /* Do we want a physical address? */
485    if (!physicalAddress)
486    {
487	address = IOKernelAllocateWithPhysicalRestrict(size, 0 /*maxPhys*/, alignment, true);
488    }
489    else do
490    {
491	IOBufferMemoryDescriptor * bmd;
492	mach_vm_address_t          physicalMask;
493	vm_offset_t		   alignMask;
494
495	alignMask = alignment - 1;
496	physicalMask = (0xFFFFFFFF ^ alignMask);
497
498	bmd = IOBufferMemoryDescriptor::inTaskWithPhysicalMask(
499		kernel_task, kIOMemoryPhysicallyContiguous, size, physicalMask);
500	if (!bmd)
501	    break;
502
503	_IOMallocContiguousEntry *
504	entry = IONew(_IOMallocContiguousEntry, 1);
505	if (!entry)
506	{
507	    bmd->release();
508	    break;
509	}
510	entry->virtualAddr = (mach_vm_address_t) bmd->getBytesNoCopy();
511	entry->md          = bmd;
512	lck_mtx_lock(gIOMallocContiguousEntriesLock);
513	queue_enter( &gIOMallocContiguousEntries, entry,
514		    _IOMallocContiguousEntry *, link );
515	lck_mtx_unlock(gIOMallocContiguousEntriesLock);
516
517	address          = (mach_vm_address_t) entry->virtualAddr;
518	*physicalAddress = bmd->getPhysicalAddress();
519    }
520    while (false);
521
522    return (void *) address;
523}
524
525void IOFreeContiguous(void * _address, vm_size_t size)
526{
527    _IOMallocContiguousEntry * entry;
528    IOMemoryDescriptor *       md = NULL;
529
530    mach_vm_address_t address = (mach_vm_address_t) _address;
531
532    if( !address)
533	return;
534
535    assert(size);
536
537    lck_mtx_lock(gIOMallocContiguousEntriesLock);
538    queue_iterate( &gIOMallocContiguousEntries, entry,
539		    _IOMallocContiguousEntry *, link )
540    {
541	if( entry->virtualAddr == address ) {
542	    md   = entry->md;
543	    queue_remove( &gIOMallocContiguousEntries, entry,
544			    _IOMallocContiguousEntry *, link );
545	    break;
546	}
547    }
548    lck_mtx_unlock(gIOMallocContiguousEntriesLock);
549
550    if (md)
551    {
552	md->release();
553	IODelete(entry, _IOMallocContiguousEntry, 1);
554    }
555    else
556    {
557	IOKernelFreePhysical((mach_vm_address_t) address, size);
558    }
559}
560
561/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
562
563kern_return_t IOIteratePageableMaps(vm_size_t size,
564                    IOIteratePageableMapsCallback callback, void * ref)
565{
566    kern_return_t	kr = kIOReturnNotReady;
567    vm_size_t		segSize;
568    UInt32		attempts;
569    UInt32		index;
570    vm_offset_t		min;
571    vm_map_t		map;
572
573    if (size > kIOPageableMaxMapSize)
574        return( kIOReturnBadArgument );
575
576    do {
577        index = gIOKitPageableSpace.hint;
578        attempts = gIOKitPageableSpace.count;
579        while( attempts--) {
580            kr = (*callback)(gIOKitPageableSpace.maps[index].map, ref);
581            if( KERN_SUCCESS == kr) {
582                gIOKitPageableSpace.hint = index;
583                break;
584            }
585            if( index)
586                index--;
587            else
588                index = gIOKitPageableSpace.count - 1;
589        }
590        if( KERN_SUCCESS == kr)
591            break;
592
593        lck_mtx_lock( gIOKitPageableSpace.lock );
594
595        index = gIOKitPageableSpace.count;
596        if( index >= (kIOMaxPageableMaps - 1)) {
597            lck_mtx_unlock( gIOKitPageableSpace.lock );
598            break;
599        }
600
601        if( size < kIOPageableMapSize)
602            segSize = kIOPageableMapSize;
603        else
604            segSize = size;
605
606        min = 0;
607        kr = kmem_suballoc(kernel_map,
608                    &min,
609                    segSize,
610                    TRUE,
611                    VM_FLAGS_ANYWHERE,
612                    &map);
613        if( KERN_SUCCESS != kr) {
614            lck_mtx_unlock( gIOKitPageableSpace.lock );
615            break;
616        }
617
618        gIOKitPageableSpace.maps[index].map 	= map;
619        gIOKitPageableSpace.maps[index].address = min;
620        gIOKitPageableSpace.maps[index].end 	= min + segSize;
621        gIOKitPageableSpace.hint 		= index;
622        gIOKitPageableSpace.count 		= index + 1;
623
624        lck_mtx_unlock( gIOKitPageableSpace.lock );
625
626    } while( true );
627
628    return kr;
629}
630
631struct IOMallocPageableRef
632{
633    vm_offset_t address;
634    vm_size_t	 size;
635};
636
637static kern_return_t IOMallocPageableCallback(vm_map_t map, void * _ref)
638{
639    struct IOMallocPageableRef * ref = (struct IOMallocPageableRef *) _ref;
640    kern_return_t	         kr;
641
642    kr = kmem_alloc_pageable( map, &ref->address, ref->size );
643
644    return( kr );
645}
646
647static void * IOMallocPageablePages(vm_size_t size, vm_size_t alignment)
648{
649    kern_return_t	       kr = kIOReturnNotReady;
650    struct IOMallocPageableRef ref;
651
652    if (alignment > page_size)
653        return( 0 );
654    if (size > kIOPageableMaxMapSize)
655        return( 0 );
656
657    ref.size = size;
658    kr = IOIteratePageableMaps( size, &IOMallocPageableCallback, &ref );
659    if( kIOReturnSuccess != kr)
660        ref.address = 0;
661
662    return( (void *) ref.address );
663}
664
665vm_map_t IOPageableMapForAddress( uintptr_t address )
666{
667    vm_map_t	map = 0;
668    UInt32	index;
669
670    for( index = 0; index < gIOKitPageableSpace.count; index++) {
671        if( (address >= gIOKitPageableSpace.maps[index].address)
672         && (address < gIOKitPageableSpace.maps[index].end) ) {
673            map = gIOKitPageableSpace.maps[index].map;
674            break;
675        }
676    }
677    if( !map)
678        panic("IOPageableMapForAddress: null");
679
680    return( map );
681}
682
683static void IOFreePageablePages(void * address, vm_size_t size)
684{
685    vm_map_t map;
686
687    map = IOPageableMapForAddress( (vm_address_t) address);
688    if( map)
689        kmem_free( map, (vm_offset_t) address, size);
690}
691
692static uintptr_t IOMallocOnePageablePage(iopa_t * a)
693{
694    return ((uintptr_t) IOMallocPageablePages(page_size, page_size));
695}
696
697void * IOMallocPageable(vm_size_t size, vm_size_t alignment)
698{
699    void * addr;
700
701    if (size >= (page_size - 4*gIOPageAllocChunkBytes)) addr = IOMallocPageablePages(size, alignment);
702    else                   addr = ((void * ) iopa_alloc(&gIOPageablePageAllocator, &IOMallocOnePageablePage, size, alignment));
703
704    if (addr) {
705#if IOALLOCDEBUG
706       debug_iomallocpageable_size += size;
707#endif
708       IOStatisticsAlloc(kIOStatisticsMallocPageable, size);
709    }
710
711    return (addr);
712}
713
714void IOFreePageable(void * address, vm_size_t size)
715{
716#if IOALLOCDEBUG
717    debug_iomallocpageable_size -= size;
718#endif
719    IOStatisticsAlloc(kIOStatisticsFreePageable, size);
720
721    if (size < (page_size - 4*gIOPageAllocChunkBytes))
722    {
723	address = (void *) iopa_free(&gIOPageablePageAllocator, (uintptr_t) address, size);
724	size = page_size;
725    }
726    if (address) IOFreePageablePages(address, size);
727}
728
729/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
730
731extern "C" void
732iopa_init(iopa_t * a)
733{
734    bzero(a, sizeof(*a));
735    a->lock = IOLockAlloc();
736    queue_init(&a->list);
737}
738
739static uintptr_t
740iopa_allocinpage(iopa_page_t * pa, uint32_t count, uint64_t align)
741{
742    uint32_t n, s;
743    uint64_t avail = pa->avail;
744
745    assert(avail);
746
747    // find strings of count 1 bits in avail
748    for (n = count; n > 1; n -= s)
749    {
750    	s = n >> 1;
751    	avail = avail & (avail << s);
752    }
753    // and aligned
754    avail &= align;
755
756    if (avail)
757    {
758	n = __builtin_clzll(avail);
759	pa->avail &= ~((-1ULL << (64 - count)) >> n);
760	if (!pa->avail && pa->link.next)
761	{
762	    remque(&pa->link);
763	    pa->link.next = 0;
764	}
765	return (n * gIOPageAllocChunkBytes + trunc_page((uintptr_t) pa));
766    }
767
768    return (0);
769}
770
771static uint32_t
772log2up(uint32_t size)
773{
774    if (size <= 1) size = 0;
775    else size = 32 - __builtin_clz(size - 1);
776    return (size);
777}
778
779uintptr_t
780iopa_alloc(iopa_t * a, iopa_proc_t alloc, vm_size_t bytes, uint32_t balign)
781{
782    static const uint64_t align_masks[] = {
783	0xFFFFFFFFFFFFFFFF,
784	0xAAAAAAAAAAAAAAAA,
785	0x8888888888888888,
786	0x8080808080808080,
787	0x8000800080008000,
788	0x8000000080000000,
789	0x8000000000000000,
790    };
791    iopa_page_t * pa;
792    uintptr_t     addr = 0;
793    uint32_t      count;
794    uint64_t      align;
795
796    if (!bytes) bytes = 1;
797    count = (bytes + gIOPageAllocChunkBytes - 1) / gIOPageAllocChunkBytes;
798    align = align_masks[log2up((balign + gIOPageAllocChunkBytes - 1) / gIOPageAllocChunkBytes)];
799
800    IOLockLock(a->lock);
801    pa = (typeof(pa)) queue_first(&a->list);
802    while (!queue_end(&a->list, &pa->link))
803    {
804	addr = iopa_allocinpage(pa, count, align);
805	if (addr)
806	{
807	    a->bytecount += bytes;
808	    break;
809	}
810	pa = (typeof(pa)) queue_next(&pa->link);
811    }
812    IOLockUnlock(a->lock);
813
814    if (!addr)
815    {
816	addr = alloc(a);
817	if (addr)
818	{
819	    pa = (typeof(pa)) (addr + page_size - gIOPageAllocChunkBytes);
820	    pa->signature = kIOPageAllocSignature;
821	    pa->avail     = -2ULL;
822
823	    addr = iopa_allocinpage(pa, count, align);
824	    IOLockLock(a->lock);
825	    if (pa->avail) enqueue_head(&a->list, &pa->link);
826	    a->pagecount++;
827	    if (addr) a->bytecount += bytes;
828	    IOLockUnlock(a->lock);
829	}
830    }
831
832    assert((addr & ((1 << log2up(balign)) - 1)) == 0);
833    return (addr);
834}
835
836uintptr_t
837iopa_free(iopa_t * a, uintptr_t addr, vm_size_t bytes)
838{
839    iopa_page_t * pa;
840    uint32_t      count;
841    uintptr_t     chunk;
842
843    if (!bytes) bytes = 1;
844
845    chunk = (addr & page_mask);
846    assert(0 == (chunk & (gIOPageAllocChunkBytes - 1)));
847
848    pa = (typeof(pa)) (addr | (page_size - gIOPageAllocChunkBytes));
849    assert(kIOPageAllocSignature == pa->signature);
850
851    count = (bytes + gIOPageAllocChunkBytes - 1) / gIOPageAllocChunkBytes;
852    chunk /= gIOPageAllocChunkBytes;
853
854    IOLockLock(a->lock);
855    if (!pa->avail)
856    {
857	assert(!pa->link.next);
858	enqueue_tail(&a->list, &pa->link);
859    }
860    pa->avail |= ((-1ULL << (64 - count)) >> chunk);
861    if (pa->avail != -2ULL) pa = 0;
862    else
863    {
864        remque(&pa->link);
865        pa->link.next = 0;
866        pa->signature = 0;
867	a->pagecount--;
868	// page to free
869	pa = (typeof(pa)) trunc_page(pa);
870    }
871    a->bytecount -= bytes;
872    IOLockUnlock(a->lock);
873
874    return ((uintptr_t) pa);
875}
876
877/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
878
879IOReturn IOSetProcessorCacheMode( task_t task, IOVirtualAddress address,
880				  IOByteCount length, IOOptionBits cacheMode )
881{
882    IOReturn	ret = kIOReturnSuccess;
883    ppnum_t	pagenum;
884
885    if( task != kernel_task)
886	return( kIOReturnUnsupported );
887    if ((address | length) & PAGE_MASK)
888    {
889//	OSReportWithBacktrace("IOSetProcessorCacheMode(0x%x, 0x%x, 0x%x) fails\n", address, length, cacheMode);
890	return( kIOReturnUnsupported );
891    }
892    length = round_page(address + length) - trunc_page( address );
893    address = trunc_page( address );
894
895    // make map mode
896    cacheMode = (cacheMode << kIOMapCacheShift) & kIOMapCacheMask;
897
898    while( (kIOReturnSuccess == ret) && (length > 0) ) {
899
900	// Get the physical page number
901	pagenum = pmap_find_phys(kernel_pmap, (addr64_t)address);
902	if( pagenum) {
903            ret = IOUnmapPages( get_task_map(task), address, page_size );
904	    ret = IOMapPages( get_task_map(task), address, ptoa_64(pagenum), page_size, cacheMode );
905	} else
906	    ret = kIOReturnVMError;
907
908	address += page_size;
909	length -= page_size;
910    }
911
912    return( ret );
913}
914
915
916IOReturn IOFlushProcessorCache( task_t task, IOVirtualAddress address,
917				  IOByteCount length )
918{
919    if( task != kernel_task)
920	return( kIOReturnUnsupported );
921
922    flush_dcache64( (addr64_t) address, (unsigned) length, false );
923
924    return( kIOReturnSuccess );
925}
926
927/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
928
929vm_offset_t OSKernelStackRemaining( void )
930{
931    return (ml_stack_remaining());
932}
933
934/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
935
936/*
937 * Spin for indicated number of milliseconds.
938 */
939void IOSleep(unsigned milliseconds)
940{
941    delay_for_interval(milliseconds, kMillisecondScale);
942}
943
944/*
945 * Spin for indicated number of microseconds.
946 */
947void IODelay(unsigned microseconds)
948{
949    delay_for_interval(microseconds, kMicrosecondScale);
950}
951
952/*
953 * Spin for indicated number of nanoseconds.
954 */
955void IOPause(unsigned nanoseconds)
956{
957    delay_for_interval(nanoseconds, kNanosecondScale);
958}
959
960/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
961
962static void _iolog_consputc(int ch, void *arg __unused)
963{
964    cons_putc_locked(ch);
965}
966
967static void _iolog_logputc(int ch, void *arg __unused)
968{
969    log_putc_locked(ch);
970}
971
972void IOLog(const char *format, ...)
973{
974    va_list ap;
975
976    va_start(ap, format);
977    IOLogv(format, ap);
978    va_end(ap);
979}
980
981void IOLogv(const char *format, va_list ap)
982{
983    va_list ap2;
984
985    va_copy(ap2, ap);
986
987    bsd_log_lock();
988    __doprnt(format, ap, _iolog_logputc, NULL, 16);
989    bsd_log_unlock();
990    logwakeup();
991
992    __doprnt(format, ap2, _iolog_consputc, NULL, 16);
993}
994
995#if !__LP64__
996void IOPanic(const char *reason)
997{
998	panic("%s", reason);
999}
1000#endif
1001
1002/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
1003
1004/*
1005 * Convert a integer constant (typically a #define or enum) to a string.
1006 */
1007static char noValue[80];	// that's pretty
1008
1009const char *IOFindNameForValue(int value, const IONamedValue *regValueArray)
1010{
1011	for( ; regValueArray->name; regValueArray++) {
1012		if(regValueArray->value == value)
1013			return(regValueArray->name);
1014	}
1015	snprintf(noValue, sizeof(noValue), "0x%x (UNDEFINED)", value);
1016	return((const char *)noValue);
1017}
1018
1019IOReturn IOFindValueForName(const char *string,
1020	const IONamedValue *regValueArray,
1021	int *value)
1022{
1023	for( ; regValueArray->name; regValueArray++) {
1024		if(!strcmp(regValueArray->name, string)) {
1025			*value = regValueArray->value;
1026			return kIOReturnSuccess;
1027		}
1028	}
1029	return kIOReturnBadArgument;
1030}
1031
1032OSString * IOCopyLogNameForPID(int pid)
1033{
1034    char   buf[128];
1035    size_t len;
1036    snprintf(buf, sizeof(buf), "pid %d, ", pid);
1037    len = strlen(buf);
1038    proc_name(pid, buf + len, sizeof(buf) - len);
1039    return (OSString::withCString(buf));
1040}
1041
1042/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
1043
1044IOAlignment IOSizeToAlignment(unsigned int size)
1045{
1046    register int shift;
1047    const int intsize = sizeof(unsigned int) * 8;
1048
1049    for (shift = 1; shift < intsize; shift++) {
1050	if (size & 0x80000000)
1051	    return (IOAlignment)(intsize - shift);
1052	size <<= 1;
1053    }
1054    return 0;
1055}
1056
1057unsigned int IOAlignmentToSize(IOAlignment align)
1058{
1059    unsigned int size;
1060
1061    for (size = 1; align; align--) {
1062	size <<= 1;
1063    }
1064    return size;
1065}
1066
1067} /* extern "C" */
1068
1069
1070
1071