xnu-3248.40.184.tar.gz

[apple/xnu.git] / osfmk / kern / sched_grrr.c

/*
 * Copyright (c) 2009 Apple Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 * 
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */

#include <mach/mach_types.h>
#include <mach/machine.h>
#include <mach/policy.h>
#include <mach/sync_policy.h>
#include <mach/thread_act.h>

#include <machine/machine_routines.h>
#include <machine/sched_param.h>
#include <machine/machine_cpu.h>

#include <kern/kern_types.h>
#include <kern/clock.h>
#include <kern/counters.h>
#include <kern/cpu_number.h>
#include <kern/cpu_data.h>
#include <kern/debug.h>
#include <kern/macro_help.h>
#include <kern/machine.h>
#include <kern/misc_protos.h>
#include <kern/processor.h>
#include <kern/queue.h>
#include <kern/sched.h>
#include <kern/sched_prim.h>
#include <kern/syscall_subr.h>
#include <kern/task.h>
#include <kern/thread.h>

#include <vm/pmap.h>
#include <vm/vm_kern.h>
#include <vm/vm_map.h>

#include <mach/sdt.h>

#include <sys/kdebug.h>

#if defined(CONFIG_SCHED_GRRR_CORE)

static void
grrr_priority_mapping_init(void);

static boolean_t
grrr_enqueue(
				   grrr_run_queue_t			rq,
				   thread_t			thread);
				   
static thread_t
grrr_select(
					grrr_run_queue_t	rq);

static void
grrr_remove(
				  grrr_run_queue_t			rq,
				  thread_t		thread);


static void
grrr_sorted_list_insert_group(grrr_run_queue_t rq,
									grrr_group_t group);

static void
grrr_rescale_work(grrr_run_queue_t rq);

static void
grrr_runqueue_init(grrr_run_queue_t		runq);

/* Map Mach priorities to ones suitable for proportional sharing */
static grrr_proportional_priority_t grrr_priority_mapping[NRQS];

/* Map each proportional priority to its group */
static grrr_group_index_t grrr_group_mapping[NUM_GRRR_PROPORTIONAL_PRIORITIES];

uint32_t			grrr_rescale_tick;

#endif /* defined(CONFIG_SCHED_GRRR_CORE) */

#if defined(CONFIG_SCHED_GRRR)

static void
sched_grrr_init(void);

static void
sched_grrr_timebase_init(void);

static void
sched_grrr_processor_init(processor_t processor);

static void
sched_grrr_pset_init(processor_set_t pset);

static void
sched_grrr_maintenance_continuation(void);

static thread_t
sched_grrr_choose_thread(processor_t		processor,
							int				priority,
							ast_t				reason);

static thread_t
sched_grrr_steal_thread(processor_set_t		pset);

static int
sched_grrr_compute_priority(thread_t thread);

static processor_t
sched_grrr_choose_processor(	processor_set_t		pset,
								processor_t			processor,
								thread_t			thread);

static boolean_t
sched_grrr_processor_enqueue(
							 processor_t			processor,
							 thread_t			thread,
							 integer_t			options);

static void
sched_grrr_processor_queue_shutdown(
									 processor_t			processor);

static boolean_t
sched_grrr_processor_queue_remove(
						    processor_t			processor,
							thread_t		thread);

static boolean_t
sched_grrr_processor_queue_empty(processor_t		processor);

static boolean_t
sched_grrr_processor_queue_has_priority(processor_t		processor,
										 int				priority,
										 boolean_t		gte);

static boolean_t
sched_grrr_priority_is_urgent(int priority);

static ast_t
sched_grrr_processor_csw_check(processor_t processor);

static uint32_t
sched_grrr_initial_quantum_size(thread_t thread);

static sched_mode_t
sched_grrr_initial_thread_sched_mode(task_t parent_task);

static boolean_t
sched_grrr_can_update_priority(thread_t	thread);

static void
sched_grrr_update_priority(thread_t	thread);

static void
sched_grrr_lightweight_update_priority(thread_t	thread);

