/* * atropos.c * --------- * * Copyright (c) 1994 University of Cambridge Computer Laboratory. * This is part of Nemesis; consult your contract for terms and conditions. * * ID : $Id: atropos.c 1.1 Tue, 13 Apr 1999 13:30:49 +0100 dr10009 $ * * This is the "atropos" CPU scheduler. */ /* Ported to Xen's generic scheduler interface by Mark Williamson * these modifications are (C) 2004 Intel Research Cambridge */ #include #include #include #include #include #define ATROPOS_TASK_UNBLOCKED 16 #define ATROPOS_TASK_WAIT 32 #define Activation_Reason_Allocated 1 #define Activation_Reason_Preempted 2 #define Activation_Reason_Extra 3 /* Atropos-specific per-domain data */ struct at_dom_info { /* MAW Xen additions */ struct task_struct *owner; /* the struct task_struct this data belongs to */ struct list_head waitq; /* wait queue */ int reason; /* reason domain was last scheduled */ /* (what remains of) the original fields */ s_time_t deadline; /* Next deadline */ s_time_t prevddln; /* Previous deadline */ s_time_t remain; /* Time remaining this period */ s_time_t period; /* Current period of time allocation */ s_time_t nat_period; /* Natural period */ s_time_t slice; /* Current length of allocation */ s_time_t nat_slice; /* Natural length of allocation */ s_time_t latency; /* Unblocking latency */ int xtratime; /* Prepared to accept extra time? */ }; /* Atropos-specific per-CPU data */ struct at_cpu_info { struct list_head waitq; /* wait queue*/ }; #define DOM_INFO(_p) ( (struct at_dom_info *)((_p)->sched_priv) ) #define CPU_INF(_p) ( (struct at_cpu_info *)((_p).sched_priv) ) #define WAITQ(cpu) (&( CPU_INF(schedule_data[cpu]) )->waitq ) #define RUNQ(cpu) (&schedule_data[cpu].runqueue) #define BESTEFFORT_QUANTUM MILLISECS(5) /* SLAB cache for struct at_dom_info objects */ static kmem_cache_t *dom_info_cache; /** calculate the length of a linked list */ static int q_len(struct list_head *q) { int i = 0; struct list_head *tmp; list_for_each(tmp, q) i++; return i; } /** waitq_el - get the task_struct that owns a wait queue list element */ static inline struct task_struct * waitq_el(struct list_head *l) { struct at_dom_info *inf; inf = list_entry(l, struct at_dom_info, waitq); return inf->owner; } /* * requeue * * Places the specified domain on the appropriate queue. * The wait queue is ordered by the time at which the domain * will receive more CPU time. If a domain has no guaranteed time * left then the domain will be placed on the WAIT queue until * its next period. * * Note that domains can be on the wait queue with remain > 0 * as a result of being blocked for a short time. * These are scheduled in preference to domains with remain < 0 * in an attempt to improve interactive performance. */ static void requeue(struct task_struct *sdom) { struct at_dom_info *inf = DOM_INFO(sdom); struct list_head *prev = WAITQ(sdom->processor); struct list_head *next; if(sdom->state == ATROPOS_TASK_WAIT || sdom->state == ATROPOS_TASK_UNBLOCKED ) { /* insert into ordered wait queue */ prev = WAITQ(sdom->processor); list_for_each(next, WAITQ(sdom->processor)) { struct at_dom_info *i = list_entry(next, struct at_dom_info, waitq); if( i->deadline > inf->deadline ) { __list_add(&inf->waitq, prev, next); break; } prev = next; } /* put the domain on the end of the list if it hasn't been put * elsewhere */ if ( next == WAITQ(sdom->processor)) list_add_tail(&inf->waitq, WAITQ(sdom->processor)); } else if(sdom->state == TASK_RUNNING) { /* insert into ordered run queue */ prev = RUNQ(sdom->processor); list_for_each(next, RUNQ(sdom->processor)) { struct task_struct *p = list_entry(next, struct task_struct, run_list); if( DOM_INFO(p)->deadline > inf->deadline || is_idle_task(p) ) { __list_add(&sdom->run_list, prev, next); break; } prev = next; } if ( next == RUNQ(sdom->processor) ) list_add_tail(&sdom->run_list, RUNQ(sdom->processor)); } /* silently ignore tasks in other states like BLOCKED, DYING, STOPPED, etc * - they shouldn't be on any queue */ } /* prepare a task to be added to scheduling */ static void at_add_task(struct task_struct *p) { s_time_t now = NOW(); ASSERT( p->sched_priv != NULL ); DOM_INFO(p)->owner = p; p->lastschd = now; /* DOM 0's parameters must be set here for it to boot the system! */ if(p->domain == 0) { DOM_INFO(p)->remain = MILLISECS(15); DOM_INFO(p)->nat_period = DOM_INFO(p)->period = MILLISECS(20); DOM_INFO(p)->nat_slice = DOM_INFO(p)->slice = MILLISECS(15); DOM_INFO(p)->latency = MILLISECS(5); DOM_INFO(p)->xtratime = 1; DOM_INFO(p)->deadline = now; DOM_INFO(p)->prevddln = now; } else /* other domains run basically best effort unless otherwise set */ { DOM_INFO(p)->remain = 0; DOM_INFO(p)->nat_period = DOM_INFO(p)->period = SECONDS(10); DOM_INFO(p)->nat_slice = DOM_INFO(p)->slice = MILLISECS(10); DOM_INFO(p)->latency = SECONDS(10); DOM_INFO(p)->xtratime = 1; DOM_INFO(p)->deadline = now + SECONDS(10); DOM_INFO(p)->prevddln = 0; } INIT_LIST_HEAD(&(DOM_INFO(p)->waitq)); } /** * dequeue - remove a domain from any queues it is on. * @sdom: the task to remove */ static void dequeue(struct task_struct *sdom) { struct at_dom_info *inf = DOM_INFO(sdom); ASSERT(sdom->domain != IDLE_DOMAIN_ID); /* just delete it from all the queues! */ list_del(&inf->waitq); INIT_LIST_HEAD(&inf->waitq); if(__task_on_runqueue(sdom)) __del_from_runqueue(sdom); sdom->run_list.next = NULL; sdom->run_list.prev = NULL; } /* * unblock * * This function deals with updating the sdom for a domain * which has just been unblocked. * * Xen's Atropos treats unblocking slightly differently to Nemesis: * * - "Short blocking" domains (i.e. that unblock before their deadline has * expired) are treated the same as in nemesis (put on the wait queue and * given preferential treatment in selecting domains for extra time). * * - "Long blocking" domains do not simply have their period truncated to their * unblocking latency as before but also have their slice recomputed to be the * same fraction of their new period. Each time the domain is scheduled, the * period and slice are doubled until they reach their original ("natural") * values, as set by the user (and stored in nat_period and nat_slice). The * idea is to give better response times to unblocking whilst preserving QoS * guarantees to other domains. */ static void unblock(struct task_struct *sdom) { s_time_t time = NOW(); struct at_dom_info *inf = DOM_INFO(sdom); dequeue(sdom); /* We distinguish two cases... short and long blocks */ if ( inf->deadline < time ) { /* Long blocking case */ /* The sdom has passed its deadline since it was blocked. Give it its new deadline based on the latency value. */ inf->prevddln = time; /* Scale the scheduling parameters as requested by the latency hint. */ inf->deadline = time + inf->latency; inf->slice = inf->nat_slice / ( inf->nat_period / inf->latency ); inf->period = inf->latency; inf->remain = inf->slice; sdom->state = TASK_RUNNING; } else { /* Short blocking case */ /* We leave REMAIN intact, but put this domain on the WAIT queue marked as recently unblocked. It will be given priority over other domains on the wait queue until while REMAIN>0 in a generous attempt to help it make up for its own foolishness. */ if(inf->remain > 0) sdom->state = ATROPOS_TASK_UNBLOCKED; else sdom->state = ATROPOS_TASK_WAIT; } requeue(sdom); } /** * ATROPOS - main scheduler function */ task_slice_t ksched_scheduler(s_time_t time) { struct task_struct *cur_sdom = current; /* Current sdom */ s_time_t newtime; s_time_t ranfor; /* How long the domain ran */ struct task_struct *sdom; /* tmp. scheduling domain */ int reason; /* reason for reschedule */ int cpu = cur_sdom->processor; /* current CPU */ struct at_dom_info *cur_info; static unsigned long waitq_rrobin = 0; int i; task_slice_t ret; cur_info = DOM_INFO(cur_sdom); ASSERT( cur_sdom != NULL); /* If we were spinning in the idle loop, there is no current * domain to deschedule. */ if (is_idle_task(cur_sdom)) goto deschedule_done; /***************************** * * Deschedule the current scheduling domain * ****************************/ /* Record the time the domain was preempted and for how long it ran. Work out if the domain is going to be blocked to save some pointless queue shuffling */ cur_sdom->lastdeschd = time; ranfor = (time - cur_sdom->lastschd); dequeue(cur_sdom); if ((cur_sdom->state == TASK_RUNNING) || (cur_sdom->state == ATROPOS_TASK_UNBLOCKED)) { /* In this block, we are doing accounting for an sdom which has been running in contracted time. Note that this could now happen even if the domain is on the wait queue (i.e. if it blocked) */ /* Deduct guaranteed time from the domain */ cur_info->remain -= ranfor; /* If guaranteed time has run out... */ if ( cur_info->remain <= 0 ) { /* Move domain to correct position in WAIT queue */ /* XXX sdom_unblocked doesn't need this since it is already in the correct place. */ cur_sdom->state = ATROPOS_TASK_WAIT; } } requeue(cur_sdom); deschedule_done: /***************************** * * We have now successfully descheduled the current sdom. * The next task is the allocate CPU time to any sdom it is due to. * ****************************/ cur_sdom = NULL; /***************************** * * Allocate CPU time to any waiting domains who have passed their * period deadline. If necessary, move them to run queue. * ****************************/ while(!list_empty(WAITQ(cpu)) && DOM_INFO(sdom = waitq_el(WAITQ(cpu)->next))->deadline <= time ) { struct at_dom_info *inf = DOM_INFO(sdom); dequeue(sdom); if ( inf->period != inf->nat_period ) { /* This domain has had its parameters adjusted as a result of * unblocking and they need to be adjusted before requeuing it */ inf->slice *= 2; inf->period *= 2; if ( inf->period > inf->nat_period ) { inf->period = inf->nat_period; inf->slice = inf->nat_slice; } } /* Domain begins a new period and receives a slice of CPU * If this domain has been blocking then throw away the * rest of it's remain - it can't be trusted */ if (inf->remain > 0) inf->remain = inf->slice; else inf->remain += inf->slice; inf->prevddln = inf->deadline; inf->deadline += inf->period; if(inf->remain > 0) sdom->state = TASK_RUNNING; else sdom->state = ATROPOS_TASK_WAIT; /* Place on the appropriate queue */ requeue(sdom); } /***************************** * * Next we need to pick an sdom to run. * If anything is actually 'runnable', we run that. * If nothing is, we pick a waiting sdom to run optimistically. * If there aren't even any of those, we have to spin waiting for an * event or a suitable time condition to happen. * ****************************/ /* we guarantee there's always something on the runqueue */ cur_sdom = list_entry(RUNQ(cpu)->next, struct task_struct, run_list); cur_info = DOM_INFO(cur_sdom); newtime = time + cur_info->remain; reason = (cur_info->prevddln > cur_sdom->lastschd) ? Activation_Reason_Allocated : Activation_Reason_Preempted; /* MAW - the idle domain is always on the run queue. We run from the * runqueue if it's NOT the idle domain or if there's nothing on the wait * queue */ if (cur_sdom->domain == IDLE_DOMAIN_ID && !list_empty(WAITQ(cpu))) { struct list_head *item; /* Try running a domain on the WAIT queue - this part of the scheduler isn't particularly efficient but then again, we don't have any guaranteed domains to worry about. */ /* See if there are any unblocked domains on the WAIT queue who we can give preferential treatment to. */ list_for_each(item,
#
# Copyright (C) 2006-2011 OpenWrt.org
#
# This is free software, licensed under the GNU General Public License v2.
# See /LICENSE for more information.
#

