lib, Add lock-less NULL terminated single list

 If there are multiple producers and multiple consumers, llist_add
 can be used in producers and llist_del_all can be used in
 consumers.  They can work simultaneously without lock.  But
 llist_del_first can not be used here.  Because llist_del_first
 depends on list->first->next does not changed if list->first is not
 changed during its operation, but llist_del_first, llist_add,
 llist_add (or llist_del_all, llist_add, llist_add) sequence in
 another consumer may violate that.

 If there are multiple producers and one consumer, llist_add can be
 used in producers and llist_del_all or llist_del_first can be used
 in the consumer.

 This can be summarized as follow:

           |   add    | del_first |  del_all
 add       |    -     |     -     |     -
 del_first |          |     L     |     L
 del_all   |          |           |     -

 Where "-" stands for no lock is needed, while "L" stands for lock
 is needed.

 The list entries deleted via llist_del_all can be traversed with
 traversing function such as llist_for_each etc.  But the list
 entries can not be traversed safely before deleted from the list.
 The order of deleted entries is from the newest to the oldest added
 one.  If you want to traverse from the oldest to the newest, you
 must reverse the order by yourself before traversing.

 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.

Conflicts:
	lib/Kconfig
	lib/Makefile
writeback: fix occasional slow sync(1)
In case when system contains no dirty pages, wakeup_flusher_threads() will
submit WB_SYNC_NONE writeback for 0 pages so wb_writeback() exits
immediately without doing anything, even though there are dirty inodes in
the system.  Thus sync(1) will write all the dirty inodes from a
WB_SYNC_ALL writeback pass which is slow.

Fix the problem by using get_nr_dirty_pages() in wakeup_flusher_threads()
instead of calculating number of dirty pages manually.  That function also
takes number of dirty inodes into account.

Change-Id: Ic90f80a31bb866b7628143b8b013871f83d05c13
Signed-off-by: Jan Kara <jack@suse.cz>
Reported-by: Paul Taysom <taysom@chromium.org>
Cc: Wu Fengguang <fengguang.wu@intel.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
writeback: fix writeback cache thrashing

From: Namjae Jeon <namjae.jeon@samsung.com>

Consider Process A: huge I/O on sda
        doing heavy write operation - dirty memory becomes more
        than dirty_background_ratio
        on HDD - flusher thread flush-8:0

Consider Process B: small I/O on sdb
        doing while [1]; read 1024K + rewrite 1024K + sleep 2sec
        on Flash device - flusher thread flush-8:16

As Process A is a heavy dirtier, dirty memory becomes more
than dirty_background_thresh. Due to this, below check becomes
true(checking global_page_state in over_bground_thresh)
for all bdi devices(even for very small dirtied bdi - sdb):

In this case, even small cached data on 'sdb' is forced to flush
and writeback cache thrashing happens.

When we added debug prints inside above 'if' condition and ran
above Process A(heavy dirtier on bdi with flush-8:0) and
Process B(1024K frequent read/rewrite on bdi with flush-8:16)
we got below prints:

[Test setup: ARM dual core CPU, 512 MB RAM]