static int
sched_grrr_processor_runq_count(processor_t	processor);

static uint64_t
sched_grrr_processor_runq_stats_count_sum(processor_t   processor);

static int
sched_grrr_processor_bound_count(processor_t	processor);

static void
sched_grrr_thread_update_scan(sched_update_scan_context_t scan_context);

const struct sched_dispatch_table sched_grrr_dispatch = {
	.sched_name                                     = "grrr",
	.init                                           = sched_grrr_init,
	.timebase_init                                  = sched_grrr_timebase_init,
	.processor_init                                 = sched_grrr_processor_init,
	.pset_init                                      = sched_grrr_pset_init,
	.maintenance_continuation                       = sched_grrr_maintenance_continuation,
	.choose_thread                                  = sched_grrr_choose_thread,
	.steal_thread_enabled                           = FALSE,
	.steal_thread                                   = sched_grrr_steal_thread,
	.compute_timeshare_priority                     = sched_grrr_compute_priority,
	.choose_processor                               = sched_grrr_choose_processor,
	.processor_enqueue                              = sched_grrr_processor_enqueue,
	.processor_queue_shutdown                       = sched_grrr_processor_queue_shutdown,
	.processor_queue_remove                         = sched_grrr_processor_queue_remove,
	.processor_queue_empty                          = sched_grrr_processor_queue_empty,
	.priority_is_urgent                             = sched_grrr_priority_is_urgent,
	.processor_csw_check                            = sched_grrr_processor_csw_check,
	.processor_queue_has_priority                   = sched_grrr_processor_queue_has_priority,
	.initial_quantum_size                           = sched_grrr_initial_quantum_size,
	.initial_thread_sched_mode                      = sched_grrr_initial_thread_sched_mode,
	.can_update_priority                            = sched_grrr_can_update_priority,
	.update_priority                                = sched_grrr_update_priority,
	.lightweight_update_priority                    = sched_grrr_lightweight_update_priority,
	.quantum_expire                                 = sched_default_quantum_expire,
	.processor_runq_count                           = sched_grrr_processor_runq_count,
	.processor_runq_stats_count_sum                 = sched_grrr_processor_runq_stats_count_sum,
	.processor_bound_count                          = sched_grrr_processor_bound_count,
	.thread_update_scan                             = sched_grrr_thread_update_scan,
	.direct_dispatch_to_idle_processors             = TRUE,
	.multiple_psets_enabled                         = TRUE,
	.sched_groups_enabled                           = FALSE,
};

extern int	max_unsafe_quanta;

static uint32_t grrr_quantum_us;
static uint32_t grrr_quantum;

static uint64_t			sched_grrr_tick_deadline;

static void
sched_grrr_init(void)
{
	if (default_preemption_rate < 1)
		default_preemption_rate = 100;
	grrr_quantum_us = (1000 * 1000) / default_preemption_rate;
	
	printf("standard grrr timeslicing quantum is %d us\n", grrr_quantum_us);

	grrr_priority_mapping_init();
}

static void
sched_grrr_timebase_init(void)
{
	uint64_t	abstime;

	/* standard timeslicing quantum */
	clock_interval_to_absolutetime_interval(
											grrr_quantum_us, NSEC_PER_USEC, &abstime);
	assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
	grrr_quantum = (uint32_t)abstime;
	
	thread_depress_time = 1 * grrr_quantum;
	default_timeshare_computation = grrr_quantum / 2;
	default_timeshare_constraint = grrr_quantum;
	
	max_unsafe_computation = max_unsafe_quanta * grrr_quantum;
	sched_safe_duration = 2 * max_unsafe_quanta * grrr_quantum;

}

static void
sched_grrr_processor_init(processor_t processor)
{
	grrr_runqueue_init(&processor->grrr_runq);
}

static void
sched_grrr_pset_init(processor_set_t pset __unused)
{
}