define KernelPackage/nls-base
  SUBMENU:=Native Language Support
  TITLE:=Native Language Support
  KCONFIG:=CONFIG_NLS
  FILES:=$(LINUX_DIR)/fs/nls/nls_base.ko
endef

define KernelPackage/nls-base/description
 Kernel module for NLS (Native Language Support)
endef

$(eval $(call KernelPackage,nls-base))


define KernelPackage/nls-cp437
  SUBMENU:=Native Language Support
  TITLE:=Codepage 437 (United States, Canada)
  KCONFIG:=CONFIG_NLS_CODEPAGE_437
  FILES:=$(LINUX_DIR)/fs/nls/nls_cp437.ko
  AUTOLOAD:=$(call AutoLoad,25,nls_cp437)
  $(call AddDepends/nls)
endef

define KernelPackage/nls-cp437/description
 Kernel module for NLS Codepage 437 (United States, Canada)
endef

$(eval $(call KernelPackage,nls-cp437))


define KernelPackage/nls-cp775
  SUBMENU:=Native Language Support
  TITLE:=Codepage 775 (Baltic Rim)
  KCONFIG:=CONFIG_NLS_CODEPAGE_775
  FILES:=$(LINUX_DIR)/fs/nls/nls_cp775.ko
  AUTOLOAD:=$(call AutoLoad,25,nls_cp775)
  $(call AddDepends/nls)