[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE =  56064 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE =  56704 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE = 84720 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE = 94720 KB
[over_bground_thresh]: wakeup flush-8:16 : BDI_RECLAIMABLE =   384 KB
[over_bground_thresh]: wakeup flush-8:16 : BDI_RECLAIMABLE =   960 KB
[over_bground_thresh]: wakeup flush-8:16 : BDI_RECLAIMABLE =    64 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE = 92160 KB
[over_bground_thresh]: wakeup flush-8:16 : BDI_RECLAIMABLE =   256 KB
[over_bground_thresh]: wakeup flush-8:16 : BDI_RECLAIMABLE =   768 KB
[over_bground_thresh]: wakeup flush-8:16 : BDI_RECLAIMABLE =    64 KB
[over_bground_thresh]: wakeup flush-8:16 : BDI_RECLAIMABLE =   256 KB
[over_bground_thresh]: wakeup flush-8:16 : BDI_RECLAIMABLE =   320 KB
[over_bground_thresh]: wakeup flush-8:16 : BDI_RECLAIMABLE =     0 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE = 92032 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE = 91968 KB
[over_bground_thresh]: wakeup flush-8:16 : BDI_RECLAIMABLE =   192 KB
[over_bground_thresh]: wakeup flush-8:16 : BDI_RECLAIMABLE =  1024 KB
[over_bground_thresh]: wakeup flush-8:16 : BDI_RECLAIMABLE =    64 KB
[over_bground_thresh]: wakeup flush-8:16 : BDI_RECLAIMABLE =   192 KB
[over_bground_thresh]: wakeup flush-8:16 : BDI_RECLAIMABLE =   576 KB
[over_bground_thresh]: wakeup flush-8:16 : BDI_RECLAIMABLE =     0 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE = 84352 KB
[over_bground_thresh]: wakeup flush-8:16 : BDI_RECLAIMABLE =   192 KB
[over_bground_thresh]: wakeup flush-8:16 : BDI_RECLAIMABLE =   512 KB
[over_bground_thresh]: wakeup flush-8:16 : BDI_RECLAIMABLE =     0 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE = 92608 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE = 92544 KB

As mentioned in above log, when global dirty memory > global background_thresh
small cached data is also forced to flush by flush-8:16.
If removing global background_thresh checking code, we can reduce cache
thrashing of frequently used small data.
And It will be great if we can reserve a portion of writeback cache using
min_ratio.

After applying patch:
$ echo 5 > /sys/block/sdb/bdi/min_ratio
$ cat /sys/block/sdb/bdi/min_ratio
5
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE =  56064 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE =  56704 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE =  84160 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE =  96960 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE =  94080 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE =  93120 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE =  93120 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE =  91520 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE =  89600 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE =  93696 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE =  93696 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE =  72960 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE =  90624 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE =  90624 KB
[over_bground_thresh]: wakeup flush-8:0 : BDI_RECLAIMABLE =  90688 KB

As mentioned in the above logs, once cache is reserved for Process B,
and patch is applied there is less writeback cache thrashing on sdb
by frequent forced writeback by flush-8:16 in over_bground_thresh.

After all, small cached data will be flushed by periodic writeback
once every dirty_writeback_interval.

Change-Id: I678b30a5a28ed99bed0e782e38926ba4626b86ee
Suggested-by: Wanpeng Li <liwanp@linux.vnet.ibm.com>
Signed-off-by: Namjae Jeon <namjae.jeon@samsung.com>
Signed-off-by: Vivek Trivedi <t.vivek@samsung.com>
Signed-off-by: Quallenauge <Hamsi2k@freenet.de>

Conflicts:
	fs/fs-writeback.c
timer: optimize apply_slack()

__fls(mask) is equivalent to find_last_bit(&mask, BITS_PER_LONG), but cheaper.
find_last_bit was showing up high on the list when I was profiling for stalls
on icache misses on a system with very small cache size (MIPS).

Signed-off-by: Felix Fietkau <nbd@openwrt.org>
Signed-off-by: edoko <r_data@naver.com>

Change-Id: I8a5021a2fb2936c00ffd456663a76cb1b23e3100
kswapd: reduce time spent in congestion_wait

By reducing the amount of time kswapd spends in
congestion_wait kswapd is able to free up more
memory in the background and therefore  reduce
the amount  of time spent in direct reclaim.

Change-Id: I46ebe577f8954d8ce9907430958fa0e53090979c
Signed-off-by: Liam Mark <lmark@codeaurora.org>
Signed-off-by: Greg Grisco <ggrisco@codeaurora.org>
Signed-off-by: Quallenauge <Hamsi2k@freenet.de>
kswapd: Introduce congestion_wait_kswapd

congestion_wait for kswapd is similar to congestion_wait, the vital
difference is that congestion_wait_kswapd uses schedule_timeout
instead of io_schedule_timeout (which can cause IO wait conditions,
due to nr_iowait usage).

Derived from: https://github.com/oppo-source/Find5-Kernel-Source-4.2/commit/c7b44a43a970b699ecd68655bd6f83a8fbb3d74d
Original author: huanggd @oppo-source

Change-Id: I08bbbdd49c8764a3180c0d7a9197d2b9c8112d81
Signed-off-by: Luis Cruz <ljc2491@gmail.com>
cpufreq: Fix broken uevents for cpufreq governor and cpu devices

cyanogens uevent commit when the governor changes was rendered
non-working since kitkat (or so) as the uevent filter function
caused events to be dropped. Now hook into cpufreq_core_init()
and cpufreq_add_dev_interface() to create our basic ksets for
cpufreq and cpu devices. Also, we don't need to set environmental
data, so clean it up a bit.

This commit requires a change in ueventd.rc that add rules for
several files of interest.

Inspired by http://review.cyanogenmod.org/#/c/61579/
cpufreq: interactive: add io_is_busy interface

compatibility fix included

Previously the idle time returned from get_cpu_idle_time_us included the
iowait time. So the iowait time was always calculated as idle time.

But now the idle time returned from get_cpu_idle_time_us does not include
the iowait time anymore because of below commit which cause the iowait time
always calculated as busy time:
    6beea0c nohz: Fix update_ts_time_stat idle accounting

Add the io_is_busy interface, as does the ondemand governor, and let the user
configure the iowait time as busy or idle through the io_is_busy sysfs
interface.

By default, io_is_busy is disabled.

[toddpoynor@google.com: minor updates]
Change-Id: If7d70ff864c43bc9c8d7fd7cfc66f930d339f9b4
Signed-off-by: Lianwei Wang <lian-wei.wang@motorola.com>
Signed-off-by: Todd Poynor <toddpoynor@google.com>
Signed-off-by: Dan Trifan <jimsth@gmail.com>

Signed-off-by: Dan Trifan <jimsth@gmail.com>

Conflicts:
	drivers/cpufreq/cpufreq_interactive.c
nohz: Fix update_ts_time_stat idle accounting

update_ts_time_stat currently updates idle time even if we are in
iowait loop at the moment. The only real users of the idle counter
(via get_cpu_idle_time_us) are CPU governors and they expect to get
cumulative time for both idle and iowait times.
The value (idle_sleeptime) is also printed to userspace by print_cpu
but it prints both idle and iowait times so the idle part is misleading.

Let's clean this up and fix update_ts_time_stat to account both counters
properly and update consumers of idle to consider iowait time as well.
If we do this we might use get_cpu_{idle,iowait}_time_us from other
contexts as well and we will get expected values.

Signed-off-by: Michal Hocko <mhocko@suse.cz>
Cc: Dave Jones <davej@redhat.com>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: Alexey Dobriyan <adobriyan@gmail.com>
Link: http://lkml.kernel.org/r/e9c909c221a8da402c4da07e4cd968c3218f8eb1.1314172057.git.mhocko@suse.cz
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Signed-off-by: Dan Trifan <jimsth@gmail.com>
drivers:cpufreq:interactive: hardcode tuntable values

Signed-off-by: Dan Trifan <jimsth@gmail.com>
cpufreq: interactive: fix race on cpufreq TRANSITION notifier

The cpufreq TRANSTION notifier callback does not check the
governor_enabled state on affected CPUS, which will case
kernel panic in update_load because the policy object maybe
NULL or invalid when governor_enabled is false.

Change-Id: Ie0f1718124f61e2f9b5da57abc6981ada5b83908
Signed-off-by: Lianwei Wang <a22439@motorola.com>
Signed-off-by: Dan Trifan <jimsth@gmail.com>
add ondemandplus governor

Signed-off-by: Dan Trifan <jimsth@gmail.com>

Conflicts:
	include/linux/cpufreq.h
ondemandplus: add and enable io_is_busy=2 option, adjust up_threshold and down_differential

Signed-off-by: Dan Trifan <jimsth@gmail.com>
ondemandplus governor: remove adaptive timer_rate logic

It is unlikely this gives any power savings and only
add some ugly code :)

