tick: Upstream fixes

 * Addresses the issue of timers being scheduled on offline CPUs.

tick: Don't invoke tick_nohz_stop_sched_tick() if the cpu is offline

commit 5b39939a4 (nohz: Move ts->idle_calls incrementation into strict
idle logic) moved code out of tick_nohz_stop_sched_tick() and missed
to bail out when the cpu is offline. That's causing subsequent
failures as an offline CPU is supposed to die and not to fiddle with
nohz magic.

Return false in can_stop_idle_tick() if the cpu is offline.

Reported-and-tested-by: Jiri Kosina <jkosina@suse.cz>
Reported-and-tested-by: Prarit Bhargava <prarit@redhat.com>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Tony Luck <tony.luck@intel.com>
Cc: x86@kernel.org
Link: http://lkml.kernel.org/r/alpine.LFD.2.02.1305132138160.2863@ionos
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

timers: Consolidate base->next_timer update

Another bunch of mindlessly copied code. All callers of
internal_add_timer() except the recascading code updates
base->next_timer.

Move this into internal_add_timer() and let the cascading code call
__internal_add_timer().

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Gilad Ben-Yossef <gilad@benyossef.com>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Link: http://lkml.kernel.org/r/20120525214819.189946224@linutronix.de

timers: Create detach_if_pending() and use it

Most callers of detach_timer() have the same pattern around
them. Check whether the timer is pending and eventually updating
base->next_timer.

Create detach_if_pending() and replace the duplicated code.

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Gilad Ben-Yossef <gilad@benyossef.com>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Link: http://lkml.kernel.org/r/20120525214819.131246037@linutronix.de

timers: Add accounting of non deferrable timers

The code in get_next_timer_interrupt() is suboptimal as it has to run
through the cascade to find the next expiring timer. On a completely
idle core we should only do that when there is an active timer
enqueued and base->next_timer does not give us a fast answer.

Add accounting of the active timers to the now consolidated
attach/detach code. I deliberately avoided sanity checks because the
code is fully symetric and any fiddling with timers w/o using the API
functions will lead to cute explosions anyway. ulong is big enough
even on 32bit and if we really run into the situation to have more
than 1<<32 timers enqueued there, then we are definitely not in a
state to go idle and run through that code.

This allows us to fix another shortcoming of get_next_timer_interrupt().

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Gilad Ben-Yossef <gilad@benyossef.com>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Link: http://lkml.kernel.org/r/20120525214819.236377028@linutronix.de

timers: Improve get_next_timer_interrupt()

Gilad reported at

 http://lkml.kernel.org/r/1336056962-10465-2-git-send-email-gilad@benyossef.com

"Current timer code fails to correctly return a value meaning that
 there is no future timer event, with the result that the timer keeps
 getting re-armed in HZ one shot mode even when we could turn it off,
 generating unneeded interrupts.

 What is happening is that when __next_timer_interrupt() wishes
 to return a value that signifies "there is no future timer
 event", it returns (base->timer_jiffies + NEXT_TIMER_MAX_DELTA).

 However, the code in tick_nohz_stop_sched_tick(), which called
 __next_timer_interrupt() via get_next_timer_interrupt(),
 compares the return value to (last_jiffies + NEXT_TIMER_MAX_DELTA)
 to see if the timer needs to be re-armed.

 base->timer_jiffies != last_jiffies and so tick_nohz_stop_sched_tick()
 interperts the return value as indication that there is a distant
 future event 12 days from now and programs the timer to fire next
 after KTIME_MAX nsecs instead of avoiding to arm it. This ends up
 causing a needless interrupt once every KTIME_MAX nsecs."

Fix this by using the new active timer accounting. This avoids scans
when no active timer is enqueued completely, so we don't have to rely
on base->timer_next and base->timer_jiffies anymore.