endef

define KernelPackage/nls-cp775/description
 Kernel module for NLS Codepage 775 (Baltic Rim)
endef

$(eval $(call KernelPackage,nls-cp775))


define KernelPackage/nls-cp850
  SUBMENU:=Native Language Support
  TITLE:=Codepage 850 (Europe)
  KCONFIG:=CONFIG_NLS_CODEPAGE_850
  FILES:=$(LINUX_DIR)/fs/nls/nls_cp850.ko
  AUTOLOAD:=$(call AutoLoad,25,nls_cp850)
  $(call AddDepends/nls)
endef

define KernelPackage/nls-cp850/description
 Kernel module for NLS Codepage 850 (Europe)
endef

$(eval $(call KernelPackage,nls-cp850))


define KernelPackage/nls-cp852
  SUBMENU:=Native Language Support
  TITLE:=Codepage 852 (Europe)
  KCONFIG:=CONFIG_NLS_CODEPAGE_852
  FILES:=$(LINUX_DIR)/fs/nls/nls_cp852.ko
  AUTOLOAD:=$(call AutoLoad,25,nls_cp852)
  $(call AddDepends/nls)
endef

define KernelPackage/nls-cp852/description
 Kernel module for NLS Codepage 852 (Europe)
endef

$(eval $(call KernelPackage,nls-cp852))