Signed-off-by: Dan Trifan <jimsth@gmail.com>
cpufreq: added HYPER, Dynamic Interactive, Sakuractive governors
cpufreq: hotplug: don't synch threads on jiffies

cpufreq-hotplug was always designed to run as a single thread that takes
aggregate load of all CPUs into account.  As such there is no need to
synchronize multiple threads to execute at the same time.  This
sychronization mechanism also causes execution of the do_dbs_check function
to be somewhat erratically scheduled.  Removing it causes scheduling of this
function to reliably happen based soley on the supplied sampling_rate
parameter.

Change-Id: If0edc89996f0d5763502236b225835dd9f4ab3c9
Signed-off-by: Mike Turquette <mturquette@ti.com>
cpufreq_hotplug.c: Update to last Cylon Kernel
added adaptive governor

Conflicts:
	drivers/cpufreq/Kconfig
	drivers/cpufreq/Makefile

Conflicts:
	include/linux/cpufreq.h
 cpufreq: interactive: fix a wrong behavior of boostpulse freq and his…

…peed_freq. Also increased boosted time to 500ms and decreased hispeed_freq to 729MHz to make up for it.

Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>

Conflicts:
	drivers/cpufreq/cpufreq_interactive.c
cpufreq: interactive: Add a sampling_down_factor for max frequencies

Change min_sample_time to 100ms when running at max

Change-Id: Ia7e35b0625bedf20e7ef3a1f52e5828ffbfed93e
Signed-off-by: Rohit Gupta <rohgup@codeaurora.org>