Change-Id: I874ee5e5f837a228cebf5e6a084baf520d33cd0f
Reported-by: Gilad Ben-Yossef <gilad@benyossef.com>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Link: http://lkml.kernel.org/r/20120525214819.317535385@linutronix.de
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
configure sgx header speed
vsprintf: optimize decimal conversion (again)

    This patch is based upon an original from Michal Nazarewicz.

    Previous code was using optimizations which were developed
    to work well even on narrow-word CPUs (by today's standards).
    But Linux runs only on 32-bit and wider CPUs. We can use that.

    First: using 32x32->64 multiply and trivial 32-bit shift,
    we can correctly divide by 10 much larger numbers, and thus
    we can print groups of 9 digits instead of groups of 5 digits.

    Next: there are two algorithms to print larger numbers.
    One is generic: divide by 1000000000 and repeatedly print
    groups of (up to) 9 digits. It's conceptually simple,
    but requires an (unsigned long long) / 1000000000 division.
    Second algorithm splits 64-bit unsigned long long into 16-bit chunks,
    manipulates them cleverly and generates groups of 4 decimal digits.
    It so happens that it does NOT require long long division.

    If long is > 32 bits, division of 64-bit values is relatively easy,
    and we will use the first algorithm.
    If long long is > 64 bits (strange architecture with VERY large long long),
    second algorithm can't be used, and we again use the first one.
    Else (if long is 32 bits and long long is 64 bits) we use second one.

    And third: there is a simple optimization which takes fast path
    not only for zero as was done before, but for all one-digit numbers.

    In all tested cases new code is faster than old one, in many cases by 30%,
    in few cases by more than 50% (for example, on x86-32, conversion of 12345678).
    Code growth is ~0 in 32-bit case and ~130 bytes in 64-bit case.

    Signed-off-by: Michal Nazarewicz <mina86@mina86.com>
    Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
    Cc: Douglas W Jones <jones@cs.uiowa.edu>a
    backported from Linux 3.4+ to Linux 3.0 by faux123

Conflicts:
	lib/vsprintf.c
f2fs: add superblock and major in-memory structure

This adds the following major in-memory structures in f2fs.

- f2fs_sb_info:
  contains f2fs-specific information, two special inode pointers for node and
  meta address spaces, and orphan inode management.

- f2fs_inode_info:
  contains vfs_inode and other fs-specific information.

- f2fs_nm_info:
  contains node manager information such as NAT entry cache, free nid list,
  and NAT page management.

- f2fs_node_info:
  represents a node as node id, inode number, block address, and its version.

- f2fs_sm_info:
  contains segment manager information such as SIT entry cache, free segment
  map, current active logs, dirty segment management, and segment utilization.
  The specific structures are sit_info, free_segmap_info, dirty_seglist_info,
  curseg_info.

In addition, add F2FS_SUPER_MAGIC in magic.h.

Signed-off-by: Chul Lee <chur.lee@samsung.com>
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>

Conflicts:
	include/uapi/linux/magic.h

Change-Id: I58ce75d143c5c706ec6eef9b51ef2dc76af6b0ec
f2fs: add super block operations

This adds the implementation of superblock operations for f2fs, which includes
- init_f2fs_fs/exit_f2fs_fs
- f2fs_mount
- super_operations of f2fs

Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
f2fs: add checkpoint operations

This adds functions required by the checkpoint operations.

Basically, f2fs adopts a roll-back model with checkpoint blocks written in the
CP area. The checkpoint procedure includes as follows.

- write_checkpoint()
1. block_operations() freezes VFS calls.
2. submit cached bios.
3. flush_nat_entries() writes NAT pages updated by dirty NAT entries.
4. flush_sit_entries() writes SIT pages updated by dirty SIT entries.
5. do_checkpoint() writes,
  - checkpoint block (#0)
  - orphan inode blocks
  - summary blocks made by active logs
  - checkpoint block (copy of #0)
6. unblock_opeations()

In order to provide an address space for meta pages, f2fs_sb_info has a special
inode, namely meta_inode. This patch also adds the address space operations for
meta_inode.

Signed-off-by: Chul Lee <chur.lee@samsung.com>
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
f2fs: add node operations

This adds specific functions to manage NAT pages, a cache for NAT entries, free
nids, direct/indirect node blocks for indexing data, and address space for node
pages.

- The key information of an NAT entry consists of a node id and a block address.

- An NAT page is composed of block addresses covered by a certain range of NAT
  entries, which is maintained by the address space of meta_inode.

- A radix tree structure is used to cache NAT entries. The index for the tree
  is a node id.

- When there is no free nid, F2FS should scan NAT entries to find new one. In
  order to avoid scanning frequently, F2FS manages a list containing a number of
  free nids in memory. Only when free nids in the list are exhausted, scanning
  process, build_free_nids(), is triggered.

- F2FS has direct and indirect node blocks for indexing data. This patch adds
  fuctions related to the node block management such as getting, allocating, and
  truncating node blocks to index data.

- In order to cache node blocks in memory, F2FS has a node_inode with an address
  space for node pages. This patch also adds the address space operations for
  node_inode.

Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
f2fs: add segment operations

This adds specific functions not only to manage dirty/free segments, SIT pages,
a cache for SIT entries, and summary entries, but also to allocate free blocks
and write three types of pages: data, node, and meta.

- F2FS maintains three types of bitmaps in memory, which indicate free, prefree,
  and dirty segments respectively.

- The key information of an SIT entry consists of a segment number, the number
  of valid blocks in the segment, a bitmap to identify there-in valid or invalid
  blocks.

- An SIT page is composed of a certain range of SIT entries, which is maintained
  by the address space of meta_inode.

- To cache SIT entries, a simple array is used. The index for the array is the
  segment number.

- A summary entry for data contains the parent node information. A summary entry
  for node contains its node offset from the inode.

- F2FS manages information about six active logs and those summary entries in
  memory. Whenever one of them is changed, its summary entries are flushed to
  its SIT page maintained by the address space of meta_inode.

- This patch adds a default block allocation function which supports heap-based
  allocation policy.

- This patch adds core functions to write data, node, and meta pages. Since LFS
  basically produces a series of sequential writes, F2FS merges sequential bios
  with a single one as much as possible to reduce the IO scheduling overhead.

Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
f2fs: add file operations

This adds memory operations and file/file_inode operations.

- F2FS supports fallocate(), mmap(), fsync(), and basic ioctl().

Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
f2fs: add address space operations for data

This adds address space operations for data.

- F2FS supports readpages(), writepages(), and direct_IO().

- Because of out-of-place writes, f2fs_direct_IO() does not write data in place.

Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
f2fs: add core inode operations

This adds core functions to get, read, write, and evict an inode.

Signed-off-by: Changman Lee <cm224.lee@samsung.com>
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
f2fs: add inode operations for special inodes

This adds inode operations for directory, symlink, and special inodes.

Signed-off-by: Changman Lee <cm224.lee@samsung.com>
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
f2fs: add core directory operations

this adds core functions to find, add, delete, and link dentries.

Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
f2fs: add xattr and acl functionalities

This implements xattr and acl functionalities.

- F2FS uses a node page to contain use extended attributes.

Signed-off-by: Changman Lee <cm224.lee@samsung.com>
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
f2fs: add garbage collection functions

This adds on-demand and background cleaning functions.

- The basic background cleaning policy is trying to do cleaning jobs as much as
  possible whenever the system is idle. Once the background cleaning is done,
  the cleaner sleeps an amount of time not to interfere with VFS calls. The time
  is dynamically adjusted according to the status of whole segments, which is
  decreased when the following conditions are satisfied.

  . GC is not conducted currently, and
  . IO subsystem is idle by checking the number of requets in bdev's request
     list, and
  . There are enough dirty segments.

  Otherwise, the time is increased incrementally until to the maximum time.
  Note that, min and max times are 10 secs and 30 secs by default.

- F2FS adopts a default victim selection policy where background cleaning uses
  a cost-benefit algorithm, while on-demand cleaning uses a greedy algorithm.

- The method of moving data during the cleaning is slightly different between
  background and on-demand cleaning schemes. In the case of background cleaning,
  F2FS loads the data, and marks them as dirty. Then, F2FS expects that the data
  will be moved by flusher or VM. In the case of on-demand cleaning, F2FS should
  move the data right away.

- In order to identify valid blocks in a victim segment, F2FS scans the bitmap
  of the segment managed as an SIT entry.

Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
f2fs: add recovery routines for roll-forward

This adds roll-forward routines to recover fsynced data.

- F2FS uses basically roll-back model with checkpointing.

- In order to implement fsync(), there are two approaches as follows.

1. A roll-back model with checkpointing at every fsync()
 : This is a naive method, but suffers from very low performance.

2. A roll-forward model
 : F2FS adopts this model where all the fsynced data should be recovered, which
   were written after checkpointing was done. In order to figure out the data,
   F2FS keeps a "fsync" mark in direct node blocks. In addition, F2FS remains
   the location of next node block in each direct node block for reconstructing
   the chain of node blocks during the recovery.

- In order to enhance the performance, F2FS keeps a "dentry" mark also in direct
  node blocks. If this is set during the recovery, F2FS replays adding a dentry.

Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
f2fs: move proc files to debugfs

This moves all of the f2fs debugging files into debugfs. The files are
located in /sys/kernel/debug/f2fs/

Note, I think we are generating all of the same information in each of
the files for every unique f2fs filesystem in the machine.  This copies
the functionality that was present in the proc files, but this should be
fixed up in the future.

Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
[jaegeuk.kim@samsung.com: merged 3 debugfs entries into a *status* entry]
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
f2fs: update Kconfig and Makefile

This adds Makefile and Kconfig for f2fs, and updates Makefile and Kconfig files
in the fs directory.

Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>

Conflicts:
	fs/Makefile

Change-Id: I9ad9138c48c1131b0dfeca803f3a1ee3528d1fec
f2fs: add document

This adds a document describing the mount options, proc entries, usage, and
design of Flash-Friendly File System, namely F2FS.

Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
f2fs: add on-disk layout

This adds a header file describing the on-disk layout of f2fs.

Signed-off-by: Changman Lee <cm224.lee@samsung.com>
Signed-off-by: Chul Lee <chur.lee@samsung.com>
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>