define KernelPackage/nls-cp862
  SUBMENU:=Native Language Support
  TITLE:=Codepage 862 (Hebrew)
  KCONFIG:=CONFIG_NLS_CODEPAGE_862
  FILES:=$(LINUX_DIR)/fs/nls/nls_cp862.ko
  AUTOLOAD:=$(call AutoLoad,25,nls_cp862)
  $(call AddDepends/nls)
endef

define KernelPackage/nls-cp862/description
  Kernel module for NLS Codepage 862 (Hebrew)
endef

$(eval $(call KernelPackage,nls-cp862))


define KernelPackage/nls-cp864
  SUBMENU:=Native Language Support
  TITLE:=Codepage 864 (Arabic)
  KCONFIG:=CONFIG_NLS_CODEPAGE_864
  FILES:=$(LINUX_DIR)/fs/nls/nls_cp864.ko
  AUTOLOAD:=$(call AutoLoad,25,nls_cp864)
  $(call AddDepends/nls)
endef

define KernelPackage/nls-cp864/description
  Kernel module for NLS Codepage 864 (Arabic)
endef

$(eval $(call KernelPackage,nls-cp864))


define KernelPackage/nls-cp866
  SUBMENU:=Native Language Support
  TITLE:=Codepage 866 (Cyrillic)
  KCONFIG:=CONFIG_NLS_CODEPAGE_866
  FILES:=$(LINUX_DIR)/fs/nls/nls_cp866.ko
  AUTOLOAD:=$(call AutoLoad,25,nls_cp866)
  $(call AddDepends/nls)
endef

define KernelPackage/nls-cp866/description
  Kernel module for NLS Codepage 866 (Cyrillic)
endef

$(eval $(call KernelPackage,nls-cp866))


define KernelPackage/nls-cp1250
  SUBMENU:=Native Language Support
  TITLE:=Codepage 1250 (Eastern Europe)
  KCONFIG:=CONFIG_NLS_CODEPAGE_1250
  FILES:=$(LINUX_DIR)/fs/nls/nls_cp1250.ko
  AUTOLOAD:=$(call AutoLoad,25,nls_cp1250)
  $(call AddDepends/nls)
endef

define KernelPackage/nls-cp1250/description
 Kernel module for NLS Codepage 1250 (Eastern Europe)
endef

$(eval $(call KernelPackage,nls-cp1250))


define KernelPackage/nls-cp1251
  SUBMENU:=Native Language Support
  TITLE:=Codepage 1251 (Russian)
  KCONFIG:=CONFIG_NLS_CODEPAGE_1251
  FILES:=$(LINUX_DIR)/fs/nls/nls_cp1251.ko
  AUTOLOAD:=$(call AutoLoad,25,nls_cp1251)
  $(call AddDepends/nls)
endef

define KernelPackage/nls-cp1251/description
 Kernel module for NLS Codepage 1251 (Russian)
endef

$(eval $(call KernelPackage,nls-cp1251))


define KernelPackage/nls-iso8859-1
  SUBMENU:=Native Language Support
  TITLE:=ISO 8859-1 (Latin 1; Western European Languages)
  KCONFIG:=CONFIG_NLS_ISO8859_1
  FILES:=$(LINUX_DIR)/fs/nls/nls_iso8859-1.ko
  AUTOLOAD:=$(call AutoLoad,25,nls_iso8859-1)
  $(call AddDepends/nls)