static void
sched_grrr_maintenance_continuation(void)
{
	uint64_t			abstime = mach_absolute_time();
	
	grrr_rescale_tick++;
    
	/*
	 *  Compute various averages.
	 */
	compute_averages(1);
	
	if (sched_grrr_tick_deadline == 0)
		sched_grrr_tick_deadline = abstime;
	
	clock_deadline_for_periodic_event(10*sched_one_second_interval, abstime,
						&sched_grrr_tick_deadline);
	
	assert_wait_deadline((event_t)sched_grrr_maintenance_continuation, THREAD_UNINT, sched_grrr_tick_deadline);
	thread_block((thread_continue_t)sched_grrr_maintenance_continuation);
	/*NOTREACHED*/
}


static thread_t
sched_grrr_choose_thread(processor_t		processor,
						  int				priority __unused,
						  ast_t				reason __unused)
{
	grrr_run_queue_t		rq = &processor->grrr_runq;
	
	return 	grrr_select(rq);
}

static thread_t
sched_grrr_steal_thread(processor_set_t		pset)
{
	pset_unlock(pset);
	
	return (THREAD_NULL);
	
}

static int
sched_grrr_compute_priority(thread_t thread)
{
	return thread->base_pri;
}

static processor_t
sched_grrr_choose_processor(	processor_set_t		pset,
							 processor_t			processor,
							 thread_t			thread)
{
	return choose_processor(pset, processor, thread);
}

static boolean_t
sched_grrr_processor_enqueue(
							 processor_t			processor,
							 thread_t			thread,
							 integer_t			options __unused)
{
	grrr_run_queue_t		rq = &processor->grrr_runq;
	boolean_t				result;
	
	result = grrr_enqueue(rq, thread);
	
	thread->runq = processor;
	
	return result;
}

static void
sched_grrr_processor_queue_shutdown(
									 processor_t			processor)
{
	processor_set_t		pset = processor->processor_set;
	thread_t			thread;
	queue_head_t		tqueue, bqueue;
	
	queue_init(&tqueue);
	queue_init(&bqueue);
	
	while ((thread = sched_grrr_choose_thread(processor, IDLEPRI, AST_NONE)) != THREAD_NULL) {
		if (thread->bound_processor == PROCESSOR_NULL) {
			enqueue_tail(&tqueue, (queue_entry_t)thread);
		} else {
			enqueue_tail(&bqueue, (queue_entry_t)thread);				
		}
	}
	
	while ((thread = (thread_t)(void *)dequeue_head(&bqueue)) != THREAD_NULL) {
		sched_grrr_processor_enqueue(processor, thread, SCHED_TAILQ);
	}	
	
	pset_unlock(pset);
	
	while ((thread = (thread_t)(void *)dequeue_head(&tqueue)) != THREAD_NULL) {
		thread_lock(thread);
		
		thread_setrun(thread, SCHED_TAILQ);
		
		thread_unlock(thread);
	}
}

static boolean_t
sched_grrr_processor_queue_remove(
								processor_t			processor,
								thread_t		thread)
{
	void *			rqlock;
	
	rqlock = &processor->processor_set->sched_lock;
	simple_lock(rqlock);
	
	if (processor == thread->runq) {
		/*
		 *	Thread is on a run queue and we have a lock on
		 *	that run queue.
		 */
		grrr_run_queue_t		rq = &processor->grrr_runq;

		grrr_remove(rq, thread);
	} else {
		/*
		 *	The thread left the run queue before we could
		 * 	lock the run queue.
		 */
		assert(thread->runq == PROCESSOR_NULL);
		processor = PROCESSOR_NULL;		
	}
	
	simple_unlock(rqlock);
	
	return (processor != PROCESSOR_NULL);	
}
				   
static boolean_t
sched_grrr_processor_queue_empty(processor_t		processor __unused)
{
	boolean_t result;
	
	result = (processor->grrr_runq.count == 0);
	
	return result;
}

