vfs: fix bad hashing of dentries

Josef Bacik found a performance regression between 3.2 and 3.10 and
narrowed it down to commit bfcfaa77bdf0 ("vfs: use 'unsigned long'
accesses for dcache name comparison and hashing"). He reports:

 "The test case is essentially

      for (i = 0; i < 1000000; i++)
              mkdir("a$i");

  On xfs on a fio card this goes at about 20k dir/sec with 3.2, and 12k
  dir/sec with 3.10.  This is because we spend waaaaay more time in
  __d_lookup on 3.10 than in 3.2.

  The new hashing function for strings is suboptimal for <
  sizeof(unsigned long) string names (and hell even > sizeof(unsigned
  long) string names that I've tested).  I broke out the old hashing
  function and the new one into a userspace helper to get real numbers
  and this is what I'm getting:

      Old hash table had 1000000 entries, 0 dupes, 0 max dupes
      New hash table had 12628 entries, 987372 dupes, 900 max dupes
      We had 11400 buckets with a p50 of 30 dupes, p90 of 240 dupes, p99 of 567 dupes for the new hash

  My test does the hash, and then does the d_hash into a integer pointer
  array the same size as the dentry hash table on my system, and then
  just increments the value at the address we got to see how many
  entries we overlap with.

  As you can see the old hash function ended up with all 1 million
  entries in their own bucket, whereas the new one they are only
  distributed among ~12.5k buckets, which is why we're using so much
  more CPU in __d_lookup".

The reason for this hash regression is two-fold:

 - On 64-bit architectures the down-mixing of the original 64-bit
   word-at-a-time hash into the final 32-bit hash value is very
   simplistic and suboptimal, and just adds the two 32-bit parts
   together.

   In particular, because there is no bit shuffling and the mixing
   boundary is also a byte boundary, similar character patterns in the
   low and high word easily end up just canceling each other out.

 - the old byte-at-a-time hash mixed each byte into the final hash as it
   hashed the path component name, resulting in the low bits of the hash
   generally being a good source of hash data.  That is not true for the
   word-at-a-time case, and the hash data is distributed among all the
   bits.

The fix is the same in both cases: do a better job of mixing the bits up
and using as much of the hash data as possible.  We already have the
"hash_32|64()" functions to do that.

Reported-by: Josef Bacik <jbacik@fb.com>
Cc: Al Viro <viro@zeniv.linux.org.uk>
Cc: Christoph Hellwig <hch@infradead.org>
Cc: Chris Mason <clm@fb.com>
Cc: linux-fsdevel@vger.kernel.org
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
Signed-off-by: Stefanescu Cristian <howerkraft@gmail.com>
ext4: Speedup WB_SYNC_ALL pass called from sync(2)

When doing filesystem wide sync, there's no need to force transaction
commit (or synchronously write inode buffer) separately for each inode
because ext4_sync_fs() takes care of forcing commit at the end (VFS
takes care of flushing buffer cache, respectively). Most of the time
this slowness doesn't manifest because previous WB_SYNC_NONE writeback
doesn't leave much to write but when there are processes aggressively
creating new files and several filesystems to sync, the sync slowness
can be noticeable. In the following test script sync(1) takes around 6
minutes when there are two ext4 filesystems mounted on a standard SATA
drive. After this patch sync takes a couple of seconds so we have about
two orders of magnitude improvement.

      function run_writers
      {
        for (( i = 0; i < 10; i++ )); do
          mkdir $1/dir$i
          for (( j = 0; j < 40000; j++ )); do
            dd if=/dev/zero of=$1/dir$i/$j bs=4k count=4 &>/dev/null
          done &
        done
      }

      for dir in "$@"; do
        run_writers $dir
      done

      sleep 40
      time sync

Signed-off-by: Jan Kara <jack@suse.cz>
Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>
Signed-off-by: Stefanescu Cristian <howerkraft@gmail.com>
ext4: speed up truncate/unlink by not using bforget() unless needed

Do not iterate over data blocks scanning for bh's to forget as they're
never exist. This improves time taken by unlink / truncate syscall.
Tested by continuously truncating file that is being written by dd.
Another test is rm -rf of linux tree while tar unpacks it. With
ordered data mode condition unlikely(!tbh) was always met in
ext4_free_blocks. With journal data mode tbh was found only few times,
so optimisation is also possible.

Unlinking fallocated 60G file after doing sync && echo 3 >
/proc/sys/vm/drop_caches && time rm --help

X86 before (linux 3.6-rc4):
# time rm -f test1
real    0m2.710s
user    0m0.000s
sys     0m1.530s

X86 after:
# time rm -f test1
real    0m0.644s
user    0m0.003s
sys     0m0.060s

MIPS before (linux 2.6.37):
# time rm -f test1
real    0m 4.93s
user    0m 0.00s
sys     0m 4.61s

MIPS after:
# time rm -f test1
real    0m 0.16s
user    0m 0.00s
sys     0m 0.06s

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Andrey Sidorov <qrxd43@motorola.com>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
ext4: Add support for FIDTRIM, a best-effort ioctl for deep discard trim

* What
This provides an interface for issuing an FITRIM which uses the
secure discard instead of just a discard.
Only the eMMC command is "secure", and not how the FS uses it:
due to the fact that the FS might reassign a region somewhere else,
the original deleted data will not be affected by the "trim" which only
handles un-used regions.
So we'll just call it "deep discard", and note that this is a
"best effort" cleanup.

* Why
Once in a while, We want to be able to cleanup most of the unused blocks
after erasing a bunch of files.
We don't want to constantly secure-discard via a mount option.

From an eMMC spec perspective, it tells the device to really get rid of
all the data for the specified blocks and not just put them back into the
pool of free ones (unlike the normal TRIM). The eMMC spec says the
secure trim handling must make sure the data (and metadata) is not available
anymore. A simple TRIM doesn't clear the data, it just puts blocks in the
free pool.
JEDEC Standard No. 84-A441
  7.6.9 Secure Erase
  7.6.10 Secure Trim

From an FS perspective, it is acceptable to leave some data behind.
 - directory entries related to deleted files
 - databases entries related to deleted files
 - small-file data stored in inode extents
 - blocks held by the FS waiting to be re-used (mitigated by sync).
 - blocks reassigned by the FS prior to FIDTRIM.

Change-Id: I676a1404a80130d93930c84898360f2e6fb2f81e
Signed-off-by: Geremy Condra <gcondra@google.com>
Signed-off-by: JP Abgrall <jpa@google.com>
dio: Convert direct_IO to use iov_iter

Change the direct_IO aop to take an iov_iter argument rather than an iovec.
This will get passed down through most filesystems so that only the
__blockdev_direct_IO helper need be aware of whether user or kernel memory
is being passed to the function.

Signed-off-by: Dave Kleikamp <dave.kleikamp@oracle.com>
heavily backported for Mako from LKML reference

Signed-off-by: faux123 <reioux@gmail.com>
Signed-off-by: Stefanescu Cristian <howerkraft@gmail.com>

Conflicts:
	fs/gfs2/aops.c
sched/cpuidle: reduce IPI store. Backport upstream 3.16 scheduler updates

Signed-off-by: Paul Reioux <reioux@gmail.com>
Signed-off-by: Stefanescu Cristian <howerkraft@gmail.com>
sched/fair: Optimize find_busiest_queue()

Use for_each_cpu_and() and thereby avoid computing the capacity for
CPUs we know we're not interested in.

Reviewed-by: Paul Turner <pjt@google.com>
Reviewed-by: Preeti U Murthy <preeti@linux.vnet.ibm.com>
Signed-off-by: Peter Zijlstra <peterz@infradead.org>
Link: http://lkml.kernel.org/n/tip-lppceyv6kb3a19g8spmrn20b@git.kernel.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Paul Reioux <reioux@gmail.com>

backported for Linux 3.4

Signed-off-by: Stefanescu Cristian <howerkraft@gmail.com>

Conflicts:
	kernel/sched/fair.c

Signed-off-by: Stefanescu Cristian <howerkraft@gmail.com>
sched/fair: Optimize cgroup pick_next_task_fair()

Since commit 2f36825b1 ("sched: Next buddy hint on sleep and preempt
path") it is likely we pick a new task from the same cgroup, doing a put
and then set on all intermediate entities is a waste of time, so try to
avoid this.

Measured using:

  mount nodev /cgroup -t cgroup -o cpu
  cd /cgroup
  mkdir a; cd a
  mkdir b; cd b
  mkdir c; cd c
  echo $$ > tasks
  perf stat --repeat 10 -- taskset 1 perf bench sched pipe

PRE :      4.542422684 seconds time elapsed   ( +-  0.33% )
POST:      4.389409991 seconds time elapsed   ( +-  0.32% )

Which shows a significant improvement of ~3.5%

Signed-off-by: Peter Zijlstra <peterz@infradead.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Tejun Heo <tj@kernel.org>
Link: http://lkml.kernel.org/r/1328936700.2476.17.camel@laptop
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Paul Reioux <reioux@gmail.com>

Backported for Linux 3.4 kernel

Signed-off-by: Stefanescu Cristian <howerkraft@gmail.com>

Conflicts:
	kernel/sched/fair.c

Signed-off-by: Stefanescu Cristian <howerkraft@gmail.com>
sched/fair: Fix unlocked reads of some cfs_b->quota/period

sched_cfs_period_timer() reads cfs_b->period without locks before calling
do_sched_cfs_period_timer(), and similarly unthrottle_offline_cfs_rqs()
would read cfs_b->period without the right lock. Thus a simultaneous
change of bandwidth could cause corruption on any platform where ktime_t
or u64 writes/reads are not atomic.

Extend cfs_b->lock from do_sched_cfs_period_timer() to include the read of
cfs_b->period to solve that issue; unthrottle_offline_cfs_rqs() can just
use 1 rather than the exact quota, much like distribute_cfs_runtime()
does.

There is also an unlocked read of cfs_b->runtime_expires, but a race
there would only delay runtime expiry by a tick. Still, the comparison
should just be != anyway, which clarifies even that problem.

Signed-off-by: Ben Segall <bsegall@google.com>
Tested-by: Roman Gushchin <klamm@yandex-team.ru>
[peterz: Fix compile warn]
Signed-off-by: Peter Zijlstra <peterz@infradead.org>
Cc: pjt@google.com
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
msm: kgsl: Add CMA memory feature to support NOMMU for GPU

Reserves CMA memory for kgsl driver early during bootup and then
uses dma_alloc_coherent() to allocate physically contiguous memory
instead of using the MMU

Change-Id: Ica9b244fe9b9d8a902d670293a0bec2edf81bd5d
Signed-off-by: Shrenuj Bansal <shrenujb@codeaurora.org>
Signed-off-by: Stefanescu Cristian <howerkraft@gmail.com>

Conflicts:
	drivers/gpu/msm/kgsl_sharedmem.c
msm: kgsl: Use a constant mask for the memops vmflags

We don't need to define a function to return a constant.  Save
ourselves some source code and some .text space too.

Change-Id: Ic0dedbadc72c2fdd473cd4369ed772c84a923a15
Signed-off-by: Jordan Crouse <jcrouse@codeaurora.org>
Signed-off-by: Stefanescu Cristian <howerkraft@gmail.com>

Conflicts:
	drivers/gpu/msm/kgsl_sharedmem.c
msm: kgsl: Don't set VM_IO on mmap()ed GPU memory objects

VM_IO prevents mapped memory from being peeked by ptrace(). That
kind of protection isn't really needed for nominal GPU buffers.
A process given itself up to ptrace() already expects to be
examined so there is no additional risk to let the parent examine
GPU buffers too.  This is done universally now, but there is no
reason why we wouldn't let the process choose which buffers to
keep private in the future.

That said; there is more of a concern about including GPU buffers
in a core dump since that is a more permanent and less secure
record of the memory so add VM_DONTDUMP for all GPU buffers to
protect against that.

CRs-Fixed: 654751
Change-Id: Ic0dedbade91a2ec458bcb27eff3312d4ec6e4389
Signed-off-by: Jordan Crouse <jcrouse@codeaurora.org>
Signed-off-by: Stefanescu Cristian <howerkraft@gmail.com>
msm: kgsl: Mark mmapped objects with VM_DONTCOPY

Add VM_DONTCOPY to the default set of mmap flags to keep VM objects
from being copied on fork() and causing issues.  KGSL file descriptors
copied to a child are not expected to be usable.

Change-Id: Ic0dedbad85c07118a931ccb9f7a6fd0507da3e5a
Signed-off-by: Jordan Crouse <jcrouse@codeaurora.org>
Signed-off-by: Stefanescu Cristian <howerkraft@gmail.com>
msm: kgsl: Fix Z180 memory leak

Decerement entry refcount, which incremented
in kgsl_sharedmem_find_region.

CRs-Fixed: 635747
Change-Id: I621ba8f8e119a9ab8ba5455b28a565e3cae2f7cd
Signed-off-by: Hareesh Gundu <hareeshg@codeaurora.org>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
msm: kgsl: Update calculation for graphics IOMMU context IDs

Calculate graphics IOMMU context IDs using the 'label' property of
the device tree node of that context. Context IDs are independent
of the register addresses of the SMMU device and its contexts, which
change for every target.

Change-Id: I16825d7248081997a442d4fb59ca5b04b88e33fd
Signed-off-by: Lokesh Batra <lbatra@codeaurora.org>
Signed-off-by: Lynus Vaz <lvaz@codeaurora.org>
Signed-off-by: Prabhat Awasthi <pawasthi@codeaurora.org>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
GPU: add optimization flags to GPU drivers

Signed-off-by: Lens-F <tnoah12@gmail.com>
Signed-off-by: flar2 <asegaert@gmail.com>
msm: kgsl: Add a flag to mark user mapped GPU buffers

Add a flag in /sys/kernel/debug/kgsl/kgsl-3do/proc/<pid>/mem
file to indicate for each GPU buffer if it is mapped to userspace
in <pid> or not.

CRs-fixed: 634962

Conflicts:

	drivers/gpu/msm/kgsl_debugfs.c

Change-Id: I8abda74ef5656aca6b1c0315af8deb77460fa5a9
Signed-off-by: Harsh Vardhan Dwivedi <hdwivedi@codeaurora.org>
Signed-off-by: Prabhat Awasthi <pawasthi@codeaurora.org>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
-Ofast

Conflicts:
	Makefile
msm: kgsl: Add a flag to mark user mapped GPU buffers

Add a flag in /sys/kernel/debug/kgsl/kgsl-3do/proc/<pid>/mem
file to indicate for each GPU buffer if it is mapped to userspace
in <pid> or not.

CRs-fixed: 634962
Change-Id: I8abda74ef5656aca6b1c0315af8deb77460fa5a9
Signed-off-by: Harsh Vardhan Dwivedi <hdwivedi@codeaurora.org>
Signed-off-by: Stefanescu Cristian <howerkraft@gmail.com>

Conflicts:
	drivers/gpu/msm/kgsl_debugfs.c

Signed-off-by: Stefanescu Cristian <howerkraft@gmail.com>