Add kernel address sanitizer infrastructure.

Address sanitizer for kernel (kasan) is a dynamic memory error detector.

The main features of kasan is:
 - is based on compiler instrumentation (fast),
 - detects out of bounds for both writes and reads,
 - provides use after free detection,

This patch only adds infrastructure for kernel address sanitizer. It's not
available for use yet. The idea and some code was borrowed from [1].

This feature requires pretty fresh GCC (revision r211699 from 2014-06-16 or
latter).

Implementation details:
The main idea of KASAN is to use shadow memory to record whether each byte of memory
is safe to access or not, and use compiler's instrumentation to check the shadow memory
on each memory access.

Address sanitizer dedicates 1/8 of the low memory to the shadow memory and uses direct
mapping with a scale and offset to translate a memory address to its corresponding
shadow address.

Here is function to translate address to corresponding shadow address:

     unsigned long kasan_mem_to_shadow(unsigned long addr)
     {
                return ((addr - PAGE_OFFSET) >> KASAN_SHADOW_SCALE_SHIFT)
                             + kasan_shadow_start;
     }

where KASAN_SHADOW_SCALE_SHIFT = 3.

So for every 8 bytes of lowmemory there is one corresponding byte of shadow memory.
The following encoding used for each shadow byte: 0 means that all 8 bytes of the
corresponding memory region are valid for access; k (1 <= k <= 7) means that
the first k bytes are valid for access, and other (8 - k) bytes are not;
Any negative value indicates that the entire 8-bytes are unaccessible.
Different negative values used to distinguish between different kinds of
unaccessible memory (redzones, freed memory) (see mm/kasan/kasan.h).

To be able to detect accesses to bad memory we need a special compiler.
Such compiler inserts a specific function calls (__asan_load*(addr), __asan_store*(addr))
before each memory access of size 1, 2, 4, 8 or 16.

These functions check whether memory region is valid to access or not by checking
corresponding shadow memory. If access is not valid an error printed.

[1] https://code.google.com/p/address-sanitizer/wiki/AddressSanitizerForKernel

Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>
init: main: initialize kasan's shadow area on boot

This patch initializes shadow area after it was allocated by arch code.
All low memory marked as accessible except shadow area itself.
Later free_all_bootmem() will release pages to buddy allocator
and these pages will be marked as unaccessible, untill somebody
will allocate them.

Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>
x86: add kasan hooks fort memcpy/memmove/memset functions

Since functions memset, memmove, memcpy are written in assembly,
compiler can't instrument memory accesses inside them.

This patch replaces these functions with our own instrumented
functions (kasan_mem*) for CONFIG_KASAN = y

In rare circumstances you may need to use the original functions,
in such case put #undef KASAN_HOOKS before includes.

Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>
x86: boot: vdso: disable instrumentation for code not linked with kernel

To avoid build errors, compiler's instrumentation must be disabled
for code not linked with kernel image.

Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>
x86: don't instrument arch/x86/kernel/cpu/common.c

Instrumentation of this file causing troubles.

Change-Id: I80e2166b6634bd571b40d8dfdaa745926faafc25
Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>
x86: mm: init: allocate shadow memory for kasan

Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>
x86: Kconfig: enable kernel address sanitizer

Now everything in x86 code is ready for kasan. Enable it.

Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>
mm: page_alloc: add kasan hooks on alloc and free pathes

Add kernel address sanitizer hooks to mark allocated page's addresses
as accessible in corresponding shadow region.
Mark freed pages as unaccessible.

Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>
mm: Makefile: kasan: don't instrument slub.c and slab_common.c files

Code in slub.c and slab_common.c files could validly access to object's
redzones

Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>
mm: slub: share slab_err and object_err functions

Remove static and add function declarations to mm/slab.h so they
could be used by kernel address sanitizer.

Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>
mm: slub: kasan: disable kasan when touching unaccessible memory

Some code in slub could validly touch memory marked by kasan as unaccessible.
Even though slub.c doesn't instrumented, functions called in it are instrumented,
so to avoid false positive reports such places are protected by
kasan_disable_local()/kasan_enable_local() calls.

Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>
mm: slub: add kernel address sanitizer hooks to slub allocator

With this patch kasan will be able to catch bugs in memory allocated
by slub.
Allocated slab page, this whole page marked as unaccessible
in corresponding shadow memory.
On allocation of slub object requested allocation size marked as
accessible, and the rest of the object (including slub's metadata)
marked as redzone (unaccessible).

We also mark object as accessible if ksize was called for this object.
There is some places in kernel where ksize function is called to inquire
size of really allocated area. Such callers could validly access whole
allocated memory, so it should be marked as accessible by kasan_krealloc call.

Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>
arm: boot: compressed: disable kasan's instrumentation

To avoid build errors, compiler's instrumentation used for kernel
address sanitizer, must be disabled for code not linked with kernel.

Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>
arm: add kasan hooks fort memcpy/memmove/memset functions

Since functions memset, memmove, memcpy are written in assembly,
compiler can't instrument memory accesses inside them.

This patch replaces these functions with our own instrumented
functions (kasan_mem*) for CONFIG_KASAN = y

In rare circumstances you may need to use the original functions,
in such case put #undef KASAN_HOOKS before includes.

Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>
arm: mm: reserve shadow memory for kasan

Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>
arm: Kconfig: enable kernel address sanitizer

Now everything in x86 code is ready for kasan. Enable it.

Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>
fs: dcache: manually unpoison dname after allocation to shut up kasan's reports

We need to manually unpoison rounded up allocation size for dname
to avoid kasan's reports in __d_lookup_rcu.
__d_lookup_rcu may validly read a little beyound allocated size.

Reported-by: Dmitry Vyukov <dvyukov@google.com>
Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>
lib: add kmalloc_bug_test module

This is a test module doing varios nasty things like
out of bounds accesses, use after free. It is usefull for testing
kernel debugging features like kernel address sanitizer.

Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>
kmemleak: kasan: disable instrumentation for kmemleak

kmemleak scans all memory while searching for pointers to
objects. So function scan_block could validly access
kasan's shadow memory region while searching for pointer.

Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>
x86: die: add notification to oopses if kernel built with CONFIG_KASAN=y

Slightly refactor __die() function as well.

Signed-off-by: Andrey Ryabinin <a.ryabinin@samsung.com>