static boolean_t
sched_grrr_processor_queue_has_priority(processor_t		processor,
										 int				priority,
										 boolean_t		gte __unused)
{
	grrr_run_queue_t		rq = &processor->grrr_runq;
	unsigned int	i;

	i = grrr_group_mapping[grrr_priority_mapping[priority]];
	for ( ; i < NUM_GRRR_GROUPS; i++) {
		if (rq->groups[i].count > 0)
			return (TRUE);
	}
	
	return (FALSE);
}

/* Implement sched_preempt_pri in code */
static boolean_t
sched_grrr_priority_is_urgent(int priority)
{
	if (priority <= BASEPRI_FOREGROUND)
		return FALSE;
	
	if (priority < MINPRI_KERNEL)
		return TRUE;

	if (priority >= BASEPRI_PREEMPT)
		return TRUE;
	
	return FALSE;
}

static ast_t
sched_grrr_processor_csw_check(processor_t processor)
{
	int				count;
	
	count = sched_grrr_processor_runq_count(processor);
	
	if (count > 0) {
		
		return AST_PREEMPT;
	}
	
	return AST_NONE;
}

static uint32_t
sched_grrr_initial_quantum_size(thread_t thread __unused)
{
	return grrr_quantum;
}

static sched_mode_t
sched_grrr_initial_thread_sched_mode(task_t parent_task)
{
	if (parent_task == kernel_task)
		return TH_MODE_FIXED;
	else
		return TH_MODE_TIMESHARE;	
}

static boolean_t
sched_grrr_can_update_priority(thread_t	thread __unused)
{
	return FALSE;
}

static void
sched_grrr_update_priority(thread_t	thread __unused)
{
	
}

static void
sched_grrr_lightweight_update_priority(thread_t	thread __unused)
{
	return;
}

static int
sched_grrr_processor_runq_count(processor_t	processor)
{
	return processor->grrr_runq.count;
}

static uint64_t
sched_grrr_processor_runq_stats_count_sum(processor_t	processor)
{
	return processor->grrr_runq.runq_stats.count_sum;
}

static int
sched_grrr_processor_bound_count(__unused processor_t	processor)
{
	return 0;
}

static void
sched_grrr_thread_update_scan(__unused sched_update_scan_context_t scan_context)
{

}

#endif /* defined(CONFIG_SCHED_GRRR) */

#if defined(CONFIG_SCHED_GRRR_CORE)

static void
grrr_priority_mapping_init(void)
{
	unsigned int i;
	
	/* Map 0->0 up to 10->20 */
	for (i=0; i <= 10; i++) {
		grrr_priority_mapping[i] = 2*i;
	}
	
	/* Map user priorities 11->33 up to 51 -> 153 */
	for (i=11; i <= 51; i++) {
		grrr_priority_mapping[i] = 3*i;
	}
	
	/* Map high priorities 52->180 up to 127->255 */
	for (i=52; i <= 127; i++) {
		grrr_priority_mapping[i] = 128 + i;
	}
	
	for (i = 0; i < NUM_GRRR_PROPORTIONAL_PRIORITIES; i++) {
		
#if 0		
		unsigned j, k;
		/* Calculate log(i); */
		for (j=0, k=1; k <= i; j++, k *= 2);
#endif
		
		/* Groups of 4 */
		grrr_group_mapping[i] = i >> 2;
	}
	
}

static thread_t
grrr_intragroup_schedule(grrr_group_t group)
{
	thread_t thread;

	if (group->count == 0) {
		return THREAD_NULL;
	}
	
	thread = group->current_client;
	if (thread == THREAD_NULL) {
		thread = (thread_t)(void *)queue_first(&group->clients);
	}
	
	if (1 /* deficit */) {
		group->current_client = (thread_t)(void *)queue_next((queue_entry_t)thread);
		if (queue_end(&group->clients, (queue_entry_t)group->current_client)) {
			group->current_client = (thread_t)(void *)queue_first(&group->clients);
		}
		
		thread = group->current_client;
	}
	
	return thread;
}

