Re: KLSAN

[Dmitry Vyukov]

On Fri, Jun 12, 2020 at 5:09 PM Maxime Villard <m...@m00nbsd.net> wrote:
>
> Hi,
> I wanted to know if you had plans on possible KLSAN LLVM instrumentation
> to develop in order to detect kernel memory leaks automatically.
>
> I see this as an important need on both Linux and NetBSD. Memory leaks are
> the last class of bugs we don't have automatic detection for; some other
> subsystems exist, such as KMEMLEAK, but they have serious limitations.
>
> Some time ago I thought about an approach based on DFSan. On the compiler
> side:
> - A 1:1 shadow, where each 8 bytes of kernel memory is backed by 8 bytes
> of shadow.
> - Memory transfers / loads / stores go through dedicated __lsan_memcpy()
> and other functions, to transfer the shadow metadata (similar to MSan).
> - Args / returns are stored in a TLS obtained by a call to the
> __lsan_get_context_state() function (similar to MSan).
> On the kernel side:
> - The return value of kmem_alloc()/malloc()/etc is tagged in the shadow.
> The tag is basically just a pointer to a structure that contains a
> refcount to the allocated area.
> - The tag naturally gets propagated in the shadow via loads/stores/etc.
> - Given that each load/store/etc goes through __lsan_memcpy()/etc, the
> kernel has the opportunity to see when a pointer to mallocated memory
> gets overwritten (that is, when its tag gets overwritten).
> - When such a pointer gets overwritten, the kernel decrements the
> refcount pointed to by the tag of the to-be-overwritten pointer. If
> the refcount reaches zero, and the area is still allocated, we have a
> leak.
>
> Obviously, there would have to be some tricks on the LLVM side, to not
> have cases where a mallocated pointer has no tag but is in a register.
> But overall it seems like a good KLSAN basis to me.
>
> Dmitry, is KLSAN something your instrumentation team would be interested
> in considering? I would tend to see that as extremely beneficial to Linux
> and other OSes.
>
> I would be interested in working on that with other people.
>
> Regards,
> Maxime

+address-sanitizer

Hi Maxime,

We do not have any plans to work on something like this in the near
future (1 year at least).

For the Linux kernel we use KMEMLEAK to find leaks. While it has some
implementation issues, it works and finds real leaks and these
implementation issues seem to be fixable.

Regarding the approach you described, frankly it looks
over-complicated to me and I would expect a very long tail of various
corner and special cases, at least for the Linux kernel. E.g.
non-instrumented asm, unions, pointers with high/low bits used for
something else, various special execution contexts and context
switches, etc. I am not even sure it will be possible to get a fully
working implementation without false positives and crashes.
The memory scanning approach used by both LSAN and KMEMLEAK looks much
more simple and robust to me. I can imagine a compiler providing some
aid for that, like register/memory slot lifetime markers, some type
info, but all of that only fights false negatives, so I would consider
it as an optional addition only.