endef

define KernelPackage/nls-iso8859-1/description
 Kernel module for NLS ISO 8859-1 (Latin 1)
endef

$(eval $(call KernelPackage,nls-iso8859-1))


define KernelPackage/nls-iso8859-2
  SUBMENU:=Native Language Support
  TITLE:=ISO 8859-2 (Latin 2; Central European Languages)
  KCONFIG:=CONFIG_NLS_ISO8859_2
  FILES:=$(LINUX_DIR)/fs/nls/nls_iso8859-2.ko
  AUTOLOAD:=$(call AutoLoad,25,nls_iso8859-2)
  $(call AddDepends/nls)
endef

define KernelPackage/nls-iso8859-2/description
 Kernel module for NLS ISO 8859-2 (Latin 2)
endef

$(eval $(call KernelPackage,nls-iso8859-2))


define KernelPackage/nls-iso8859-6
  SUBMENU:=Native Language Support
  TITLE:=ISO 8859-6 (Arabic)
  KCONFIG:=CONFIG_NLS_ISO8859_6
  FILES:=$(LINUX_DIR)/fs/nls/nls_iso8859-6.ko
  AUTOLOAD:=$(call AutoLoad,25,nls_iso8859-6)
  $(call AddDepends/nls)
endef

define KernelPackage/nls-iso8859-6/description
 Kernel module for NLS ISO 8859-6 (Arabic)
endef

$(eval $(call KernelPackage,nls-iso8859-6))


define KernelPackage/nls-iso8859-8
  SUBMENU:=Native Language Support
  TITLE:=ISO 8859-8, CP1255 (Hebrew)
  KCONFIG:=CONFIG_NLS_ISO8859_8
  FILES:=$(LINUX_DIR)/fs/nls/nls_cp1255.ko
  AUTOLOAD:=$(call AutoLoad,25,nls_cp1255)
  $(call AddDepends/nls)
endef

define KernelPackage/nls-iso8859-8/description
 Kernel module for Hebrew charsets (ISO-8859-8, CP1255)
endef

$(eval $(call KernelPackage,nls-iso8859-8))


define KernelPackage/nls-iso8859-13
  SUBMENU:=Native Language Support
  TITLE:=ISO 8859-13 (Latin 7; Baltic)
  KCONFIG:=CONFIG_NLS_ISO8859_13
  FILES:=$(LINUX_DIR)/fs/nls/nls_iso8859-13.ko
  AUTOLOAD:=$(call AutoLoad,25,nls_iso8859-13)
  $(call AddDepends/nls)
endef

define KernelPackage/nls-iso8859-13/description
 Kernel module for NLS ISO 8859-13 (Latin 7; Baltic)
endef

$(eval $(call KernelPackage,nls-iso8859-13))


define KernelPackage/nls-iso8859-15
  SUBMENU:=Native Language Support
  TITLE:=ISO 8859-15 (Latin 9; Western, with Euro symbol)
  KCONFIG:=CONFIG_NLS_ISO8859_15
  FILES:=$(LINUX_DIR)/fs/nls/nls_iso8859-15.ko
  AUTOLOAD:=$(call AutoLoad,25,nls_iso8859-15)
  $(call AddDepends/nls)
endef

define KernelPackage/nls-iso8859-15/description
 Kernel module for NLS ISO 8859-15 (Latin 9)
endef

$(eval $(call KernelPackage,nls-iso8859-15))


define KernelPackage/nls-koi8r
  SUBMENU:=Native Language Support
  TITLE:=KOI8-R (Russian)
  KCONFIG:=CONFIG_NLS_KOI8_R
  FILES:=$(LINUX_DIR)/fs/nls/nls_koi8-r.ko
  AUTOLOAD:=$(call AutoLoad,25,nls_koi8-r)
  $(call AddDepends/nls)
endef

define KernelPackage/nls-koi8r/description
 Kernel module for NLS KOI8-R (Russian)
endef

$(eval $(call KernelPackage,nls-koi8r))


define KernelPackage/nls-utf8
  SUBMENU:=Native Language Support
  TITLE:=UTF-8
  KCONFIG:=CONFIG_NLS_UTF8
  FILES:=$(LINUX_DIR)/fs/nls/nls_utf8.ko
  AUTOLOAD:=$(call AutoLoad,25,nls_utf8)
  $(call AddDepends/nls)
endef

define KernelPackage/nls-utf8/description
 Kernel module for NLS UTF-8
endef

$(eval $(call KernelPackage,nls-utf8))
generated by cgit v1.2.3 (git 2.25.1) at 2026-01-31 01:52:31 +0000