static thread_t
grrr_intergroup_schedule(grrr_run_queue_t rq)
{
	thread_t thread;
	grrr_group_t group;
	
	if (rq->count == 0) {
		return THREAD_NULL;
	}
	
	group = rq->current_group;
	
	if (group == GRRR_GROUP_NULL) {
		group = (grrr_group_t)queue_first(&rq->sorted_group_list);
	}
	
	thread = grrr_intragroup_schedule(group);
	
	if ((group->work >= (UINT32_MAX-256)) || (rq->last_rescale_tick != grrr_rescale_tick)) {
		grrr_rescale_work(rq);
	}
	group->work++;
	
	if (queue_end(&rq->sorted_group_list, queue_next((queue_entry_t)group))) {
		/* last group, go back to beginning */
		group = (grrr_group_t)queue_first(&rq->sorted_group_list);
	} else {
		grrr_group_t nextgroup = (grrr_group_t)queue_next((queue_entry_t)group);
		uint64_t orderleft, orderright;
		
		/*
		 * The well-ordering condition for intergroup selection is:
		 *
		 * (group->work+1) / (nextgroup->work+1) > (group->weight) / (nextgroup->weight)
		 *
		 * Multiply both sides by their denominators to avoid division
		 *
		 */
		orderleft = (group->work + 1) * ((uint64_t)nextgroup->weight);
		orderright = (nextgroup->work + 1) * ((uint64_t)group->weight);
		if (orderleft > orderright) {
			group = nextgroup;
		} else {
			group = (grrr_group_t)queue_first(&rq->sorted_group_list);
		}
	}
	
	rq->current_group = group;
	
	return thread;
}

static void
grrr_runqueue_init(grrr_run_queue_t		runq)
{
	grrr_group_index_t index;
	
	runq->count = 0;
	
	for (index = 0; index < NUM_GRRR_GROUPS; index++) {
		unsigned int prisearch;

		for (prisearch = 0;
			 prisearch < NUM_GRRR_PROPORTIONAL_PRIORITIES;
			 prisearch++) {
			if (grrr_group_mapping[prisearch] == index) {
				runq->groups[index].minpriority = (grrr_proportional_priority_t)prisearch;
				break;
			}
		}
		
		runq->groups[index].index = index;

		queue_init(&runq->groups[index].clients);
		runq->groups[index].count = 0;
		runq->groups[index].weight = 0;
		runq->groups[index].work = 0;
		runq->groups[index].current_client = THREAD_NULL;
	}
	
	queue_init(&runq->sorted_group_list);
	runq->weight = 0;
	runq->current_group = GRRR_GROUP_NULL;
}

static void
grrr_rescale_work(grrr_run_queue_t rq)
{
	grrr_group_index_t index;

	/* avoid overflow by scaling by 1/8th */
	for (index = 0; index < NUM_GRRR_GROUPS; index++) {
		rq->groups[index].work >>= 3;
	}

	rq->last_rescale_tick = grrr_rescale_tick;
}

static boolean_t
grrr_enqueue(
							 grrr_run_queue_t			rq,
							 thread_t			thread)
{							 
	grrr_proportional_priority_t	gpriority;
	grrr_group_index_t		gindex;
	grrr_group_t			group;

	gpriority = grrr_priority_mapping[thread->sched_pri];
	gindex = grrr_group_mapping[gpriority];
	group = &rq->groups[gindex];

#if 0
	thread->grrr_deficit = 0;
#endif
	
	if (group->count == 0) {
		/* Empty group, this is the first client */
		enqueue_tail(&group->clients, (queue_entry_t)thread);
		group->count = 1;
		group->weight = gpriority;
		group->current_client = thread;
	} else {
		/* Insert before the current client */
		if (group->current_client == THREAD_NULL ||
			queue_first(&group->clients) == (queue_entry_t)group->current_client) {
			enqueue_head(&group->clients, (queue_entry_t)thread);
		} else {
			insque((queue_entry_t)thread, queue_prev((queue_entry_t)group->current_client));
		}
		SCHED_STATS_RUNQ_CHANGE(&rq->runq_stats, rq->count);
		group->count++;
		group->weight += gpriority;

		/* Since there was already a client, this is on the per-processor sorted list already */
		remqueue((queue_entry_t)group);
	}
	
	grrr_sorted_list_insert_group(rq, group);

	rq->count++;
	rq->weight += gpriority;
	
	return (FALSE);
}

