From ec12cb7f31e28854efae7dd6f9544e0a66379040 Mon Sep 17 00:00:00 2001 From: Paul Turner Date: Thu, 21 Jul 2011 09:43:30 -0700 Subject: sched: Accumulate per-cfs_rq cpu usage and charge against bandwidth Account bandwidth usage on the cfs_rq level versus the task_groups to which they belong. Whether we are tracking bandwidth on a given cfs_rq is maintained under cfs_rq->runtime_enabled. cfs_rq's which belong to a bandwidth constrained task_group have their runtime accounted via the update_curr() path, which withdraws bandwidth from the global pool as desired. Updates involving the global pool are currently protected under cfs_bandwidth->lock, local runtime is protected by rq->lock. This patch only assigns and tracks quota, no action is taken in the case that cfs_rq->runtime_used exceeds cfs_rq->runtime_assigned. Signed-off-by: Paul Turner Signed-off-by: Nikhil Rao Signed-off-by: Bharata B Rao Reviewed-by: Hidetoshi Seto Signed-off-by: Peter Zijlstra Link: http://lkml.kernel.org/r/20110721184757.179386821@google.com Signed-off-by: Ingo Molnar --- include/linux/sched.h | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'include/linux') diff --git a/include/linux/sched.h b/include/linux/sched.h index 4ac2c0578e0f..bc6f5f2e24fa 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -2040,6 +2040,10 @@ static inline void sched_autogroup_fork(struct signal_struct *sig) { } static inline void sched_autogroup_exit(struct signal_struct *sig) { } #endif +#ifdef CONFIG_CFS_BANDWIDTH +extern unsigned int sysctl_sched_cfs_bandwidth_slice; +#endif + #ifdef CONFIG_RT_MUTEXES extern int rt_mutex_getprio(struct task_struct *p); extern void rt_mutex_setprio(struct task_struct *p, int prio); -- cgit v1.2.3 From 1230db8e1543c0471dd165727d34647ab098cc1e Mon Sep 17 00:00:00 2001 From: Huang Ying Date: Thu, 8 Sep 2011 14:00:42 +0800 Subject: llist: Make some llist functions inline Because llist code will be used in performance critical scheduler code path, make llist_add() and llist_del_all() inline to avoid function calling overhead and related 'glue' overhead. Signed-off-by: Huang Ying Acked-by: Mathieu Desnoyers Signed-off-by: Peter Zijlstra Link: http://lkml.kernel.org/r/1315461646-1379-2-git-send-email-ying.huang@intel.com Signed-off-by: Ingo Molnar --- include/linux/llist.h | 64 ++++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 58 insertions(+), 6 deletions(-) (limited to 'include/linux') diff --git a/include/linux/llist.h b/include/linux/llist.h index aa0c8b5b3cd0..3eccdfd66096 100644 --- a/include/linux/llist.h +++ b/include/linux/llist.h @@ -37,8 +37,28 @@ * architectures that don't have NMI-safe cmpxchg implementation, the * list can NOT be used in NMI handler. So code uses the list in NMI * handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG. + * + * Copyright 2010,2011 Intel Corp. + * Author: Huang Ying + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License version + * 2 as published by the Free Software Foundation; + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ +#include +#include +#include + struct llist_head { struct llist_node *first; }; @@ -113,14 +133,46 @@ static inline void init_llist_head(struct llist_head *list) * test whether the list is empty without deleting something from the * list. */ -static inline int llist_empty(const struct llist_head *head) +static inline bool llist_empty(const struct llist_head *head) { return ACCESS_ONCE(head->first) == NULL; } -void llist_add(struct llist_node *new, struct llist_head *head); -void llist_add_batch(struct llist_node *new_first, struct llist_node *new_last, - struct llist_head *head); -struct llist_node *llist_del_first(struct llist_head *head); -struct llist_node *llist_del_all(struct llist_head *head); +/** + * llist_add - add a new entry + * @new: new entry to be added + * @head: the head for your lock-less list + */ +static inline void llist_add(struct llist_node *new, struct llist_head *head) +{ + struct llist_node *entry, *old_entry; + +#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG + BUG_ON(in_nmi()); +#endif + + entry = head->first; + do { + old_entry = entry; + new->next = entry; + cpu_relax(); + } while ((entry = cmpxchg(&head->first, old_entry, new)) != old_entry); +} + +/** + * llist_del_all - delete all entries from lock-less list + * @head: the head of lock-less list to delete all entries + * + * If list is empty, return NULL, otherwise, delete all entries and + * return the pointer to the first entry. The order of entries + * deleted is from the newest to the oldest added one. + */ +static inline struct llist_node *llist_del_all(struct llist_head *head) +{ +#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG + BUG_ON(in_nmi()); +#endif + + return xchg(&head->first, NULL); +} #endif /* LLIST_H */ -- cgit v1.2.3 From 2c30245c65e8ebc3080b75ce65572ab8140bad0b Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Tue, 4 Oct 2011 12:43:11 +0200 Subject: llist: Remove the platform-dependent NMI checks Remove the nmi() checks spread around the code. in_nmi() is not available on every architecture and it's a pretty obscure and ugly check in any case. Cc: Huang Ying Cc: Mathieu Desnoyers Cc: Peter Zijlstra Link: http://lkml.kernel.org/r/1315461646-1379-3-git-send-email-ying.huang@intel.com Signed-off-by: Ingo Molnar --- include/linux/llist.h | 12 ++---------- 1 file changed, 2 insertions(+), 10 deletions(-) (limited to 'include/linux') diff --git a/include/linux/llist.h b/include/linux/llist.h index 3eccdfd66096..65fca1cbf514 100644 --- a/include/linux/llist.h +++ b/include/linux/llist.h @@ -35,8 +35,8 @@ * * The basic atomic operation of this list is cmpxchg on long. On * architectures that don't have NMI-safe cmpxchg implementation, the - * list can NOT be used in NMI handler. So code uses the list in NMI - * handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG. + * list can NOT be used in NMI handlers. So code that uses the list in + * an NMI handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG. * * Copyright 2010,2011 Intel Corp. * Author: Huang Ying @@ -147,10 +147,6 @@ static inline void llist_add(struct llist_node *new, struct llist_head *head) { struct llist_node *entry, *old_entry; -#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG - BUG_ON(in_nmi()); -#endif - entry = head->first; do { old_entry = entry; @@ -169,10 +165,6 @@ static inline void llist_add(struct llist_node *new, struct llist_head *head) */ static inline struct llist_node *llist_del_all(struct llist_head *head) { -#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG - BUG_ON(in_nmi()); -#endif - return xchg(&head->first, NULL); } #endif /* LLIST_H */ -- cgit v1.2.3 From a3127336b71f6833d1483c856dce91fe558dc3a9 Mon Sep 17 00:00:00 2001 From: Huang Ying Date: Thu, 8 Sep 2011 14:00:44 +0800 Subject: llist: Move cpu_relax() to after the cmpxchg() If in llist_add()/etc. functions the first cmpxchg() call succeeds, it is not necessary to use cpu_relax() before the cmpxchg(). So cpu_relax() in a busy loop involving cmpxchg() should go after cmpxchg() instead of before that. This patch fixes this for all involved llist functions. Signed-off-by: Huang Ying Acked-by: Mathieu Desnoyers Signed-off-by: Peter Zijlstra Link: http://lkml.kernel.org/r/1315461646-1379-4-git-send-email-ying.huang@intel.com Signed-off-by: Ingo Molnar --- include/linux/llist.h | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) (limited to 'include/linux') diff --git a/include/linux/llist.h b/include/linux/llist.h index 65fca1cbf514..ca91875286bf 100644 --- a/include/linux/llist.h +++ b/include/linux/llist.h @@ -148,11 +148,14 @@ static inline void llist_add(struct llist_node *new, struct llist_head *head) struct llist_node *entry, *old_entry; entry = head->first; - do { + for (;;) { old_entry = entry; new->next = entry; + entry = cmpxchg(&head->first, old_entry, new); + if (entry == old_entry) + break; cpu_relax(); - } while ((entry = cmpxchg(&head->first, old_entry, new)) != old_entry); + } } /** -- cgit v1.2.3 From 781f7fd916fc77a862e20063ed3aeedf173234f9 Mon Sep 17 00:00:00 2001 From: Huang Ying Date: Thu, 8 Sep 2011 14:00:45 +0800 Subject: llist: Return whether list is empty before adding in llist_add() Extend the llist_add*() functions to return a success indicator, this allows us in the scheduler code to send an IPI if the queue was empty. ( There's no effect on existing users, because the list_add_xxx() functions are inline, thus this will be optimized out by the compiler if not used by callers. ) Signed-off-by: Huang Ying Cc: Mathieu Desnoyers Signed-off-by: Peter Zijlstra Link: http://lkml.kernel.org/r/1315461646-1379-5-git-send-email-ying.huang@intel.com Signed-off-by: Ingo Molnar --- include/linux/llist.h | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (limited to 'include/linux') diff --git a/include/linux/llist.h b/include/linux/llist.h index ca91875286bf..27bbdf5ddf82 100644 --- a/include/linux/llist.h +++ b/include/linux/llist.h @@ -142,8 +142,10 @@ static inline bool llist_empty(const struct llist_head *head) * llist_add - add a new entry * @new: new entry to be added * @head: the head for your lock-less list + * + * Return whether list is empty before adding. */ -static inline void llist_add(struct llist_node *new, struct llist_head *head) +static inline bool llist_add(struct llist_node *new, struct llist_head *head) { struct llist_node *entry, *old_entry; @@ -156,6 +158,8 @@ static inline void llist_add(struct llist_node *new, struct llist_head *head) break; cpu_relax(); } + + return old_entry == NULL; } /** -- cgit v1.2.3 From 38aaf8090d34b623b7919d8c933f6e938c9bf44b Mon Sep 17 00:00:00 2001 From: Huang Ying Date: Thu, 8 Sep 2011 14:00:46 +0800 Subject: irq_work: Use llist in the struct irq_work logic Use llist in irq_work instead of the lock-less linked list implementation in irq_work to avoid the code duplication. Signed-off-by: Huang Ying Signed-off-by: Peter Zijlstra Link: http://lkml.kernel.org/r/1315461646-1379-6-git-send-email-ying.huang@intel.com Signed-off-by: Ingo Molnar --- include/linux/irq_work.h | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-) (limited to 'include/linux') diff --git a/include/linux/irq_work.h b/include/linux/irq_work.h index 4fa09d4d0b71..6a9e8f5399e2 100644 --- a/include/linux/irq_work.h +++ b/include/linux/irq_work.h @@ -1,20 +1,23 @@ #ifndef _LINUX_IRQ_WORK_H #define _LINUX_IRQ_WORK_H +#include + struct irq_work { - struct irq_work *next; + unsigned long flags; + struct llist_node llnode; void (*func)(struct irq_work *); }; static inline -void init_irq_work(struct irq_work *entry, void (*func)(struct irq_work *)) +void init_irq_work(struct irq_work *work, void (*func)(struct irq_work *)) { - entry->next = NULL; - entry->func = func; + work->flags = 0; + work->func = func; } -bool irq_work_queue(struct irq_work *entry); +bool irq_work_queue(struct irq_work *work); void irq_work_run(void); -void irq_work_sync(struct irq_work *entry); +void irq_work_sync(struct irq_work *work); #endif /* _LINUX_IRQ_WORK_H */ -- cgit v1.2.3 From 924f8f5af31423529cc3940cb2ae9fee736b7517 Mon Sep 17 00:00:00 2001 From: Peter Zijlstra Date: Mon, 12 Sep 2011 13:12:28 +0200 Subject: llist: Add llist_next() So we don't have to expose the struct list_node member. Cc: Huang Ying Cc: Andrew Morton Signed-off-by: Peter Zijlstra Link: http://lkml.kernel.org/r/1315836348.26517.41.camel@twins Signed-off-by: Ingo Molnar --- include/linux/llist.h | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'include/linux') diff --git a/include/linux/llist.h b/include/linux/llist.h index 27bbdf5ddf82..e2e96d04ee48 100644 --- a/include/linux/llist.h +++ b/include/linux/llist.h @@ -138,6 +138,11 @@ static inline bool llist_empty(const struct llist_head *head) return ACCESS_ONCE(head->first) == NULL; } +static inline struct llist_node *llist_next(struct llist_node *node) +{ + return node->next; +} + /** * llist_add - add a new entry * @new: new entry to be added -- cgit v1.2.3 From fa14ff4accfb24e59d2473f3d864d6648d80563b Mon Sep 17 00:00:00 2001 From: Peter Zijlstra Date: Mon, 12 Sep 2011 13:06:17 +0200 Subject: sched: Convert to struct llist Use the generic llist primitives. We had a private lockless list implementation in the scheduler in the wake-list code, now that we have a generic llist implementation that provides all required operations, switch to it. This patch is not expected to change any behavior. Signed-off-by: Peter Zijlstra Cc: Huang Ying Cc: Andrew Morton Link: http://lkml.kernel.org/r/1315836353.26517.42.camel@twins Signed-off-by: Ingo Molnar --- include/linux/sched.h | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'include/linux') diff --git a/include/linux/sched.h b/include/linux/sched.h index 9fda2888a6ab..fc3e8911818a 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -90,6 +90,7 @@ struct sched_param { #include #include #include +#include #include @@ -1225,7 +1226,7 @@ struct task_struct { unsigned int ptrace; #ifdef CONFIG_SMP - struct task_struct *wake_entry; + struct llist_node wake_entry; int on_cpu; #endif int on_rq; -- cgit v1.2.3 From f0f1d32f931b705c4ee5dd374074d34edf3eae14 Mon Sep 17 00:00:00 2001 From: Peter Zijlstra Date: Mon, 12 Sep 2011 15:50:49 +0200 Subject: llist: Remove cpu_relax() usage in cmpxchg loops Initial benchmarks show they're a net loss: $ for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor ; do echo performance > $i; done $ echo 4096 32000 64 128 > /proc/sys/kernel/sem $ ./sembench -t 2048 -w 1900 -o 0 Pre: run time 30 seconds 778936 worker burns per second run time 30 seconds 912190 worker burns per second run time 30 seconds 817506 worker burns per second run time 30 seconds 830870 worker burns per second run time 30 seconds 845056 worker burns per second Post: run time 30 seconds 905920 worker burns per second run time 30 seconds 849046 worker burns per second run time 30 seconds 886286 worker burns per second run time 30 seconds 822320 worker burns per second run time 30 seconds 900283 worker burns per second So about 4% faster. (!) cpu_relax() stalls the pipeline, therefore, when used in a tight loop it has the following benefits: - allows SMT siblings to have a go; - reduces pressure on the CPU interconnect. However, cmpxchg loops are unfair and thus have unbounded completion time, therefore we should avoid getting in such heavily contended situations where the above benefits make any difference. A typical cmpxchg loop should not go round more than a handfull of times at worst, therefore adding extra delays just slows things down. Since the llist primitives are new, there aren't any bad users yet, and we should avoid growing them. Heavily contended sites should generally be better off using the ticket locks for serialization since they provide bounded completion times (fifo-fair over the cpus). Signed-off-by: Peter Zijlstra Cc: Huang Ying Cc: Andrew Morton Link: http://lkml.kernel.org/r/1315836358.26517.43.camel@twins Signed-off-by: Ingo Molnar --- include/linux/llist.h | 1 - 1 file changed, 1 deletion(-) (limited to 'include/linux') diff --git a/include/linux/llist.h b/include/linux/llist.h index e2e96d04ee48..837fb4ae66fb 100644 --- a/include/linux/llist.h +++ b/include/linux/llist.h @@ -161,7 +161,6 @@ static inline bool llist_add(struct llist_node *new, struct llist_head *head) entry = cmpxchg(&head->first, old_entry, new); if (entry == old_entry) break; - cpu_relax(); } return old_entry == NULL; -- cgit v1.2.3 From 540f41edc15473ca3b2876de72646546ae101374 Mon Sep 17 00:00:00 2001 From: Stephen Rothwell Date: Wed, 5 Oct 2011 17:25:28 +1100 Subject: llist: Add back llist_add_batch() and llist_del_first() prototypes Commit 1230db8e1543 ("llist: Make some llist functions inline") has deleted the definitions, causing problems for (not upstream yet) code that tries to make use of them. Signed-off-by: Stephen Rothwell Acked-by: Peter Zijlstra Cc: Huang Ying Cc: David Miller Link: http://lkml.kernel.org/r/20111005172528.0d0a8afc65acef7ace22a24e@canb.auug.org.au Signed-off-by: Ingo Molnar --- include/linux/llist.h | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'include/linux') diff --git a/include/linux/llist.h b/include/linux/llist.h index 837fb4ae66fb..7287734e08d1 100644 --- a/include/linux/llist.h +++ b/include/linux/llist.h @@ -178,4 +178,10 @@ static inline struct llist_node *llist_del_all(struct llist_head *head) { return xchg(&head->first, NULL); } + +extern bool llist_add_batch(struct llist_node *new_first, + struct llist_node *new_last, + struct llist_head *head); +extern struct llist_node *llist_del_first(struct llist_head *head); + #endif /* LLIST_H */ -- cgit v1.2.3