static thread_t
grrr_select(grrr_run_queue_t	rq)
{
	thread_t		thread;

	thread = grrr_intergroup_schedule(rq);
	if (thread != THREAD_NULL) {
		grrr_proportional_priority_t	gpriority;
		grrr_group_index_t		gindex;
		grrr_group_t			group;
		
		gpriority = grrr_priority_mapping[thread->sched_pri];
		gindex = grrr_group_mapping[gpriority];
		group = &rq->groups[gindex];
		
		remqueue((queue_entry_t)thread);
		SCHED_STATS_RUNQ_CHANGE(&rq->runq_stats, rq->count);
		group->count--;
		group->weight -= gpriority;
		if (group->current_client == thread) {
			group->current_client = THREAD_NULL;
		}
		
		remqueue((queue_entry_t)group);
		if (group->count == 0) {
			if (rq->current_group == group) {
				rq->current_group = GRRR_GROUP_NULL;
			}
		} else {
			/* Need to re-insert in sorted location */
			grrr_sorted_list_insert_group(rq, group);
		}
		
		rq->count--;
		rq->weight -= gpriority;
		
		thread->runq = PROCESSOR_NULL;
	}		
	
	
	return (thread);
}

static void
grrr_remove(
								 grrr_run_queue_t			rq,
								 thread_t		thread)
{				   
	grrr_proportional_priority_t	gpriority;
	grrr_group_index_t		gindex;
	grrr_group_t			group;
	
	gpriority = grrr_priority_mapping[thread->sched_pri];
	gindex = grrr_group_mapping[gpriority];
	group = &rq->groups[gindex];
	
	remqueue((queue_entry_t)thread);
	SCHED_STATS_RUNQ_CHANGE(&rq->runq_stats, rq->count);
	group->count--;
	group->weight -= gpriority;
	if (group->current_client == thread) {
		group->current_client = THREAD_NULL;
	}
	
	remqueue((queue_entry_t)group);
	if (group->count == 0) {
		if (rq->current_group == group) {
			rq->current_group = GRRR_GROUP_NULL;
		}
	} else {
		/* Need to re-insert in sorted location */
		grrr_sorted_list_insert_group(rq, group);
	}
	
	rq->count--;
	rq->weight -= gpriority;
	
	thread->runq = PROCESSOR_NULL;
}

static void
grrr_sorted_list_insert_group(grrr_run_queue_t rq,
												grrr_group_t group)
{
	/* Simple insertion sort */
	if (queue_empty(&rq->sorted_group_list)) {
		enqueue_tail(&rq->sorted_group_list, (queue_entry_t)group);
	} else {
		grrr_group_t search_group;
		
		/* Start searching from the head (heaviest weight) for the first
		 * element less than us, so we can insert before it
		 */
		search_group = (grrr_group_t)queue_first(&rq->sorted_group_list);
		while (!queue_end(&rq->sorted_group_list, (queue_entry_t)search_group) ) {
			
			if (search_group->weight < group->weight) {
				/* we should be before this */
				search_group = (grrr_group_t)queue_prev((queue_entry_t)search_group);
				break;
			} if (search_group->weight == group->weight) {
				/* Use group index as a tie breaker */
				if (search_group->index < group->index) {
					search_group = (grrr_group_t)queue_prev((queue_entry_t)search_group);
					break;
				}
			}
			
			/* otherwise, our weight is too small, keep going */
			search_group = (grrr_group_t)queue_next((queue_entry_t)search_group);
		}
		
		if (queue_end(&rq->sorted_group_list, (queue_entry_t)search_group)) {
			enqueue_tail(&rq->sorted_group_list, (queue_entry_t)group);
		} else {
			insque((queue_entry_t)group, (queue_entry_t)search_group);
		}
	}
}

#endif /* defined(CONFIG_SCHED_GRRR_CORE) */