* Re: [PATCH v9] mm: support madvise(MADV_FREE)
From: Minchan Kim @ 2014-07-03 7:29 UTC (permalink / raw)
To: Kirill A. Shutemov
Cc: Andrew Morton, linux-kernel, linux-mm, Michael Kerrisk, Linux API,
Hugh Dickins, Johannes Weiner, Rik van Riel, KOSAKI Motohiro,
Mel Gorman, Jason Evans, Zhang Yanfei, Martin Schwidefsky,
Heiko Carstens, linux390, Gerald Schaefer
In-Reply-To: <20140703010318.GA2939@bbox>
Hello,
On Thu, Jul 03, 2014 at 10:03:19AM +0900, Minchan Kim wrote:
> Hello,
>
> On Tue, Jul 01, 2014 at 05:50:58PM +0300, Kirill A. Shutemov wrote:
> > On Tue, Jul 01, 2014 at 09:36:15AM +0900, Minchan Kim wrote:
> > > + do {
> > > + /*
> > > + * XXX: We can optimize with supporting Hugepage free
> > > + * if the range covers.
> > > + */
> > > + next = pmd_addr_end(addr, end);
> > > + if (pmd_trans_huge(*pmd))
> > > + split_huge_page_pmd(vma, addr, pmd);
> >
> > Could you implement proper THP support before upstreaming the feature?
> > It shouldn't be a big deal.
>
> Okay, Hope to review.
>
> Thanks for the feedback!
>
I tried to implement it but had a issue.
I need pmd_mkold, pmd_mkclean for MADV_FREE operation and pmd_dirty for
page_referenced. When I investigate all of arches supported THP,
it's not a big deal but s390 is not sure to me who has no idea of
soft tracking of s390 by storage key instead of page table information.
Cced s390 maintainer. Hope to help.
So, if there isn't any help from s390, I should introduce
HAVE_ARCH_THP_MADVFREE to disable MADV_FREE support of THP in s390 but
not want to introduce such new config.
At least, jemalloc case, it's hard to play with THP because it has
some metadata in the head of chunk so normally it doesn't free 2M
entirely. I guess other allocator works with similar approach
so not sure it's worth in this stage.
Do you have any workload to use MADV_FREE with THP?
so do you really want to support THP MADV_FREE now?
--
Kind regards,
Minchan Kim
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply
* Re: [PATCH RFC net-next 03/14] bpf: introduce syscall(BPF, ...) and BPF maps
From: Alexei Starovoitov @ 2014-07-03 2:29 UTC (permalink / raw)
To: Andy Lutomirski
Cc: David S. Miller, Ingo Molnar, Linus Torvalds, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Arnaldo Carvalho de Melo, Jiri Olsa, Thomas Gleixner,
H. Peter Anvin, Andrew Morton, Kees Cook, Linux API,
Network Development, linux-kernel@vger.kernel.org
In-Reply-To: <CALCETrW5WitpzcFmkGDwR6U=qOwCkOfQMy=XOtQTuHs-942Drw@mail.gmail.com>
On Wed, Jul 2, 2014 at 6:43 PM, Andy Lutomirski <luto@amacapital.net> wrote:
> On Tue, Jul 1, 2014 at 10:33 PM, Alexei Starovoitov <ast@plumgrid.com> wrote:
>> I want to avoid string names, since they will force new 'strtab', 'symtab'
>> sections in the programs/maps and will uglify the user interface quite a bit.
>
> To be fair, you really need to imitate ELF here. A very simple
> relocation-like table should do the trick.
simple.. right :) I do see the amount of struggle you have with
binutils and vdso.
I really don't want to add relocation unless this is last resort.
Especially since it can be solved without it.
I don't think I explained it enough in my last email… trying again:
>> Back in september one loadable unit was: one eBPF program + set of maps,
>> but tracing requirements forced a change, since multiple programs need
>> to access the same map and maps may need to be pre-populated before
>> the programs start executing, so I've split maps and programs into mostly
>> independent entities, but programs still need to think of maps as local:
>> For example I want to do a skb leak check 'tracing filter':
>> - attach this program to kretprobe of __alloc_skb():
>> u64 key = (u64) skb;
>> u64 value = bpf_get_time();
>> bpf_update_map_elem(1/*const_map_id*/, &key, &value);
>> - attach this program to consume_skb and kfree_skb tracepoints:
>> u64 key = (u64) skb;
>> bpf_delete_map_elem(1/*const_map_id*/, &key);
>> - and have user space do:
>> prior to loading:
>> bpf_create_map(1/*map_id*/, 8/*key_size*/, 8/*value*/, 1M /*max_entries*/)
>> and then periodically iterate the map to see whether any skb stayed
>> in the map for too long.
>>
>> Programs need to be written with hard coded map_ids otherwise usability
>> suffers, so I did global 32-bit id in this RFC
>>, but this indeed doesn't work
>
> Really? That will mean that you have to edit the source of your
> filter program if the small integer map number you chose conflicts
> with another program. That sounds unpleasant.
unpleasant. exactly. that's why I'm proposing per-process local map-id,
so that programs don't need to be edited.
>> for unprivileged chrome browser unless programs are previously loaded
>> by root and chrome only does attach to seccomp.
>>
>> So here is the non-root bpf syscall interface I'm thinking about:
>>
>> ufd = bpf_create_map(map_id, key_size, value_size, max_entries);
>>
>> it will create a global map in the system which will be accessible
>> in this process via 'ufd'. Internally this 'ufd' will be assigned global map_id
>> and process-local map_id that was passed as a 1st argument.
>> To do update/lookup the process will use bpf_map_xxx_elem(ufd,…)
>>
>
> Erk. Unprivileged programs shouldn't be able to allocate global ids
> of their choosing, especially if privileged programs can also do it.
> Otherwise unprivileged programs can force a collision and possibly
> steal information.
of course. that's not what said.
>> Then to load eBPF program the process will do:
>> ufd = bpf_prog_load(prog_type, ebpf_insn_array, license)
>> and instructions will be referring to maps via local map_id that
>> was hard coded as part of the program.
>
> I think relocations would be must prettier than per-process map id tables.
I think per process map_id are much cleaner.
non-root API:
ufd = bpf_create_map(local_map_id,… )
bpf_map_update/delete/lookup_elem(ufd,…)
ufd = bpf_prog_load(insns)
close(ufd)
root only API:
global_id = bpf_get_id(ufd) // returns either map or prog global id
bpf_map_delete(global_map_id)
bpf_prog_unload(global_prog_id)
Details:
ufd = bpf_create_map(local_map_id, ...);
local_map_id - process local map_id
(this id is used to access maps from eBPF program loaded by this process)
ufd - process local file descriptor
(used to update/lookup maps from this process)
global_map_id = bpf_get_id(ufd)
this is root only call to get global_ids and pass them to global events
like tracing.
global ids will only be seen by root. There is no way for root or non-root
to influence id ranges.
>> Beyond the normal create_map, update/lookup/delete, load_prog
>> operations (that are accessible to both root and non-root), the root user
>> gains one more operations: bpf_get_global_id(ufd) that returns
>> global map_id or prog_id. This id can be attached to global events
>> like tracing. Non-root users lose ability to do delete_map and
>> unload_prog (they do close(ufd) instead), so this ops are for root
>> only and operate on global ids.
>> This is the cleanest way I could think of to combine non-root
>> security, per-process id and global id all in one API. Thoughts?
>
> I think I'm okay with this part, although an interface to get a map fd
> given some reference to the program (in sysfs) that uses it would also
> work and maybe be more straightforward.
If you meant debugfs, then yes. I'm planning to add a way for root
to see all loaded programs and maps (similar to /proc as lsmod does),
and then do bpf_map_delete/bpf_prog_unload (similar to rmmod)
setsockopt and seccomp will be non-root and programs will go
through additional dont_leak_pointers check in verifier.
tracing/dtrace will be for root only, since they would need to attach
to global events.
I think it will be cleaner once I finish fd conversion as a patch.
^ permalink raw reply
* Re: [PATCH 08/10] userfaultfd: add new syscall to provide memory externalization
From: Andy Lutomirski @ 2014-07-03 1:56 UTC (permalink / raw)
To: Andrea Arcangeli, qemu-devel, kvm, linux-mm, linux-kernel
Cc: "Dr. David Alan Gilbert", Johannes Weiner, Andrew Morton,
Android Kernel Team, Robert Love, Mel Gorman, Hugh Dickins,
Dave Hansen, Rik van Riel, Dmitry Adamushko, Neil Brown,
Mike Hommey, Taras Glek, Jan Kara, KOSAKI Motohiro,
Michel Lespinasse, Minchan Kim, Keith Packard, Huangpeng (Peter),
Isaku Yamahata, Linux API
In-Reply-To: <1404319816-30229-9-git-send-email-aarcange@redhat.com>
On 07/02/2014 09:50 AM, Andrea Arcangeli wrote:
> Once an userfaultfd is created MADV_USERFAULT regions talks through
> the userfaultfd protocol with the thread responsible for doing the
> memory externalization of the process.
>
> The protocol starts by userland writing the requested/preferred
> USERFAULT_PROTOCOL version into the userfault fd (64bit write), if
> kernel knows it, it will ack it by allowing userland to read 64bit
> from the userfault fd that will contain the same 64bit
> USERFAULT_PROTOCOL version that userland asked. Otherwise userfault
> will read __u64 value -1ULL (aka USERFAULTFD_UNKNOWN_PROTOCOL) and it
> will have to try again by writing an older protocol version if
> suitable for its usage too, and read it back again until it stops
> reading -1ULL. After that the userfaultfd protocol starts.
>
> The protocol consists in the userfault fd reads 64bit in size
> providing userland the fault addresses. After a userfault address has
> been read and the fault is resolved by userland, the application must
> write back 128bits in the form of [ start, end ] range (64bit each)
> that will tell the kernel such a range has been mapped. Multiple read
> userfaults can be resolved in a single range write. poll() can be used
> to know when there are new userfaults to read (POLLIN) and when there
> are threads waiting a wakeup through a range write (POLLOUT).
>
> Signed-off-by: Andrea Arcangeli <aarcange@redhat.com>
> +#ifdef CONFIG_PROC_FS
> +static int userfaultfd_show_fdinfo(struct seq_file *m, struct file *f)
> +{
> + struct userfaultfd_ctx *ctx = f->private_data;
> + int ret;
> + wait_queue_t *wq;
> + struct userfaultfd_wait_queue *uwq;
> + unsigned long pending = 0, total = 0;
> +
> + spin_lock(&ctx->fault_wqh.lock);
> + list_for_each_entry(wq, &ctx->fault_wqh.task_list, task_list) {
> + uwq = container_of(wq, struct userfaultfd_wait_queue, wq);
> + if (uwq->pending)
> + pending++;
> + total++;
> + }
> + spin_unlock(&ctx->fault_wqh.lock);
> +
> + ret = seq_printf(m, "pending:\t%lu\ntotal:\t%lu\n", pending, total);
This should show the protocol version, too.
> +
> +SYSCALL_DEFINE1(userfaultfd, int, flags)
> +{
> + int fd, error;
> + struct file *file;
This looks like it can't be used more than once in a process. That will
be unfortunate for libraries. Would it be feasible to either have
userfaultfd claim a range of addresses or for a vma to be explicitly
associated with a userfaultfd? (In the latter case, giant PROT_NONE
MAP_NORESERVE mappings could be used.)
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply
* Re: [PATCH 00/10] RFC: userfault
From: Andy Lutomirski @ 2014-07-03 1:51 UTC (permalink / raw)
To: Andrea Arcangeli, qemu-devel-qX2TKyscuCcdnm+yROfE0A,
kvm-u79uwXL29TY76Z2rM5mHXA, linux-mm-Bw31MaZKKs3YtjvyW6yDsg,
linux-kernel-u79uwXL29TY76Z2rM5mHXA
Cc: "Dr. David Alan Gilbert", Johannes Weiner, Andrew Morton,
Android Kernel Team, Robert Love, Mel Gorman, Hugh Dickins,
Dave Hansen, Rik van Riel, Dmitry Adamushko, Neil Brown,
Mike Hommey, Taras Glek, Jan Kara, KOSAKI Motohiro,
Michel Lespinasse, Minchan Kim, Keith Packard, Huangpeng (Peter),
Isaku Yamahata, Linux API
In-Reply-To: <1404319816-30229-1-git-send-email-aarcange-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
On 07/02/2014 09:50 AM, Andrea Arcangeli wrote:
> Hello everyone,
>
> There's a large CC list for this RFC because this adds two new
> syscalls (userfaultfd and remap_anon_pages) and
> MADV_USERFAULT/MADV_NOUSERFAULT, so suggestions on changes to the API
> or on a completely different API if somebody has better ideas are
> welcome now.
cc:linux-api -- this is certainly worthy of linux-api discussion.
>
> The combination of these features are what I would propose to
> implement postcopy live migration in qemu, and in general demand
> paging of remote memory, hosted in different cloud nodes.
>
> The MADV_USERFAULT feature should be generic enough that it can
> provide the userfaults to the Android volatile range feature too, on
> access of reclaimed volatile pages.
>
> If the access could ever happen in kernel context through syscalls
> (not not just from userland context), then userfaultfd has to be used
> to make the userfault unnoticeable to the syscall (no error will be
> returned). This latter feature is more advanced than what volatile
> ranges alone could do with SIGBUS so far (but it's optional, if the
> process doesn't call userfaultfd, the regular SIGBUS will fire, if the
> fd is closed SIGBUS will also fire for any blocked userfault that was
> waiting a userfaultfd_write ack).
>
> userfaultfd is also a generic enough feature, that it allows KVM to
> implement postcopy live migration without having to modify a single
> line of KVM kernel code. Guest async page faults, FOLL_NOWAIT and all
> other GUP features works just fine in combination with userfaults
> (userfaults trigger async page faults in the guest scheduler so those
> guest processes that aren't waiting for userfaults can keep running in
> the guest vcpus).
>
> remap_anon_pages is the syscall to use to resolve the userfaults (it's
> not mandatory, vmsplice will likely still be used in the case of local
> postcopy live migration just to upgrade the qemu binary, but
> remap_anon_pages is faster and ideal for transferring memory across
> the network, it's zerocopy and doesn't touch the vma: it only holds
> the mmap_sem for reading).
>
> The current behavior of remap_anon_pages is very strict to avoid any
> chance of memory corruption going unnoticed. mremap is not strict like
> that: if there's a synchronization bug it would drop the destination
> range silently resulting in subtle memory corruption for
> example. remap_anon_pages would return -EEXIST in that case. If there
> are holes in the source range remap_anon_pages will return -ENOENT.
>
> If remap_anon_pages is used always with 2M naturally aligned
> addresses, transparent hugepages will not be splitted. In there could
> be 4k (or any size) holes in the 2M (or any size) source range,
> remap_anon_pages should be used with the RAP_ALLOW_SRC_HOLES flag to
> relax some of its strict checks (-ENOENT won't be returned if
> RAP_ALLOW_SRC_HOLES is set, remap_anon_pages then will just behave as
> a noop on any hole in the source range). This flag is generally useful
> when implementing userfaults with THP granularity, but it shouldn't be
> set if doing the userfaults with PAGE_SIZE granularity if the
> developer wants to benefit from the strict -ENOENT behavior.
>
> The remap_anon_pages syscall API is not vectored, as I expect it to be
> used mainly for demand paging (where there can be just one faulting
> range per userfault) or for large ranges (with the THP model as an
> alternative to zapping re-dirtied pages with MADV_DONTNEED with 4k
> granularity before starting the guest in the destination node) where
> vectoring isn't going to provide much performance advantages (thanks
> to the THP coarser granularity).
>
> On the rmap side remap_anon_pages doesn't add much complexity: there's
> no need of nonlinear anon vmas to support it because I added the
> constraint that it will fail if the mapcount is more than 1. So in
> general the source range of remap_anon_pages should be marked
> MADV_DONTFORK to prevent any risk of failure if the process ever
> forks (like qemu can in some case).
>
> One part that hasn't been tested is the poll() syscall on the
> userfaultfd because the postcopy migration thread currently is more
> efficient waiting on blocking read()s (I'll write some code to test
> poll() too). I also appended below a patch to trinity to exercise
> remap_anon_pages and userfaultfd and it completes trinity
> successfully.
>
> The code can be found here:
>
> git clone --reference linux git://git.kernel.org/pub/scm/linux/kernel/git/andrea/aa.git -b userfault
>
> The branch is rebased so you can get updates for example with:
>
> git fetch && git checkout -f origin/userfault
>
> Comments welcome, thanks!
> Andrea
>
> From cbe940e13b4cead41e0f862b3abfa3814f235ec3 Mon Sep 17 00:00:00 2001
> From: Andrea Arcangeli <aarcange-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
> Date: Wed, 2 Jul 2014 18:32:35 +0200
> Subject: [PATCH] add remap_anon_pages and userfaultfd
>
> Signed-off-by: Andrea Arcangeli <aarcange-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
> ---
> include/syscalls-x86_64.h | 2 +
> syscalls/remap_anon_pages.c | 100 ++++++++++++++++++++++++++++++++++++++++++++
> syscalls/syscalls.h | 2 +
> syscalls/userfaultfd.c | 12 ++++++
> 4 files changed, 116 insertions(+)
> create mode 100644 syscalls/remap_anon_pages.c
> create mode 100644 syscalls/userfaultfd.c
>
> diff --git a/include/syscalls-x86_64.h b/include/syscalls-x86_64.h
> index e09df43..a5b3a88 100644
> --- a/include/syscalls-x86_64.h
> +++ b/include/syscalls-x86_64.h
> @@ -324,4 +324,6 @@ struct syscalltable syscalls_x86_64[] = {
> { .entry = &syscall_sched_setattr },
> { .entry = &syscall_sched_getattr },
> { .entry = &syscall_renameat2 },
> + { .entry = &syscall_remap_anon_pages },
> + { .entry = &syscall_userfaultfd },
> };
> diff --git a/syscalls/remap_anon_pages.c b/syscalls/remap_anon_pages.c
> new file mode 100644
> index 0000000..b1e9d3c
> --- /dev/null
> +++ b/syscalls/remap_anon_pages.c
> @@ -0,0 +1,100 @@
> +/*
> + * SYSCALL_DEFINE3(remap_anon_pages,
> + unsigned long, dst_start, unsigned long, src_start,
> + unsigned long, len)
> + */
> +#include <stdlib.h>
> +#include <asm/mman.h>
> +#include <assert.h>
> +#include "arch.h"
> +#include "maps.h"
> +#include "random.h"
> +#include "sanitise.h"
> +#include "shm.h"
> +#include "syscall.h"
> +#include "tables.h"
> +#include "trinity.h"
> +#include "utils.h"
> +
> +static const unsigned long alignments[] = {
> + 1 * MB, 2 * MB, 4 * MB, 8 * MB,
> + 10 * MB, 100 * MB,
> +};
> +
> +static unsigned char *g_src, *g_dst;
> +static unsigned long g_size;
> +static int g_check;
> +
> +#define RAP_ALLOW_SRC_HOLES (1UL<<0)
> +
> +static void sanitise_remap_anon_pages(struct syscallrecord *rec)
> +{
> + unsigned long size = alignments[rand() % ARRAY_SIZE(alignments)];
> + unsigned long max_rand;
> + if (rand_bool()) {
> + g_src = mmap(NULL, size, PROT_READ|PROT_WRITE,
> + MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
> + } else
> + g_src = MAP_FAILED;
> + if (rand_bool()) {
> + g_dst = mmap(NULL, size, PROT_READ|PROT_WRITE,
> + MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
> + } else
> + g_dst = MAP_FAILED;
> + g_size = size;
> + g_check = 1;
> +
> + rec->a1 = (unsigned long) g_dst;
> + rec->a2 = (unsigned long) g_src;
> + rec->a3 = g_size;
> + rec->a4 = 0;
> +
> + if (rand_bool())
> + max_rand = -1UL;
> + else
> + max_rand = g_size << 1;
> + if (rand_bool()) {
> + rec->a3 += (rand() % max_rand) - g_size;
> + g_check = 0;
> + }
> + if (rand_bool()) {
> + rec->a1 += (rand() % max_rand) - g_size;
> + g_check = 0;
> + }
> + if (rand_bool()) {
> + rec->a2 += (rand() % max_rand) - g_size;
> + g_check = 0;
> + }
> + if (rand_bool()) {
> + if (rand_bool()) {
> + rec->a4 = rand();
> + } else
> + rec->a4 = RAP_ALLOW_SRC_HOLES;
> + }
> + if (g_src != MAP_FAILED)
> + memset(g_src, 0xaa, size);
> +}
> +
> +static void post_remap_anon_pages(struct syscallrecord *rec)
> +{
> + if (g_check && !rec->retval) {
> + unsigned long size = g_size;
> + unsigned char *dst = g_dst;
> + while (size--)
> + assert(dst[size] == 0xaaU);
> + }
> + munmap(g_src, g_size);
> + munmap(g_dst, g_size);
> +}
> +
> +struct syscallentry syscall_remap_anon_pages = {
> + .name = "remap_anon_pages",
> + .num_args = 4,
> + .arg1name = "dst_start",
> + .arg2name = "src_start",
> + .arg3name = "len",
> + .arg4name = "flags",
> + .group = GROUP_VM,
> + .sanitise = sanitise_remap_anon_pages,
> + .post = post_remap_anon_pages,
> +};
> diff --git a/syscalls/syscalls.h b/syscalls/syscalls.h
> index 114500c..b8eaa63 100644
> --- a/syscalls/syscalls.h
> +++ b/syscalls/syscalls.h
> @@ -370,3 +370,5 @@ extern struct syscallentry syscall_sched_setattr;
> extern struct syscallentry syscall_sched_getattr;
> extern struct syscallentry syscall_renameat2;
> extern struct syscallentry syscall_kern_features;
> +extern struct syscallentry syscall_remap_anon_pages;
> +extern struct syscallentry syscall_userfaultfd;
> diff --git a/syscalls/userfaultfd.c b/syscalls/userfaultfd.c
> new file mode 100644
> index 0000000..769fe78
> --- /dev/null
> +++ b/syscalls/userfaultfd.c
> @@ -0,0 +1,12 @@
> +/*
> + * SYSCALL_DEFINE1(userfaultfd, int, flags)
> + */
> +#include "sanitise.h"
> +
> +struct syscallentry syscall_userfaultfd = {
> + .name = "userfaultfd",
> + .num_args = 1,
> + .arg1name = "flags",
> + .arg1type = ARG_LEN,
> + .rettype = RET_FD,
> +};
>
>
> Andrea Arcangeli (10):
> mm: madvise MADV_USERFAULT: prepare vm_flags to allow more than 32bits
> mm: madvise MADV_USERFAULT
> mm: PT lock: export double_pt_lock/unlock
> mm: rmap preparation for remap_anon_pages
> mm: swp_entry_swapcount
> mm: sys_remap_anon_pages
> waitqueue: add nr wake parameter to __wake_up_locked_key
> userfaultfd: add new syscall to provide memory externalization
> userfaultfd: make userfaultfd_write non blocking
> userfaultfd: use VM_FAULT_RETRY in handle_userfault()
>
> arch/alpha/include/uapi/asm/mman.h | 3 +
> arch/mips/include/uapi/asm/mman.h | 3 +
> arch/parisc/include/uapi/asm/mman.h | 3 +
> arch/x86/syscalls/syscall_32.tbl | 2 +
> arch/x86/syscalls/syscall_64.tbl | 2 +
> arch/xtensa/include/uapi/asm/mman.h | 3 +
> fs/Makefile | 1 +
> fs/proc/task_mmu.c | 5 +-
> fs/userfaultfd.c | 593 +++++++++++++++++++++++++++++++++
> include/linux/huge_mm.h | 11 +-
> include/linux/ksm.h | 4 +-
> include/linux/mm.h | 5 +
> include/linux/mm_types.h | 2 +-
> include/linux/swap.h | 6 +
> include/linux/syscalls.h | 5 +
> include/linux/userfaultfd.h | 42 +++
> include/linux/wait.h | 5 +-
> include/uapi/asm-generic/mman-common.h | 3 +
> init/Kconfig | 10 +
> kernel/sched/wait.c | 7 +-
> kernel/sys_ni.c | 2 +
> mm/fremap.c | 506 ++++++++++++++++++++++++++++
> mm/huge_memory.c | 209 ++++++++++--
> mm/ksm.c | 2 +-
> mm/madvise.c | 19 +-
> mm/memory.c | 14 +
> mm/mremap.c | 2 +-
> mm/rmap.c | 9 +
> mm/swapfile.c | 13 +
> net/sunrpc/sched.c | 2 +-
> 30 files changed, 1447 insertions(+), 46 deletions(-)
> create mode 100644 fs/userfaultfd.c
> create mode 100644 include/linux/userfaultfd.h
>
> --
> To unsubscribe, send a message with 'unsubscribe linux-mm' in
> the body to majordomo-Bw31MaZKKs0EbZ0PF+XxCw@public.gmane.org For more info on Linux MM,
> see: http://www.linux-mm.org/ .
> Don't email: <a href=mailto:"dont-Bw31MaZKKs3YtjvyW6yDsg@public.gmane.org"> email-Bw31MaZKKs3YtjvyW6yDsg@public.gmane.org </a>
>
^ permalink raw reply
* Re: [PATCH RFC net-next 03/14] bpf: introduce syscall(BPF, ...) and BPF maps
From: Andy Lutomirski @ 2014-07-03 1:43 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: David S. Miller, Ingo Molnar, Linus Torvalds, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Arnaldo Carvalho de Melo, Jiri Olsa, Thomas Gleixner,
H. Peter Anvin, Andrew Morton, Kees Cook, Linux API,
Network Development,
linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
In-Reply-To: <CAMEtUuzHrzyUG1nie5cWzGZYTDTnqL7vPvAmPZdie_uSM_wqRA-JsoAwUIsXosN+BqQ9rBEUg@public.gmane.org>
On Tue, Jul 1, 2014 at 10:33 PM, Alexei Starovoitov <ast-uqk4Ao+rVK5Wk0Htik3J/w@public.gmane.org> wrote:
> On Tue, Jul 1, 2014 at 8:11 AM, Andy Lutomirski <luto-kltTT9wpgjJwATOyAt5JVQ@public.gmane.org> wrote:
>> On Mon, Jun 30, 2014 at 10:47 PM, Alexei Starovoitov <ast@plumgrid.com> wrote:
>>> On Mon, Jun 30, 2014 at 3:09 PM, Andy Lutomirski <luto@amacapital.net> wrote:
>>>> On Sat, Jun 28, 2014 at 11:36 PM, Alexei Starovoitov <ast@plumgrid.com> wrote:
>>>>> On Sat, Jun 28, 2014 at 6:52 PM, Andy Lutomirski <luto@amacapital.net> wrote:
>>>>>> On Sat, Jun 28, 2014 at 1:49 PM, Alexei Starovoitov <ast@plumgrid.com> wrote:
>>>>>>>
>>>>>>> Sorry I don't like 'fd' direction at all.
>>>>>>> 1. it will make the whole thing very socket specific and 'net' dependent.
>>>>>>> but the goal here is to be able to use eBPF for tracing in embedded
>>>>>>> setups. So it's gotta be net independent.
>>>>>>> 2. sockets are already overloaded with all sorts of stuff. Adding more
>>>>>>> types of sockets will complicate it a lot.
>>>>>>> 3. and most important. read/write operations on sockets are not
>>>>>>> done every nanosecond, whereas lookup operations on bpf maps
>>>>>>> are done every dozen instructions, so we cannot have any overhead
>>>>>>> when accessing maps.
>>>>>>> In other words the verifier is done as static analyzer. I moved all
>>>>>>> the complexity to verify time, so at run-time the programs are as
>>>>>>> fast as possible. I'm strongly against run-time checks in critical path,
>>>>>>> since they kill performance and make the whole approach a lot less usable.
>>>>>>
>>>>>> I may have described my suggestion poorly. I'm suggesting that all of
>>>>>> these global ids be replaced *for userspace's benefit* with fds. That
>>>>>> is, a map would have an associated struct inode, and, when you load an
>>>>>> eBPF program, you'd pass fds into the kernel instead of global ids.
>>>>>> The kernel would still compile the eBPF program to use the global ids,
>>>>>> though.
>>>>>
>>>>> Hmm. If I understood you correctly, you're suggesting to do it similar
>>>>> to ipc/mqueue, shmem, sockets do. By registering and mounting
>>>>> a file system and providing all superblock and inode hooks… and
>>>>> probably have its own namespace type… hmm… may be. That's
>>>>> quite a bit of work to put lightly. As I said in the other email the first
>>>>> step is root only and all these complexity just not worth doing
>>>>> at this stage.
>>>>
>>>> The downside of not doing it right away is that it's harder to
>>>> retrofit in without breaking early users.
>>>>
>>>> You might be able to get away with using anon_inodes. That will
>>>
>>> Spent quite a bit of time playing with anon_inode_getfd(). The model
>>> works ok for seccomp, but doesn't seem to work for tracing,
>>> since tracepoints are global. Say, syscall(bpf, load_prog) returns
>>> a process-local fd. This 'fd' as a string can be written to
>>> debugfs/tracing/events/.../filter which will increment a refcnt of a global
>>> ebpf_program structure and will keep using it. When process exits it will
>>> close all fds which in case of ebpf_prog_fd should be a nop, since
>>> the program is still attached to a global event. Now we have a
>>> program and maps that still alive and dangling, since tracepoint events
>>> keep coming, but no new process can access it. Here we just lost all
>>> benefits of making it 'fd' based. Theoretically we can extend tracing to
>>> be fd-based too and tracepoints will auto-detach upon process exit,
>>> but that's not going to work for all other global events. Like networking
>>> components (bridge, ovs, …) are global and they won't be adding
>>> fd-based interfaces.
>>> I'm still thinking about it, but it looks like that any process-local
>>> ebpf_prog_id scheme is not going to work for global events. Thoughts?
>>
>> Hmm. Maybe these things do need global ids for tracing, or at least
>> there need to be some way to stash them somewhere and find them again.
>> I suppose that debugfs could have symlinks to them, but I don't know
>> how hard that would be to implement or how awkward it would be to use.
>>
>> I imagine there's some awkwardness regardless. For tracing, if I
>> create map 75 and eBPF program 492 that uses map 75, then I still need
>> to remember that map 75 is the map I want (or I need to parse the eBPF
>> program later on).
>>
>> How do you imagine the userspace code working? Maybe it would make
>> sense to add some nlattrs for eBPF programs to map between referenced
>> objects and nicknames for them. Then user code could look at
>> /sys/kernel/debug/whatever/nickname_of_map to resolve the map id or
>> even just open it directly.
>
> I want to avoid string names, since they will force new 'strtab', 'symtab'
> sections in the programs/maps and will uglify the user interface quite a bit.
To be fair, you really need to imitate ELF here. A very simple
relocation-like table should do the trick.
>
> Back in september one loadable unit was: one eBPF program + set of maps,
> but tracing requirements forced a change, since multiple programs need
> to access the same map and maps may need to be pre-populated before
> the programs start executing, so I've split maps and programs into mostly
> independent entities, but programs still need to think of maps as local:
> For example I want to do a skb leak check 'tracing filter':
> - attach this program to kretprobe of __alloc_skb():
> u64 key = (u64) skb;
> u64 value = bpf_get_time();
> bpf_update_map_elem(1/*const_map_id*/, &key, &value);
> - attach this program to consume_skb and kfree_skb tracepoints:
> u64 key = (u64) skb;
> bpf_delete_map_elem(1/*const_map_id*/, &key);
> - and have user space do:
> prior to loading:
> bpf_create_map(1/*map_id*/, 8/*key_size*/, 8/*value*/, 1M /*max_entries*/)
> and then periodically iterate the map to see whether any skb stayed
> in the map for too long.
>
> Programs need to be written with hard coded map_ids otherwise usability
> suffers, so I did global 32-bit id in this RFC
>, but this indeed doesn't work
Really? That will mean that you have to edit the source of your
filter program if the small integer map number you chose conflicts
with another program. That sounds unpleasant.
> for unprivileged chrome browser unless programs are previously loaded
> by root and chrome only does attach to seccomp.
>
> So here is the non-root bpf syscall interface I'm thinking about:
>
> ufd = bpf_create_map(map_id, key_size, value_size, max_entries);
>
> it will create a global map in the system which will be accessible
> in this process via 'ufd'. Internally this 'ufd' will be assigned global map_id
> and process-local map_id that was passed as a 1st argument.
> To do update/lookup the process will use bpf_map_xxx_elem(ufd,…)
>
Erk. Unprivileged programs shouldn't be able to allocate global ids
of their choosing, especially if privileged programs can also do it.
Otherwise unprivileged programs can force a collision and possibly
steal information.
> Then to load eBPF program the process will do:
> ufd = bpf_prog_load(prog_type, ebpf_insn_array, license)
> and instructions will be referring to maps via local map_id that
> was hard coded as part of the program.
I think relocations would be must prettier than per-process map id tables.
>
> Beyond the normal create_map, update/lookup/delete, load_prog
> operations (that are accessible to both root and non-root), the root user
> gains one more operations: bpf_get_global_id(ufd) that returns
> global map_id or prog_id. This id can be attached to global events
> like tracing. Non-root users lose ability to do delete_map and
> unload_prog (they do close(ufd) instead), so this ops are for root
> only and operate on global ids.
> This is the cleanest way I could think of to combine non-root
> security, per-process id and global id all in one API. Thoughts?
I think I'm okay with this part, although an interface to get a map fd
given some reference to the program (in sysfs) that uses it would also
work and maybe be more straightforward.
--Andy
^ permalink raw reply
* Re: [PATCH v9] mm: support madvise(MADV_FREE)
From: Minchan Kim @ 2014-07-03 1:03 UTC (permalink / raw)
To: Kirill A. Shutemov
Cc: Andrew Morton, linux-kernel-u79uwXL29TY76Z2rM5mHXA,
linux-mm-Bw31MaZKKs3YtjvyW6yDsg, Michael Kerrisk, Linux API,
Hugh Dickins, Johannes Weiner, Rik van Riel, KOSAKI Motohiro,
Mel Gorman, Jason Evans, Zhang Yanfei
In-Reply-To: <20140701145058.GA2084-nhfs4B5ZimeFUdmeq17FyvUpdFzICT1y@public.gmane.org>
Hello,
On Tue, Jul 01, 2014 at 05:50:58PM +0300, Kirill A. Shutemov wrote:
> On Tue, Jul 01, 2014 at 09:36:15AM +0900, Minchan Kim wrote:
> > + do {
> > + /*
> > + * XXX: We can optimize with supporting Hugepage free
> > + * if the range covers.
> > + */
> > + next = pmd_addr_end(addr, end);
> > + if (pmd_trans_huge(*pmd))
> > + split_huge_page_pmd(vma, addr, pmd);
>
> Could you implement proper THP support before upstreaming the feature?
> It shouldn't be a big deal.
Okay, Hope to review.
Thanks for the feedback!
--
Kind regards,
Minchan Kim
^ permalink raw reply
* Re: [PATCH RFC net-next 08/14] bpf: add eBPF verifier
From: Alexei Starovoitov @ 2014-07-03 0:01 UTC (permalink / raw)
To: Chema Gonzalez
Cc: David S. Miller, Ingo Molnar, Linus Torvalds, Steven Rostedt,
Daniel Borkmann, Eric Dumazet, Peter Zijlstra,
Arnaldo Carvalho de Melo, Jiri Olsa, Thomas Gleixner,
H. Peter Anvin, Andrew Morton, Kees Cook, Linux API,
Network Development, LKML
In-Reply-To: <CA+ZOOTM9KkOYJ5Nf25_x1fT+f76xMsdJRkqjYaABiNK9y3FNXA-JsoAwUIsXosN+BqQ9rBEUg@public.gmane.org>
On Wed, Jul 2, 2014 at 4:35 PM, Chema Gonzalez <chema-hpIqsD4AKlfQT0dZR+AlfA@public.gmane.org> wrote:
> On Wed, Jul 2, 2014 at 4:04 PM, Alexei Starovoitov <ast-uqk4Ao+rVK5Wk0Htik3J/w@public.gmane.org> wrote:
>>>> + reg = regs + BPF_REG_1; /* 1st arg to a function */
>>>> + reg->ptr = PTR_TO_CTX;
>>> Wait, doesn't this depend on doing "BPF_MOV64_REG(BPF_REG_CTX,
>>> BPF_REG_ARG1)" (the bpf-to-ebpf prologue), which is only enforced on
>>> filters converted from bpf? In fact, shouldn't this set
>>> regs[BPF_REG_CTX] instead of regs[BPF_REG_1] ?
>>
>> nope. it's REG_1.
>> as you said r6=r1 is only emitted by converted classic filters.
>> Verifier will see this 'r6=r1' assignment and will copy the r1 type into r6.
> You're right. I read BPF_MOV64_REG() AT&T-syntax-style.
>
> BTW, check_stack_write() in kernel/bpf/verifier.c has a couple of
> assignments of a slot->ptr to 0 (instead of INVALID_PTR). I assume
> this is unintended.
yes. good catch. Will fix it.
Too bad C compiler silently casts integers to enums
^ permalink raw reply
* Re: [PATCH RFC net-next 08/14] bpf: add eBPF verifier
From: Chema Gonzalez @ 2014-07-02 23:35 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: David S. Miller, Ingo Molnar, Linus Torvalds, Steven Rostedt,
Daniel Borkmann, Eric Dumazet, Peter Zijlstra,
Arnaldo Carvalho de Melo, Jiri Olsa, Thomas Gleixner,
H. Peter Anvin, Andrew Morton, Kees Cook, Linux API,
Network Development, LKML
In-Reply-To: <CAMEtUuxfrAUDDQVGNsNV2PeDii-6LAwQCbB2XGEHTJDwkkvyWg@mail.gmail.com>
On Wed, Jul 2, 2014 at 4:04 PM, Alexei Starovoitov <ast@plumgrid.com> wrote:
>>> + reg = regs + BPF_REG_1; /* 1st arg to a function */
>>> + reg->ptr = PTR_TO_CTX;
>> Wait, doesn't this depend on doing "BPF_MOV64_REG(BPF_REG_CTX,
>> BPF_REG_ARG1)" (the bpf-to-ebpf prologue), which is only enforced on
>> filters converted from bpf? In fact, shouldn't this set
>> regs[BPF_REG_CTX] instead of regs[BPF_REG_1] ?
>
> nope. it's REG_1.
> as you said r6=r1 is only emitted by converted classic filters.
> Verifier will see this 'r6=r1' assignment and will copy the r1 type into r6.
You're right. I read BPF_MOV64_REG() AT&T-syntax-style.
BTW, check_stack_write() in kernel/bpf/verifier.c has a couple of
assignments of a slot->ptr to 0 (instead of INVALID_PTR). I assume
this is unintended.
-Chema
^ permalink raw reply
* Re: [PATCH RFC net-next 08/14] bpf: add eBPF verifier
From: Alexei Starovoitov @ 2014-07-02 23:04 UTC (permalink / raw)
To: Chema Gonzalez
Cc: David S. Miller, Ingo Molnar, Linus Torvalds, Steven Rostedt,
Daniel Borkmann, Eric Dumazet, Peter Zijlstra,
Arnaldo Carvalho de Melo, Jiri Olsa, Thomas Gleixner,
H. Peter Anvin, Andrew Morton, Kees Cook, Linux API,
Network Development, LKML
In-Reply-To: <CA+ZOOTODDPN=6SECq1uPPD7AGP1zgBJ+bfYaX9o3YhnaCTiHYQ-JsoAwUIsXosN+BqQ9rBEUg@public.gmane.org>
On Wed, Jul 2, 2014 at 3:22 PM, Chema Gonzalez <chema-hpIqsD4AKlfQT0dZR+AlfA@public.gmane.org> wrote:
>> + * - unreachable insns exist (shouldn't be a forest. program = one function)
> This seems to me an unnecessary style restriction on user code.
unreachable instructions to me is a ticking time bomb of potential exploits.
Definitely should be rejected.
>> +#define _(OP) ({ int ret = OP; if (ret < 0) return ret; })
> +1 to removing the _ macro. If you want to avoid the 3 lines (is there
> anything in the style guide against "if ((err=OP) < 0) ..." ?), at
assignment and function call inside 'if' ? I don't like such style.
> least use some meaningful macro name (DO_AND_CHECK, or something like
> that).
Try replacing _ with any other name and see how bad it will look.
I tried with MACRO_NAME and with 'if (err) goto' and with 'if (err) return',
before I converged on _ macro.
I think it's a hidden gem of this patch.
> Can you please add:
>
> + } else if (class == BPF_LD) {
> + if (BPF_MODE(insn->code) == BPF_ABS) {
> + pr_cont("(%02x) r0 = *(%s *)skb[%d]\n",
> + insn->code,
> + bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
> + insn->imm);
> + } else if (BPF_MODE(insn->code) == BPF_IND) {
> + pr_cont("(%02x) r0 = *(%s *)skb[r%d + %d]\n",
> + insn->code,
> + bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
> + insn->src_reg, insn->imm);
> + } else {
> + pr_cont("BUG_ld_%02x\n", insn->code);
> + return;
> + }
>
> Note that I'm hardcoding r0 (instead of using %d for insn->dst_reg)
> because that's how ebpf writes the instructions.
ohh yes. it's a copy paste error, since it was in a different file before.
Will definitely add. Thanks!
>> +static void init_reg_state(struct reg_state *regs)
>> +{
>> + struct reg_state *reg;
>> + int i;
>> +
>> + for (i = 0; i < MAX_BPF_REG; i++) {
>> + regs[i].ptr = INVALID_PTR;
>> + regs[i].read_ok = false;
>> + regs[i].imm = 0xbadbad;
>> + }
>> + reg = regs + BPF_REG_FP;
> Any reason you switching from the array syntax to the pointer one? I
> find "reg = regs[BPF_REG_FP];" more readable (and the one you chose in
> the loop).
in this function no particular reason. It felt a bit less verbose, but
I can make
the change.
>> + reg = regs + BPF_REG_1; /* 1st arg to a function */
>> + reg->ptr = PTR_TO_CTX;
> Wait, doesn't this depend on doing "BPF_MOV64_REG(BPF_REG_CTX,
> BPF_REG_ARG1)" (the bpf-to-ebpf prologue), which is only enforced on
> filters converted from bpf? In fact, shouldn't this set
> regs[BPF_REG_CTX] instead of regs[BPF_REG_1] ?
nope. it's REG_1.
as you said r6=r1 is only emitted by converted classic filters.
Verifier will see this 'r6=r1' assignment and will copy the r1 type into r6.
Thank you for review!
^ permalink raw reply
* Re: [PATCH RFC net-next 08/14] bpf: add eBPF verifier
From: Alexei Starovoitov @ 2014-07-02 22:43 UTC (permalink / raw)
To: David Laight
Cc: Daniel Borkmann, David S. Miller, Ingo Molnar, Linus Torvalds,
Steven Rostedt, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Arnaldo Carvalho de Melo, Jiri Olsa, Thomas Gleixner,
H. Peter Anvin, Andrew Morton, Kees Cook, Linux API,
Network Development, LKML
In-Reply-To: <063D6719AE5E284EB5DD2968C1650D6D1726B207-VkEWCZq2GCInGFn1LkZF6NBPR1lH4CV8@public.gmane.org>
On Wed, Jul 2, 2014 at 1:11 AM, David Laight <David.Laight-JxhZ9S5GRejQT0dZR+AlfA@public.gmane.org> wrote:
> From: Alexei Starovoitov
> ...
>> >> +#define _(OP) ({ int ret = OP; if (ret < 0) return ret; })
> ...
>> >> + _(get_map_info(env, map_id, &map));
>> >
>> > Nit: such macros should be removed, please.
>>
>> It may surely look unconventional, but alternative is to replace
>> every usage of _ macro with:
>> err =
>> if (err)
>> return err;
>>
>> and since this macro is used 38 times, it will add ~120 unnecessary
>> lines that will only make code much harder to follow.
>> I tried not using macro and results were not pleasing.
>
> The problem is that they are hidden control flow.
> As such they make flow analysis harder for the casual reader.
In the abstract context macros with gotos and returns are bad,
but in this case extra verbosity is the bigger evil.
Consider this piece of code:
#define _(OP) ({ int ret = OP; if (ret < 0) return ret; })
if (opcode == BPF_END || opcode == BPF_NEG) {
if (BPF_SRC(insn->code) != BPF_X)
return -EINVAL;
/* check src operand */
_(check_reg_arg(regs, insn->dst_reg, 1));
/* check dest operand */
_(check_reg_arg(regs, insn->dst_reg, 0));
} else if (opcode == BPF_MOV) {
if (BPF_SRC(insn->code) == BPF_X)
/* check src operand */
_(check_reg_arg(regs, insn->src_reg, 1));
/* check dest operand */
_(check_reg_arg(regs, insn->dst_reg, 0));
where casual reader can easily see what the purpose of the code
and what it's doing.
Now rewrite it without '_' macro:
if (opcode == BPF_END || opcode == BPF_NEG) {
if (BPF_SRC(insn->code) != BPF_X)
return -EINVAL;
/* check src operand */
err = check_reg_arg(regs, insn->dst_reg, 1);
if (err)
return err;
/* check dest operand */
err = check_reg_arg(regs, insn->dst_reg, 0);
if (err)
return err;
} else if (opcode == BPF_MOV) {
if (BPF_SRC(insn->code) == BPF_X) {
/* check src operand */
err = check_reg_arg(regs, insn->src_reg, 1);
if (err)
return err;
}
/* check dest operand */
err = check_reg_arg(regs, insn->dst_reg, 0);
if (err)
return err;
see how your eyes are now picking up endless control flow of
if conditions and returns, instead of focusing on the code itself.
It's much easier to understand the semantics when if (err) is out
of the way. Note that replacing _ with real name will ruin
the reading experience, since CAPITAL letters of the macro
will be screaming: "look at me", instead of letting reviewer
focus on the code.
I believe that this usage of _ as a macro specifically as defined,
would be a great addition to kernel coding style in general.
I don't want to see _ to be redefined differently.
^ permalink raw reply
* Re: [PATCH RFC net-next 08/14] bpf: add eBPF verifier
From: Chema Gonzalez @ 2014-07-02 22:22 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: David S. Miller, Ingo Molnar, Linus Torvalds, Steven Rostedt,
Daniel Borkmann, Eric Dumazet, Peter Zijlstra,
Arnaldo Carvalho de Melo, Jiri Olsa, Thomas Gleixner,
H. Peter Anvin, Andrew Morton, Kees Cook, linux-api,
Network Development, LKML
In-Reply-To: <1403913966-4927-9-git-send-email-ast@plumgrid.com>
I'm in the process of reading the code, and got some questions/comments.
-Chema
On Fri, Jun 27, 2014 at 5:06 PM, Alexei Starovoitov <ast@plumgrid.com> wrote:
> Safety of eBPF programs is statically determined by the verifier, which detects:
> - loops
> - out of range jumps
> - unreachable instructions
> - invalid instructions
> - uninitialized register access
> - uninitialized stack access
> - misaligned stack access
> - out of range stack access
> - invalid calling convention
>
> It checks that
> - R1-R5 registers statisfy function prototype
> - program terminates
> - BPF_LD_ABS|IND instructions are only used in socket filters
>
> It is configured with:
>
> - bool (*is_valid_access)(int off, int size, enum bpf_access_type type);
> that provides information to the verifer which fields of 'ctx'
> are accessible (remember 'ctx' is the first argument to eBPF program)
>
> - const struct bpf_func_proto *(*get_func_proto)(enum bpf_func_id func_id);
> reports argument types of kernel helper functions that eBPF program
> may call, so that verifier can checks that R1-R5 types match prototype
>
> More details in Documentation/networking/filter.txt
>
> Signed-off-by: Alexei Starovoitov <ast@plumgrid.com>
> ---
> Documentation/networking/filter.txt | 233 ++++++
> include/linux/bpf.h | 48 ++
> include/uapi/linux/bpf.h | 1 +
> kernel/bpf/Makefile | 2 +-
> kernel/bpf/syscall.c | 2 +-
> kernel/bpf/verifier.c | 1431 +++++++++++++++++++++++++++++++++++
> 6 files changed, 1715 insertions(+), 2 deletions(-)
> create mode 100644 kernel/bpf/verifier.c
>
> diff --git a/Documentation/networking/filter.txt b/Documentation/networking/filter.txt
> index e14e486f69cd..05fee8fcedf1 100644
> --- a/Documentation/networking/filter.txt
> +++ b/Documentation/networking/filter.txt
> @@ -995,6 +995,108 @@ BPF_XADD | BPF_DW | BPF_STX: lock xadd *(u64 *)(dst_reg + off16) += src_reg
> Where size is one of: BPF_B or BPF_H or BPF_W or BPF_DW. Note that 1 and
> 2 byte atomic increments are not supported.
>
> +eBPF verifier
> +-------------
> +The safety of the eBPF program is determined in two steps.
> +
> +First step does DAG check to disallow loops and other CFG validation.
> +In particular it will detect programs that have unreachable instructions.
> +(though classic BPF checker allows them)
> +
> +Second step starts from the first insn and descends all possible paths.
> +It simulates execution of every insn and observes the state change of
> +registers and stack.
> +
> +At the start of the program the register R1 contains a pointer to context
> +and has type PTR_TO_CTX.
> +If verifier sees an insn that does R2=R1, then R2 has now type
> +PTR_TO_CTX as well and can be used on the right hand side of expression.
> +If R1=PTR_TO_CTX and insn is R2=R1+R1, then R2=INVALID_PTR,
> +since addition of two valid pointers makes invalid pointer.
> +
> +If register was never written to, it's not readable:
> + bpf_mov R0 = R2
> + bpf_exit
> +will be rejected, since R2 is unreadable at the start of the program.
> +
> +After kernel function call, R1-R5 are reset to unreadable and
> +R0 has a return type of the function.
> +
> +Since R6-R9 are callee saved, their state is preserved across the call.
> + bpf_mov R6 = 1
> + bpf_call foo
> + bpf_mov R0 = R6
> + bpf_exit
> +is a correct program. If there was R1 instead of R6, it would have
> +been rejected.
> +
> +Classic BPF register X is mapped to eBPF register R7 inside sk_convert_filter(),
> +so that its state is preserved across calls.
> +
> +load/store instructions are allowed only with registers of valid types, which
> +are PTR_TO_CTX, PTR_TO_MAP, PTR_TO_STACK. They are bounds and alignment checked.
> +For example:
> + bpf_mov R1 = 1
> + bpf_mov R2 = 2
> + bpf_xadd *(u32 *)(R1 + 3) += R2
> + bpf_exit
> +will be rejected, since R1 doesn't have a valid pointer type at the time of
> +execution of instruction bpf_xadd.
> +
> +At the start R1 contains pointer to ctx and R1 type is PTR_TO_CTX.
> +ctx is generic. verifier is configured to known what context is for particular
> +class of bpf programs. For example, context == skb (for socket filters) and
> +ctx == seccomp_data for seccomp filters.
> +A callback is used to customize verifier to restrict eBPF program access to only
> +certain fields within ctx structure with specified size and alignment.
> +
> +For example, the following insn:
> + bpf_ld R0 = *(u32 *)(R6 + 8)
> +intends to load a word from address R6 + 8 and store it into R0
> +If R6=PTR_TO_CTX, via is_valid_access() callback the verifier will know
> +that offset 8 of size 4 bytes can be accessed for reading, otherwise
> +the verifier will reject the program.
> +If R6=PTR_TO_STACK, then access should be aligned and be within
> +stack bounds, which are [-MAX_BPF_STACK, 0). In this example offset is 8,
> +so it will fail verification, since it's out of bounds.
> +
> +The verifier will allow eBPF program to read data from stack only after
> +it wrote into it.
> +Classic BPF verifier does similar check with M[0-15] memory slots.
> +For example:
> + bpf_ld R0 = *(u32 *)(R10 - 4)
> + bpf_exit
> +is invalid program.
> +Though R10 is correct read-only register and has type PTR_TO_STACK
> +and R10 - 4 is within stack bounds, there were no stores into that location.
> +
> +Pointer register spill/fill is tracked as well, since four (R6-R9)
> +callee saved registers may not be enough for some programs.
> +
> +Allowed function calls are customized with bpf_verifier_ops->get_func_proto()
> +For example, skb_get_nlattr() function has the following definition:
> + struct bpf_func_proto proto = {RET_INTEGER, PTR_TO_CTX};
> +and eBPF verifier will check that this function is always called with first
> +argument being 'ctx'. In other words R1 must have type PTR_TO_CTX
> +at the time of bpf_call insn.
> +After the call register R0 will be set to readable state, so that
> +program can access it.
> +
> +Function calls is a main mechanism to extend functionality of eBPF programs.
> +Socket filters may let programs to call one set of functions, whereas tracing
> +filters may allow completely different set.
> +
> +If a function made accessible to eBPF program, it needs to be thought through
> +from security point of view. The verifier will guarantee that the function is
> +called with valid arguments.
> +
> +seccomp vs socket filters have different security restrictions for classic BPF.
> +Seccomp solves this by two stage verifier: classic BPF verifier is followed
> +by seccomp verifier. In case of eBPF one configurable verifier is shared for
> +all use cases.
> +
> +See details of eBPF verifier in kernel/bpf/verifier.c
> +
> eBPF maps
> ---------
> 'maps' is a generic storage of different types for sharing data between kernel
> @@ -1064,6 +1166,137 @@ size. It will not let programs pass junk values as 'key' and 'value' to
> bpf_map_*_elem() functions, so these functions (implemented in C inside kernel)
> can safely access the pointers in all cases.
>
> +Understanding eBPF verifier messages
> +------------------------------------
> +
> +The following are few examples of invalid eBPF programs and verifier error
> +messages as seen in the log:
> +
> +Program with unreachable instructions:
> +static struct sock_filter_int prog[] = {
> + BPF_EXIT_INSN(),
> + BPF_EXIT_INSN(),
> +};
> +Error:
> + unreachable insn 1
> +
> +Program that reads uninitialized register:
> + BPF_ALU64_REG(BPF_MOV, BPF_REG_0, BPF_REG_2),
> + BPF_EXIT_INSN(),
> +Error:
> + 0: (bf) r0 = r2
> + R2 !read_ok
> +
> +Program that doesn't initialize R0 before exiting:
> + BPF_ALU64_REG(BPF_MOV, BPF_REG_2, BPF_REG_1),
> + BPF_EXIT_INSN(),
> +Error:
> + 0: (bf) r2 = r1
> + 1: (95) exit
> + R0 !read_ok
> +
> +Program that accesses stack out of bounds:
> + BPF_ST_MEM(BPF_DW, BPF_REG_10, 8, 0),
> + BPF_EXIT_INSN(),
> +Error:
> + 0: (7a) *(u64 *)(r10 +8) = 0
> + invalid stack off=8 size=8
> +
> +Program that doesn't initialize stack before passing its address into function:
> + BPF_ALU64_REG(BPF_MOV, BPF_REG_2, BPF_REG_10),
> + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
> + BPF_ALU64_IMM(BPF_MOV, BPF_REG_1, 1),
> + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
> + BPF_EXIT_INSN(),
> +Error:
> + 0: (bf) r2 = r10
> + 1: (07) r2 += -8
> + 2: (b7) r1 = 1
> + 3: (85) call 1
> + invalid indirect read from stack off -8+0 size 8
> +
> +Program that uses invalid map_id=2 while calling to map_lookup_elem() function:
> + BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
> + BPF_ALU64_REG(BPF_MOV, BPF_REG_2, BPF_REG_10),
> + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
> + BPF_ALU64_IMM(BPF_MOV, BPF_REG_1, 2),
> + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
> + BPF_EXIT_INSN(),
> +Error:
> + 0: (7a) *(u64 *)(r10 -8) = 0
> + 1: (bf) r2 = r10
> + 2: (07) r2 += -8
> + 3: (b7) r1 = 2
> + 4: (85) call 1
> + invalid access to map_id=2
> +
> +Program that doesn't check return value of map_lookup_elem() before accessing
> +map element:
> + BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
> + BPF_ALU64_REG(BPF_MOV, BPF_REG_2, BPF_REG_10),
> + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
> + BPF_ALU64_IMM(BPF_MOV, BPF_REG_1, 1),
> + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
> + BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
> + BPF_EXIT_INSN(),
> +Error:
> + 0: (7a) *(u64 *)(r10 -8) = 0
> + 1: (bf) r2 = r10
> + 2: (07) r2 += -8
> + 3: (b7) r1 = 1
> + 4: (85) call 1
> + 5: (7a) *(u64 *)(r0 +0) = 0
> + R0 invalid mem access 'map_value_or_null'
> +
> +Program that correctly checks map_lookup_elem() returned value for NULL, but
> +accesses the memory with incorrect alignment:
> + BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
> + BPF_ALU64_REG(BPF_MOV, BPF_REG_2, BPF_REG_10),
> + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
> + BPF_ALU64_IMM(BPF_MOV, BPF_REG_1, 1),
> + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
> + BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
> + BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),
> + BPF_EXIT_INSN(),
> +Error:
> + 0: (7a) *(u64 *)(r10 -8) = 0
> + 1: (bf) r2 = r10
> + 2: (07) r2 += -8
> + 3: (b7) r1 = 1
> + 4: (85) call 1
> + 5: (15) if r0 == 0x0 goto pc+1
> + R0=map_value1 R10=fp
> + 6: (7a) *(u64 *)(r0 +4) = 0
> + misaligned access off 4 size 8
> +
> +Program that correctly checks map_lookup_elem() returned value for NULL and
> +accesses memory with correct alignment in one side of 'if' branch, but fails
> +to do so in the other side of 'if' branch:
> + BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
> + BPF_ALU64_REG(BPF_MOV, BPF_REG_2, BPF_REG_10),
> + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
> + BPF_ALU64_IMM(BPF_MOV, BPF_REG_1, 1),
> + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
> + BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
> + BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
> + BPF_EXIT_INSN(),
> + BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 1),
> + BPF_EXIT_INSN(),
> +Error:
> + 0: (7a) *(u64 *)(r10 -8) = 0
> + 1: (bf) r2 = r10
> + 2: (07) r2 += -8
> + 3: (b7) r1 = 1
> + 4: (85) call 1
> + 5: (15) if r0 == 0x0 goto pc+2
> + R0=map_value1 R10=fp
> + 6: (7a) *(u64 *)(r0 +0) = 0
> + 7: (95) exit
> +
> + from 5 to 8: R0=imm0 R10=fp
> + 8: (7a) *(u64 *)(r0 +0) = 1
> + R0 invalid mem access 'imm'
> +
> Testing
> -------
>
> diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> index 7bfcad87018e..67fd49eac904 100644
> --- a/include/linux/bpf.h
> +++ b/include/linux/bpf.h
> @@ -47,17 +47,63 @@ struct bpf_map_type_list {
> void bpf_register_map_type(struct bpf_map_type_list *tl);
> struct bpf_map *bpf_map_get(u32 map_id);
>
> +/* types of values:
> + * - stored in an eBPF register
> + * - passed into helper functions as an argument
> + * - returned from helper functions
> + */
> +enum bpf_reg_type {
> + INVALID_PTR, /* reg doesn't contain a valid pointer */
> + PTR_TO_CTX, /* reg points to bpf_context */
> + PTR_TO_MAP, /* reg points to map element value */
> + PTR_TO_MAP_CONDITIONAL, /* points to map element value or NULL */
> + PTR_TO_STACK, /* reg == frame_pointer */
> + PTR_TO_STACK_IMM, /* reg == frame_pointer + imm */
> + PTR_TO_STACK_IMM_MAP_KEY, /* pointer to stack used as map key */
> + PTR_TO_STACK_IMM_MAP_VALUE, /* pointer to stack used as map elem */
> + RET_INTEGER, /* function returns integer */
> + RET_VOID, /* function returns void */
> + CONST_ARG, /* function expects integer constant argument */
> + CONST_ARG_MAP_ID, /* int const argument that is used as map_id */
> + /* int const argument indicating number of bytes accessed from stack
> + * previous function argument must be ptr_to_stack_imm
> + */
> + CONST_ARG_STACK_IMM_SIZE,
> +};
> +
> /* eBPF function prototype used by verifier to allow BPF_CALLs from eBPF programs
> * to in-kernel helper functions and for adjusting imm32 field in BPF_CALL
> * instructions after verifying
> */
> struct bpf_func_proto {
> s32 func_off;
> + enum bpf_reg_type ret_type;
> + enum bpf_reg_type arg1_type;
> + enum bpf_reg_type arg2_type;
> + enum bpf_reg_type arg3_type;
> + enum bpf_reg_type arg4_type;
> + enum bpf_reg_type arg5_type;
> +};
> +
> +/* bpf_context is intentionally undefined structure. Pointer to bpf_context is
> + * the first argument to eBPF programs.
> + * For socket filters: 'struct bpf_context *' == 'struct sk_buff *'
> + */
> +struct bpf_context;
> +
> +enum bpf_access_type {
> + BPF_READ = 1,
> + BPF_WRITE = 2
> };
>
> struct bpf_verifier_ops {
> /* return eBPF function prototype for verification */
> const struct bpf_func_proto *(*get_func_proto)(enum bpf_func_id func_id);
> +
> + /* return true if 'size' wide access at offset 'off' within bpf_context
> + * with 'type' (read or write) is allowed
> + */
> + bool (*is_valid_access)(int off, int size, enum bpf_access_type type);
> };
>
> struct bpf_prog_type_list {
> @@ -78,5 +124,7 @@ struct bpf_prog_info {
>
> void free_bpf_prog_info(struct bpf_prog_info *info);
> struct sk_filter *bpf_prog_get(u32 prog_id);
> +/* verify correctness of eBPF program */
> +int bpf_check(struct sk_filter *fp);
>
> #endif /* _LINUX_BPF_H */
> diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
> index ed067e245099..597a35cc101d 100644
> --- a/include/uapi/linux/bpf.h
> +++ b/include/uapi/linux/bpf.h
> @@ -381,6 +381,7 @@ enum bpf_prog_attributes {
>
> enum bpf_prog_type {
> BPF_PROG_TYPE_UNSPEC,
> + BPF_PROG_TYPE_SOCKET_FILTER,
> };
>
> /* integer value in 'imm' field of BPF_CALL instruction selects which helper
> diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile
> index 558e12712ebc..95a9035e0f29 100644
> --- a/kernel/bpf/Makefile
> +++ b/kernel/bpf/Makefile
> @@ -1 +1 @@
> -obj-y := core.o syscall.o hashtab.o
> +obj-y := core.o syscall.o hashtab.o verifier.o
> diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
> index 836809b1bc4e..48d8f43da151 100644
> --- a/kernel/bpf/syscall.c
> +++ b/kernel/bpf/syscall.c
> @@ -554,7 +554,7 @@ static int bpf_prog_load(int prog_id, enum bpf_prog_type type,
> mutex_lock(&bpf_map_lock);
>
> /* run eBPF verifier */
> - /* err = bpf_check(prog); */
> + err = bpf_check(prog);
>
> if (err == 0 && prog->info->used_maps) {
> /* program passed verifier and it's using some maps,
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> new file mode 100644
> index 000000000000..470fce48b3b0
> --- /dev/null
> +++ b/kernel/bpf/verifier.c
> @@ -0,0 +1,1431 @@
> +/* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
> + *
> + * This program is free software; you can redistribute it and/or
> + * modify it under the terms of version 2 of the GNU General Public
> + * License as published by the Free Software Foundation.
> + *
> + * This program is distributed in the hope that it will be useful, but
> + * WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> + * General Public License for more details.
> + */
> +#include <linux/kernel.h>
> +#include <linux/types.h>
> +#include <linux/slab.h>
> +#include <linux/bpf.h>
> +#include <linux/filter.h>
> +#include <linux/capability.h>
> +
> +/* bpf_check() is a static code analyzer that walks the BPF program
> + * instruction by instruction and updates register/stack state.
> + * All paths of conditional branches are analyzed until 'ret' insn.
> + *
> + * At the first pass depth-first-search verifies that the BPF program is a DAG.
> + * It rejects the following programs:
> + * - larger than BPF_MAXINSNS insns
> + * - if loop is present (detected via back-edge)
> + * - unreachable insns exist (shouldn't be a forest. program = one function)
This seems to me an unnecessary style restriction on user code.
> + * - ret insn is not a last insn
> + * - out of bounds or malformed jumps
> + * The second pass is all possible path descent from the 1st insn.
> + * Conditional branch target insns keep a link list of verifier states.
> + * If the state already visited, this path can be pruned.
> + * If it wasn't a DAG, such state prunning would be incorrect, since it would
> + * skip cycles. Since it's analyzing all pathes through the program,
> + * the length of the analysis is limited to 32k insn, which may be hit even
> + * if insn_cnt < 4K, but there are too many branches that change stack/regs.
> + * Number of 'branches to be analyzed' is limited to 1k
> + *
> + * All registers are 64-bit (even on 32-bit arch)
> + * R0 - return register
> + * R1-R5 argument passing registers
> + * R6-R9 callee saved registers
> + * R10 - frame pointer read-only
> + *
> + * At the start of BPF program the register R1 contains a pointer to bpf_context
> + * and has type PTR_TO_CTX.
> + *
> + * R10 has type PTR_TO_STACK. The sequence 'mov Rd, R10; add Rd, imm' changes
> + * Rd state to PTR_TO_STACK_IMM and immediate constant is saved for further
> + * stack bounds checking
> + *
> + * registers used to pass pointers to function calls are verified against
> + * function prototypes
> + *
> + * Example: before the call to bpf_map_lookup_elem(),
> + * R1 must contain integer constant and R2 PTR_TO_STACK_IMM_MAP_KEY
> + * Integer constant in R1 is a map_id. The verifier checks that map_id is valid
> + * and corresponding map->key_size fetched to check that
> + * [R3, R3 + map_info->key_size) are within stack limits and all that stack
> + * memory was initiliazed earlier by BPF program.
> + * After bpf_table_lookup() call insn, R0 is set to PTR_TO_MAP_CONDITIONAL
> + * R1-R5 are cleared and no longer readable (but still writeable).
> + *
> + * bpf_table_lookup() function returns ether pointer to map value or NULL
> + * which is type PTR_TO_MAP_CONDITIONAL. Once it passes through !=0 insn
> + * the register holding that pointer in the true branch changes state to
> + * PTR_TO_MAP and the same register changes state to INVALID_PTR in the false
> + * branch. See check_cond_jmp_op()
> + *
> + * load/store alignment is checked
> + * Ex: BPF_STX|BPF_W [Rd + 3] = Rs is rejected, because it's misaligned
> + *
> + * load/store to stack bounds checked and register spill is tracked
> + * Ex: BPF_STX|BPF_B [R10 + 0] = Rs is rejected, because it's out of bounds
> + *
> + * load/store to map bounds checked and map_id provides map size
> + * Ex: BPF_STX|BPF_H [Rd + 8] = Rs is ok, if Rd is PTR_TO_MAP and
> + * 8 + sizeof(u16) <= map_info->value_size
> + *
> + * load/store to bpf_context checked against known fields
> + */
> +#define _(OP) ({ int ret = OP; if (ret < 0) return ret; })
+1 to removing the _ macro. If you want to avoid the 3 lines (is there
anything in the style guide against "if ((err=OP) < 0) ..." ?), at
least use some meaningful macro name (DO_AND_CHECK, or something like
that).
> +
> +struct reg_state {
> + enum bpf_reg_type ptr;
> + int imm;
> + bool read_ok;
> +};
> +
> +enum bpf_stack_slot_type {
> + STACK_INVALID, /* nothing was stored in this stack slot */
> + STACK_SPILL, /* 1st byte of register spilled into stack */
> + STACK_SPILL_PART, /* other 7 bytes of register spill */
> + STACK_MISC /* BPF program wrote some data into this slot */
> +};
> +
> +struct bpf_stack_slot {
> + enum bpf_stack_slot_type type;
> + enum bpf_reg_type ptr;
> + int imm;
> +};
> +
> +/* state of the program:
> + * type of all registers and stack info
> + */
> +struct verifier_state {
> + struct reg_state regs[MAX_BPF_REG];
> + struct bpf_stack_slot stack[MAX_BPF_STACK];
> +};
> +
> +/* linked list of verifier states used to prune search */
> +struct verifier_state_list {
> + struct verifier_state state;
> + struct verifier_state_list *next;
> +};
> +
> +/* verifier_state + insn_idx are pushed to stack when branch is encountered */
> +struct verifier_stack_elem {
> + /* verifer state is 'st'
> + * before processing instruction 'insn_idx'
> + * and after processing instruction 'prev_insn_idx'
> + */
> + struct verifier_state st;
> + int insn_idx;
> + int prev_insn_idx;
> + struct verifier_stack_elem *next;
> +};
> +
> +#define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */
> +
> +/* single container for all structs
> + * one verifier_env per bpf_check() call
> + */
> +struct verifier_env {
> + struct sk_filter *prog; /* eBPF program being verified */
> + struct verifier_stack_elem *head; /* stack of verifier states to be processed */
> + int stack_size; /* number of states to be processed */
> + struct verifier_state cur_state; /* current verifier state */
> + struct verifier_state_list **branch_landing; /* search prunning optimization */
> + u32 used_maps[MAX_USED_MAPS]; /* array of map_id's used by eBPF program */
> + u32 used_map_cnt; /* number of used maps */
> +};
> +
> +/* verbose verifier prints what it's seeing
> + * bpf_check() is called under map lock, so no race to access this global var
> + */
> +static bool verbose_on;
> +
> +/* when verifier rejects eBPF program, it does a second path with verbose on
> + * to dump the verification trace to the log, so the user can figure out what's
> + * wrong with the program
> + */
> +static int verbose(const char *fmt, ...)
> +{
> + va_list args;
> + int ret;
> +
> + if (!verbose_on)
> + return 0;
> +
> + va_start(args, fmt);
> + ret = vprintk(fmt, args);
> + va_end(args);
> + return ret;
> +}
> +
> +/* string representation of 'enum bpf_reg_type' */
> +static const char * const reg_type_str[] = {
> + [INVALID_PTR] = "inv",
> + [PTR_TO_CTX] = "ctx",
> + [PTR_TO_MAP] = "map_value",
> + [PTR_TO_MAP_CONDITIONAL] = "map_value_or_null",
> + [PTR_TO_STACK] = "fp",
> + [PTR_TO_STACK_IMM] = "fp",
> + [PTR_TO_STACK_IMM_MAP_KEY] = "fp_key",
> + [PTR_TO_STACK_IMM_MAP_VALUE] = "fp_value",
> + [RET_INTEGER] = "ret_int",
> + [RET_VOID] = "ret_void",
> + [CONST_ARG] = "imm",
> + [CONST_ARG_MAP_ID] = "map_id",
> + [CONST_ARG_STACK_IMM_SIZE] = "imm_size",
> +};
> +
> +static void pr_cont_verifier_state(struct verifier_env *env)
> +{
> + enum bpf_reg_type ptr;
> + int i;
> +
> + for (i = 0; i < MAX_BPF_REG; i++) {
> + if (!env->cur_state.regs[i].read_ok)
> + continue;
> + ptr = env->cur_state.regs[i].ptr;
> + pr_cont(" R%d=%s", i, reg_type_str[ptr]);
> + if (ptr == CONST_ARG ||
> + ptr == PTR_TO_STACK_IMM ||
> + ptr == PTR_TO_MAP_CONDITIONAL ||
> + ptr == PTR_TO_MAP)
> + pr_cont("%d", env->cur_state.regs[i].imm);
> + }
> + for (i = 0; i < MAX_BPF_STACK; i++) {
> + if (env->cur_state.stack[i].type == STACK_SPILL)
> + pr_cont(" fp%d=%s", -MAX_BPF_STACK + i,
> + reg_type_str[env->cur_state.stack[i].ptr]);
> + }
> + pr_cont("\n");
> +}
> +
> +static const char *const bpf_class_string[] = {
> + "ld", "ldx", "st", "stx", "alu", "jmp", "BUG", "alu64"
> +};
> +
> +static const char *const bpf_alu_string[] = {
> + "+=", "-=", "*=", "/=", "|=", "&=", "<<=", ">>=", "neg",
> + "%=", "^=", "=", "s>>=", "endian", "BUG", "BUG"
> +};
> +
> +static const char *const bpf_ldst_string[] = {
> + "u32", "u16", "u8", "u64"
> +};
> +
> +static const char *const bpf_jmp_string[] = {
> + "jmp", "==", ">", ">=", "&", "!=", "s>", "s>=", "call", "exit"
> +};
> +
> +static void pr_cont_bpf_insn(struct sock_filter_int *insn)
> +{
> + u8 class = BPF_CLASS(insn->code);
> +
> + if (class == BPF_ALU || class == BPF_ALU64) {
> + if (BPF_SRC(insn->code) == BPF_X)
> + pr_cont("(%02x) %sr%d %s %sr%d\n",
> + insn->code, class == BPF_ALU ? "(u32) " : "",
> + insn->dst_reg,
> + bpf_alu_string[BPF_OP(insn->code) >> 4],
> + class == BPF_ALU ? "(u32) " : "",
> + insn->src_reg);
> + else
> + pr_cont("(%02x) %sr%d %s %s%d\n",
> + insn->code, class == BPF_ALU ? "(u32) " : "",
> + insn->dst_reg,
> + bpf_alu_string[BPF_OP(insn->code) >> 4],
> + class == BPF_ALU ? "(u32) " : "",
> + insn->imm);
> + } else if (class == BPF_STX) {
> + if (BPF_MODE(insn->code) == BPF_MEM)
> + pr_cont("(%02x) *(%s *)(r%d %+d) = r%d\n",
> + insn->code,
> + bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
> + insn->dst_reg,
> + insn->off, insn->src_reg);
> + else if (BPF_MODE(insn->code) == BPF_XADD)
> + pr_cont("(%02x) lock *(%s *)(r%d %+d) += r%d\n",
> + insn->code,
> + bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
> + insn->dst_reg, insn->off,
> + insn->src_reg);
> + else
> + pr_cont("BUG_%02x\n", insn->code);
> + } else if (class == BPF_ST) {
> + if (BPF_MODE(insn->code) != BPF_MEM) {
> + pr_cont("BUG_st_%02x\n", insn->code);
> + return;
> + }
> + pr_cont("(%02x) *(%s *)(r%d %+d) = %d\n",
> + insn->code,
> + bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
> + insn->dst_reg,
> + insn->off, insn->imm);
> + } else if (class == BPF_LDX) {
> + if (BPF_MODE(insn->code) != BPF_MEM) {
> + pr_cont("BUG_ldx_%02x\n", insn->code);
> + return;
> + }
> + pr_cont("(%02x) r%d = *(%s *)(r%d %+d)\n",
> + insn->code, insn->dst_reg,
> + bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
> + insn->src_reg, insn->off);
Can you please add:
+ } else if (class == BPF_LD) {
+ if (BPF_MODE(insn->code) == BPF_ABS) {
+ pr_cont("(%02x) r0 = *(%s *)skb[%d]\n",
+ insn->code,
+ bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
+ insn->imm);
+ } else if (BPF_MODE(insn->code) == BPF_IND) {
+ pr_cont("(%02x) r0 = *(%s *)skb[r%d + %d]\n",
+ insn->code,
+ bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
+ insn->src_reg, insn->imm);
+ } else {
+ pr_cont("BUG_ld_%02x\n", insn->code);
+ return;
+ }
Note that I'm hardcoding r0 (instead of using %d for insn->dst_reg)
because that's how ebpf writes the instructions.
> + } else if (class == BPF_JMP) {
> + u8 opcode = BPF_OP(insn->code);
> +
> + if (opcode == BPF_CALL) {
> + pr_cont("(%02x) call %d\n", insn->code, insn->imm);
> + } else if (insn->code == (BPF_JMP | BPF_JA)) {
> + pr_cont("(%02x) goto pc%+d\n",
> + insn->code, insn->off);
> + } else if (insn->code == (BPF_JMP | BPF_EXIT)) {
> + pr_cont("(%02x) exit\n", insn->code);
> + } else if (BPF_SRC(insn->code) == BPF_X) {
> + pr_cont("(%02x) if r%d %s r%d goto pc%+d\n",
> + insn->code, insn->dst_reg,
> + bpf_jmp_string[BPF_OP(insn->code) >> 4],
> + insn->src_reg, insn->off);
> + } else {
> + pr_cont("(%02x) if r%d %s 0x%x goto pc%+d\n",
> + insn->code, insn->dst_reg,
> + bpf_jmp_string[BPF_OP(insn->code) >> 4],
> + insn->imm, insn->off);
> + }
> + } else {
> + pr_cont("(%02x) %s\n", insn->code, bpf_class_string[class]);
> + }
> +}
> +
> +static int pop_stack(struct verifier_env *env, int *prev_insn_idx)
> +{
> + struct verifier_stack_elem *elem;
> + int insn_idx;
> +
> + if (env->head == NULL)
> + return -1;
> +
> + memcpy(&env->cur_state, &env->head->st, sizeof(env->cur_state));
> + insn_idx = env->head->insn_idx;
> + if (prev_insn_idx)
> + *prev_insn_idx = env->head->prev_insn_idx;
> + elem = env->head->next;
> + kfree(env->head);
> + env->head = elem;
> + env->stack_size--;
> + return insn_idx;
> +}
> +
> +static struct verifier_state *push_stack(struct verifier_env *env, int insn_idx,
> + int prev_insn_idx)
> +{
> + struct verifier_stack_elem *elem;
> +
> + elem = kmalloc(sizeof(struct verifier_stack_elem), GFP_KERNEL);
> + if (!elem)
> + goto err;
> +
> + memcpy(&elem->st, &env->cur_state, sizeof(env->cur_state));
> + elem->insn_idx = insn_idx;
> + elem->prev_insn_idx = prev_insn_idx;
> + elem->next = env->head;
> + env->head = elem;
> + env->stack_size++;
> + if (env->stack_size > 1024) {
> + verbose("BPF program is too complex\n");
> + goto err;
> + }
> + return &elem->st;
> +err:
> + /* pop all elements and return */
> + while (pop_stack(env, NULL) >= 0);
> + return NULL;
> +}
> +
> +#define CALLER_SAVED_REGS 6
> +static const int caller_saved[CALLER_SAVED_REGS] = {
> + BPF_REG_0, BPF_REG_1, BPF_REG_2, BPF_REG_3, BPF_REG_4, BPF_REG_5
> +};
> +
> +static void init_reg_state(struct reg_state *regs)
> +{
> + struct reg_state *reg;
> + int i;
> +
> + for (i = 0; i < MAX_BPF_REG; i++) {
> + regs[i].ptr = INVALID_PTR;
> + regs[i].read_ok = false;
> + regs[i].imm = 0xbadbad;
> + }
> + reg = regs + BPF_REG_FP;
Any reason you switching from the array syntax to the pointer one? I
find "reg = regs[BPF_REG_FP];" more readable (and the one you chose in
the loop).
> + reg->ptr = PTR_TO_STACK;
> + reg->read_ok = true;
> +
> + reg = regs + BPF_REG_1; /* 1st arg to a function */
> + reg->ptr = PTR_TO_CTX;
Wait, doesn't this depend on doing "BPF_MOV64_REG(BPF_REG_CTX,
BPF_REG_ARG1)" (the bpf-to-ebpf prologue), which is only enforced on
filters converted from bpf? In fact, shouldn't this set
regs[BPF_REG_CTX] instead of regs[BPF_REG_1] ?
> + reg->read_ok = true;
> +}
> +
> +static void mark_reg_no_ptr(struct reg_state *regs, int regno)
> +{
> + regs[regno].ptr = INVALID_PTR;
> + regs[regno].imm = 0xbadbad;
> + regs[regno].read_ok = true;
> +}
> +
> +static int check_reg_arg(struct reg_state *regs, int regno, bool is_src)
> +{
> + if (is_src) {
> + if (!regs[regno].read_ok) {
> + verbose("R%d !read_ok\n", regno);
> + return -EACCES;
> + }
> + } else {
> + if (regno == BPF_REG_FP)
> + /* frame pointer is read only */
> + return -EACCES;
> + mark_reg_no_ptr(regs, regno);
> + }
> + return 0;
> +}
> +
> +static int bpf_size_to_bytes(int bpf_size)
> +{
> + if (bpf_size == BPF_W)
> + return 4;
> + else if (bpf_size == BPF_H)
> + return 2;
> + else if (bpf_size == BPF_B)
> + return 1;
> + else if (bpf_size == BPF_DW)
> + return 8;
> + else
> + return -EACCES;
> +}
> +
> +static int check_stack_write(struct verifier_state *state, int off, int size,
> + int value_regno)
> +{
> + struct bpf_stack_slot *slot;
> + int i;
> +
> + if (value_regno >= 0 &&
> + (state->regs[value_regno].ptr == PTR_TO_MAP ||
> + state->regs[value_regno].ptr == PTR_TO_STACK_IMM ||
> + state->regs[value_regno].ptr == PTR_TO_CTX)) {
> +
> + /* register containing pointer is being spilled into stack */
> + if (size != 8) {
> + verbose("invalid size of register spill\n");
> + return -EACCES;
> + }
> +
> + slot = &state->stack[MAX_BPF_STACK + off];
> + slot->type = STACK_SPILL;
> + /* save register state */
> + slot->ptr = state->regs[value_regno].ptr;
> + slot->imm = state->regs[value_regno].imm;
> + for (i = 1; i < 8; i++) {
> + slot = &state->stack[MAX_BPF_STACK + off + i];
> + slot->type = STACK_SPILL_PART;
> + slot->ptr = 0;
> + slot->imm = 0;
> + }
> + } else {
> +
> + /* regular write of data into stack */
> + for (i = 0; i < size; i++) {
> + slot = &state->stack[MAX_BPF_STACK + off + i];
> + slot->type = STACK_MISC;
> + slot->ptr = 0;
> + slot->imm = 0;
> + }
> + }
> + return 0;
> +}
> +
> +static int check_stack_read(struct verifier_state *state, int off, int size,
> + int value_regno)
> +{
> + int i;
> + struct bpf_stack_slot *slot;
> +
> + slot = &state->stack[MAX_BPF_STACK + off];
> +
> + if (slot->type == STACK_SPILL) {
> + if (size != 8) {
> + verbose("invalid size of register spill\n");
> + return -EACCES;
> + }
> + for (i = 1; i < 8; i++) {
> + if (state->stack[MAX_BPF_STACK + off + i].type !=
> + STACK_SPILL_PART) {
> + verbose("corrupted spill memory\n");
> + return -EACCES;
> + }
> + }
> +
> + /* restore register state from stack */
> + state->regs[value_regno].ptr = slot->ptr;
> + state->regs[value_regno].imm = slot->imm;
> + state->regs[value_regno].read_ok = true;
> + return 0;
> + } else {
> + for (i = 0; i < size; i++) {
> + if (state->stack[MAX_BPF_STACK + off + i].type !=
> + STACK_MISC) {
> + verbose("invalid read from stack off %d+%d size %d\n",
> + off, i, size);
> + return -EACCES;
> + }
> + }
> + /* have read misc data from the stack */
> + mark_reg_no_ptr(state->regs, value_regno);
> + return 0;
> + }
> +}
> +
> +static int remember_map_id(struct verifier_env *env, u32 map_id)
> +{
> + int i;
> +
> + /* check whether we recorded this map_id already */
> + for (i = 0; i < env->used_map_cnt; i++)
> + if (env->used_maps[i] == map_id)
> + return 0;
> +
> + if (env->used_map_cnt >= MAX_USED_MAPS)
> + return -E2BIG;
> +
> + /* remember this map_id */
> + env->used_maps[env->used_map_cnt++] = map_id;
> + return 0;
> +}
> +
> +static int get_map_info(struct verifier_env *env, u32 map_id,
> + struct bpf_map **map)
> +{
> + /* if BPF program contains bpf_table_lookup(map_id, key)
> + * the incorrect map_id will be caught here
> + */
> + *map = bpf_map_get(map_id);
> + if (!*map) {
> + verbose("invalid access to map_id=%d\n", map_id);
> + return -EACCES;
> + }
> +
> + _(remember_map_id(env, map_id));
> +
> + return 0;
> +}
> +
> +/* check read/write into map element returned by bpf_table_lookup() */
> +static int check_table_access(struct verifier_env *env, int regno, int off,
> + int size)
> +{
> + struct bpf_map *map;
> + int map_id = env->cur_state.regs[regno].imm;
> +
> + _(get_map_info(env, map_id, &map));
> +
> + if (off < 0 || off + size > map->value_size) {
> + verbose("invalid access to map_id=%d leaf_size=%d off=%d size=%d\n",
> + map_id, map->value_size, off, size);
> + return -EACCES;
> + }
> + return 0;
> +}
> +
> +/* check access to 'struct bpf_context' fields */
> +static int check_ctx_access(struct verifier_env *env, int off, int size,
> + enum bpf_access_type t)
> +{
> + if (env->prog->info->ops->is_valid_access &&
> + env->prog->info->ops->is_valid_access(off, size, t))
> + return 0;
> +
> + verbose("invalid bpf_context access off=%d size=%d\n", off, size);
> + return -EACCES;
> +}
> +
> +static int check_mem_access(struct verifier_env *env, int regno, int off,
> + int bpf_size, enum bpf_access_type t,
> + int value_regno)
> +{
> + struct verifier_state *state = &env->cur_state;
> + int size;
> +
> + _(size = bpf_size_to_bytes(bpf_size));
> +
> + if (off % size != 0) {
> + verbose("misaligned access off %d size %d\n", off, size);
> + return -EACCES;
> + }
> +
> + if (state->regs[regno].ptr == PTR_TO_MAP) {
> + _(check_table_access(env, regno, off, size));
> + if (t == BPF_READ)
> + mark_reg_no_ptr(state->regs, value_regno);
> + } else if (state->regs[regno].ptr == PTR_TO_CTX) {
> + _(check_ctx_access(env, off, size, t));
> + if (t == BPF_READ)
> + mark_reg_no_ptr(state->regs, value_regno);
> + } else if (state->regs[regno].ptr == PTR_TO_STACK) {
> + if (off >= 0 || off < -MAX_BPF_STACK) {
> + verbose("invalid stack off=%d size=%d\n", off, size);
> + return -EACCES;
> + }
> + if (t == BPF_WRITE)
> + _(check_stack_write(state, off, size, value_regno));
> + else
> + _(check_stack_read(state, off, size, value_regno));
> + } else {
> + verbose("R%d invalid mem access '%s'\n",
> + regno, reg_type_str[state->regs[regno].ptr]);
> + return -EACCES;
> + }
> + return 0;
> +}
> +
> +/* when register 'regno' is passed into function that will read 'access_size'
> + * bytes from that pointer, make sure that it's within stack boundary
> + * and all elements of stack are initialized
> + */
> +static int check_stack_boundary(struct verifier_env *env,
> + int regno, int access_size)
> +{
> + struct verifier_state *state = &env->cur_state;
> + struct reg_state *regs = state->regs;
> + int off, i;
> +
> + if (regs[regno].ptr != PTR_TO_STACK_IMM)
> + return -EACCES;
> +
> + off = regs[regno].imm;
> + if (off >= 0 || off < -MAX_BPF_STACK || off + access_size > 0 ||
> + access_size <= 0) {
> + verbose("invalid stack ptr R%d off=%d access_size=%d\n",
> + regno, off, access_size);
> + return -EACCES;
> + }
> +
> + for (i = 0; i < access_size; i++) {
> + if (state->stack[MAX_BPF_STACK + off + i].type != STACK_MISC) {
> + verbose("invalid indirect read from stack off %d+%d size %d\n",
> + off, i, access_size);
> + return -EACCES;
> + }
> + }
> + return 0;
> +}
> +
> +static int check_func_arg(struct verifier_env *env, int regno,
> + enum bpf_reg_type arg_type, int *map_id,
> + struct bpf_map **mapp)
> +{
> + struct reg_state *reg = env->cur_state.regs + regno;
> + enum bpf_reg_type expected_type;
> +
> + if (arg_type == INVALID_PTR)
> + return 0;
> +
> + if (!reg->read_ok) {
> + verbose("R%d !read_ok\n", regno);
> + return -EACCES;
> + }
> +
> + if (arg_type == PTR_TO_STACK_IMM_MAP_KEY ||
> + arg_type == PTR_TO_STACK_IMM_MAP_VALUE)
> + expected_type = PTR_TO_STACK_IMM;
> + else if (arg_type == CONST_ARG_MAP_ID ||
> + arg_type == CONST_ARG_STACK_IMM_SIZE)
> + expected_type = CONST_ARG;
> + else
> + expected_type = arg_type;
> +
> + if (reg->ptr != expected_type) {
> + verbose("R%d type=%s expected=%s\n", regno,
> + reg_type_str[reg->ptr], reg_type_str[expected_type]);
> + return -EACCES;
> + }
> +
> + if (arg_type == CONST_ARG_MAP_ID) {
> + /* bpf_map_xxx(map_id) call: check that map_id is valid */
> + *map_id = reg->imm;
> + _(get_map_info(env, reg->imm, mapp));
> + } else if (arg_type == PTR_TO_STACK_IMM_MAP_KEY) {
> + /*
> + * bpf_map_xxx(..., map_id, ..., key) call:
> + * check that [key, key + map->key_size) are within
> + * stack limits and initialized
> + */
> + if (!*mapp) {
> + /*
> + * in function declaration map_id must come before
> + * table_key or table_elem, so that it's verified
> + * and known before we have to check table_key here
> + */
> + verbose("invalid map_id to access map->key\n");
> + return -EACCES;
> + }
> + _(check_stack_boundary(env, regno, (*mapp)->key_size));
> + } else if (arg_type == PTR_TO_STACK_IMM_MAP_VALUE) {
> + /*
> + * bpf_map_xxx(..., map_id, ..., value) call:
> + * check [value, value + map->value_size) validity
> + */
> + if (!*mapp) {
> + verbose("invalid map_id to access map->elem\n");
> + return -EACCES;
> + }
> + _(check_stack_boundary(env, regno, (*mapp)->value_size));
> + } else if (arg_type == CONST_ARG_STACK_IMM_SIZE) {
> + /*
> + * bpf_xxx(..., buf, len) call will access 'len' bytes
> + * from stack pointer 'buf'. Check it
> + * note: regno == len, regno - 1 == buf
> + */
> + _(check_stack_boundary(env, regno - 1, reg->imm));
> + }
> +
> + return 0;
> +}
> +
> +static int check_call(struct verifier_env *env, int func_id)
> +{
> + struct verifier_state *state = &env->cur_state;
> + const struct bpf_func_proto *fn = NULL;
> + struct reg_state *regs = state->regs;
> + struct bpf_map *map = NULL;
> + struct reg_state *reg;
> + int map_id = -1;
> + int i;
> +
> + /* find function prototype */
> + if (func_id <= 0 || func_id >= __BPF_FUNC_MAX_ID) {
> + verbose("invalid func %d\n", func_id);
> + return -EINVAL;
> + }
> +
> + if (env->prog->info->ops->get_func_proto)
> + fn = env->prog->info->ops->get_func_proto(func_id);
> +
> + if (!fn || (fn->ret_type != RET_INTEGER &&
> + fn->ret_type != PTR_TO_MAP_CONDITIONAL &&
> + fn->ret_type != RET_VOID)) {
> + verbose("unknown func %d\n", func_id);
> + return -EINVAL;
> + }
> +
> + /* check args */
> + _(check_func_arg(env, BPF_REG_1, fn->arg1_type, &map_id, &map));
> + _(check_func_arg(env, BPF_REG_2, fn->arg2_type, &map_id, &map));
> + _(check_func_arg(env, BPF_REG_3, fn->arg3_type, &map_id, &map));
> + _(check_func_arg(env, BPF_REG_4, fn->arg4_type, &map_id, &map));
> +
> + /* reset caller saved regs */
> + for (i = 0; i < CALLER_SAVED_REGS; i++) {
> + reg = regs + caller_saved[i];
> + reg->read_ok = false;
> + reg->ptr = INVALID_PTR;
> + reg->imm = 0xbadbad;
> + }
> +
> + /* update return register */
> + reg = regs + BPF_REG_0;
> + if (fn->ret_type == RET_INTEGER) {
> + reg->read_ok = true;
> + reg->ptr = INVALID_PTR;
> + } else if (fn->ret_type != RET_VOID) {
> + reg->read_ok = true;
> + reg->ptr = fn->ret_type;
> + if (fn->ret_type == PTR_TO_MAP_CONDITIONAL)
> + /*
> + * remember map_id, so that check_table_access()
> + * can check 'value_size' boundary of memory access
> + * to map element returned from bpf_table_lookup()
> + */
> + reg->imm = map_id;
> + }
> + return 0;
> +}
> +
> +/* check validity of 32-bit and 64-bit arithmetic operations */
> +static int check_alu_op(struct reg_state *regs, struct sock_filter_int *insn)
> +{
> + u8 opcode = BPF_OP(insn->code);
> +
> + if (opcode == BPF_END || opcode == BPF_NEG) {
> + if (BPF_SRC(insn->code) != BPF_X)
> + return -EINVAL;
> + /* check src operand */
> + _(check_reg_arg(regs, insn->dst_reg, 1));
> +
> + /* check dest operand */
> + _(check_reg_arg(regs, insn->dst_reg, 0));
> +
> + } else if (opcode == BPF_MOV) {
> +
> + if (BPF_SRC(insn->code) == BPF_X)
> + /* check src operand */
> + _(check_reg_arg(regs, insn->src_reg, 1));
> +
> + /* check dest operand */
> + _(check_reg_arg(regs, insn->dst_reg, 0));
> +
> + if (BPF_SRC(insn->code) == BPF_X) {
> + if (BPF_CLASS(insn->code) == BPF_ALU64) {
> + /* case: R1 = R2
> + * copy register state to dest reg
> + */
> + regs[insn->dst_reg].ptr = regs[insn->src_reg].ptr;
> + regs[insn->dst_reg].imm = regs[insn->src_reg].imm;
> + } else {
> + regs[insn->dst_reg].ptr = INVALID_PTR;
> + regs[insn->dst_reg].imm = 0;
> + }
> + } else {
> + /* case: R = imm
> + * remember the value we stored into this reg
> + */
> + regs[insn->dst_reg].ptr = CONST_ARG;
> + regs[insn->dst_reg].imm = insn->imm;
> + }
> +
> + } else { /* all other ALU ops: and, sub, xor, add, ... */
> +
> + int stack_relative = 0;
> +
> + if (BPF_SRC(insn->code) == BPF_X)
> + /* check src1 operand */
> + _(check_reg_arg(regs, insn->src_reg, 1));
> +
> + /* check src2 operand */
> + _(check_reg_arg(regs, insn->dst_reg, 1));
> +
> + if (opcode == BPF_ADD && BPF_CLASS(insn->code) == BPF_ALU64 &&
> + regs[insn->dst_reg].ptr == PTR_TO_STACK &&
> + BPF_SRC(insn->code) == BPF_K)
> + stack_relative = 1;
> +
> + /* check dest operand */
> + _(check_reg_arg(regs, insn->dst_reg, 0));
> +
> + if (stack_relative) {
> + regs[insn->dst_reg].ptr = PTR_TO_STACK_IMM;
> + regs[insn->dst_reg].imm = insn->imm;
> + }
> + }
> +
> + return 0;
> +}
> +
> +static int check_cond_jmp_op(struct verifier_env *env,
> + struct sock_filter_int *insn, int *insn_idx)
> +{
> + struct reg_state *regs = env->cur_state.regs;
> + struct verifier_state *other_branch;
> + u8 opcode = BPF_OP(insn->code);
> +
> + if (BPF_SRC(insn->code) == BPF_X)
> + /* check src1 operand */
> + _(check_reg_arg(regs, insn->src_reg, 1));
> +
> + /* check src2 operand */
> + _(check_reg_arg(regs, insn->dst_reg, 1));
> +
> + /* detect if R == 0 where R was initialized to zero earlier */
> + if (BPF_SRC(insn->code) == BPF_K &&
> + (opcode == BPF_JEQ || opcode == BPF_JNE) &&
> + regs[insn->dst_reg].ptr == CONST_ARG &&
> + regs[insn->dst_reg].imm == insn->imm) {
> + if (opcode == BPF_JEQ) {
> + /* if (imm == imm) goto pc+off;
> + * only follow the goto, ignore fall-through
> + */
> + *insn_idx += insn->off;
> + return 0;
> + } else {
> + /* if (imm != imm) goto pc+off;
> + * only follow fall-through branch, since
> + * that's where the program will go
> + */
> + return 0;
> + }
> + }
> +
> + other_branch = push_stack(env, *insn_idx + insn->off + 1, *insn_idx);
> + if (!other_branch)
> + return -EFAULT;
> +
> + /* detect if R == 0 where R is returned value from table_lookup() */
> + if (BPF_SRC(insn->code) == BPF_K &&
> + insn->imm == 0 && (opcode == BPF_JEQ ||
> + opcode == BPF_JNE) &&
> + regs[insn->dst_reg].ptr == PTR_TO_MAP_CONDITIONAL) {
> + if (opcode == BPF_JEQ) {
> + /* next fallthrough insn can access memory via
> + * this register
> + */
> + regs[insn->dst_reg].ptr = PTR_TO_MAP;
> + /* branch targer cannot access it, since reg == 0 */
> + other_branch->regs[insn->dst_reg].ptr = CONST_ARG;
> + other_branch->regs[insn->dst_reg].imm = 0;
> + } else {
> + other_branch->regs[insn->dst_reg].ptr = PTR_TO_MAP;
> + regs[insn->dst_reg].ptr = CONST_ARG;
> + regs[insn->dst_reg].imm = 0;
> + }
> + } else if (BPF_SRC(insn->code) == BPF_K &&
> + (opcode == BPF_JEQ || opcode == BPF_JNE)) {
> +
> + if (opcode == BPF_JEQ) {
> + /* detect if (R == imm) goto
> + * and in the target state recognize that R = imm
> + */
> + other_branch->regs[insn->dst_reg].ptr = CONST_ARG;
> + other_branch->regs[insn->dst_reg].imm = insn->imm;
> + } else {
> + /* detect if (R != imm) goto
> + * and in the fall-through state recognize that R = imm
> + */
> + regs[insn->dst_reg].ptr = CONST_ARG;
> + regs[insn->dst_reg].imm = insn->imm;
> + }
> + }
> + if (verbose_on)
> + pr_cont_verifier_state(env);
> + return 0;
> +}
> +
> +/* verify safety of LD_ABS|LD_IND instructions:
> + * - they can only appear in the programs where ctx == skb
> + * - since they are wrappers of function calls, they scratch R1-R5 registers,
> + * preserve R6-R9, and store return value into R0
> + *
> + * Implicit input:
> + * ctx == skb == R6 == CTX
> + *
> + * Explicit input:
> + * SRC == any register
> + * IMM == 32-bit immediate
> + *
> + * Output:
> + * R0 - 8/16/32-bit skb data converted to cpu endianness
> + */
> +
> +static int check_ld_abs(struct verifier_env *env, struct sock_filter_int *insn)
> +{
> + struct reg_state *regs = env->cur_state.regs;
> + u8 mode = BPF_MODE(insn->code);
> + struct reg_state *reg;
> + int i;
> +
> + if (mode != BPF_ABS && mode != BPF_IND)
> + return -EINVAL;
> +
> + if (env->prog->info->prog_type != BPF_PROG_TYPE_SOCKET_FILTER) {
> + verbose("BPF_LD_ABS|IND instructions are only allowed in socket filters\n");
> + return -EINVAL;
> + }
> +
> + /* check whether implicit source operand (register R6) is readable */
> + _(check_reg_arg(regs, BPF_REG_6, 1));
> +
> + if (regs[BPF_REG_6].ptr != PTR_TO_CTX) {
> + verbose("at the time of BPF_LD_ABS|IND R6 != pointer to skb\n");
> + return -EINVAL;
> + }
> +
> + if (mode == BPF_IND)
> + /* check explicit source operand */
> + _(check_reg_arg(regs, insn->src_reg, 1));
> +
> + /* reset caller saved regs to unreadable */
> + for (i = 0; i < CALLER_SAVED_REGS; i++) {
> + reg = regs + caller_saved[i];
> + reg->read_ok = false;
> + reg->ptr = INVALID_PTR;
> + reg->imm = 0xbadbad;
> + }
> +
> + /* mark destination R0 register as readable, since it contains
> + * the value fetched from the packet
> + */
> + regs[BPF_REG_0].read_ok = true;
> + return 0;
> +}
> +
> +/* non-recursive DFS pseudo code
> + * 1 procedure DFS-iterative(G,v):
> + * 2 label v as discovered
> + * 3 let S be a stack
> + * 4 S.push(v)
> + * 5 while S is not empty
> + * 6 t <- S.pop()
> + * 7 if t is what we're looking for:
> + * 8 return t
> + * 9 for all edges e in G.adjacentEdges(t) do
> + * 10 if edge e is already labelled
> + * 11 continue with the next edge
> + * 12 w <- G.adjacentVertex(t,e)
> + * 13 if vertex w is not discovered and not explored
> + * 14 label e as tree-edge
> + * 15 label w as discovered
> + * 16 S.push(w)
> + * 17 continue at 5
> + * 18 else if vertex w is discovered
> + * 19 label e as back-edge
> + * 20 else
> + * 21 // vertex w is explored
> + * 22 label e as forward- or cross-edge
> + * 23 label t as explored
> + * 24 S.pop()
> + *
> + * convention:
> + * 1 - discovered
> + * 2 - discovered and 1st branch labelled
> + * 3 - discovered and 1st and 2nd branch labelled
> + * 4 - explored
> + */
> +
> +#define STATE_END ((struct verifier_state_list *)-1)
> +
> +#define PUSH_INT(I) \
> + do { \
> + if (cur_stack >= insn_cnt) { \
> + ret = -E2BIG; \
> + goto free_st; \
> + } \
> + stack[cur_stack++] = I; \
> + } while (0)
> +
> +#define PEAK_INT() \
> + ({ \
> + int _ret; \
> + if (cur_stack == 0) \
> + _ret = -1; \
> + else \
> + _ret = stack[cur_stack - 1]; \
> + _ret; \
> + })
> +
> +#define POP_INT() \
> + ({ \
> + int _ret; \
> + if (cur_stack == 0) \
> + _ret = -1; \
> + else \
> + _ret = stack[--cur_stack]; \
> + _ret; \
> + })
> +
> +#define PUSH_INSN(T, W, E) \
> + do { \
> + int w = W; \
> + if (E == 1 && st[T] >= 2) \
> + break; \
> + if (E == 2 && st[T] >= 3) \
> + break; \
> + if (w >= insn_cnt) { \
> + ret = -EACCES; \
> + goto free_st; \
> + } \
> + if (E == 2) \
> + /* mark branch target for state pruning */ \
> + env->branch_landing[w] = STATE_END; \
> + if (st[w] == 0) { \
> + /* tree-edge */ \
> + st[T] = 1 + E; \
> + st[w] = 1; /* discovered */ \
> + PUSH_INT(w); \
> + goto peak_stack; \
> + } else if (st[w] == 1 || st[w] == 2 || st[w] == 3) { \
> + verbose("back-edge from insn %d to %d\n", t, w); \
> + ret = -EINVAL; \
> + goto free_st; \
> + } else if (st[w] == 4) { \
> + /* forward- or cross-edge */ \
> + st[T] = 1 + E; \
> + } else { \
> + verbose("insn state internal bug\n"); \
> + ret = -EFAULT; \
> + goto free_st; \
> + } \
> + } while (0)
> +
> +/* non-recursive depth-first-search to detect loops in BPF program
> + * loop == back-edge in directed graph
> + */
> +static int check_cfg(struct verifier_env *env)
> +{
> + struct sock_filter_int *insns = env->prog->insnsi;
> + int insn_cnt = env->prog->len;
> + int cur_stack = 0;
> + int *stack;
> + int ret = 0;
> + int *st;
> + int i, t;
> +
> + if (insns[insn_cnt - 1].code != (BPF_JMP | BPF_EXIT)) {
> + verbose("last insn is not a 'ret'\n");
> + return -EINVAL;
> + }
> +
> + st = kzalloc(sizeof(int) * insn_cnt, GFP_KERNEL);
> + if (!st)
> + return -ENOMEM;
> +
> + stack = kzalloc(sizeof(int) * insn_cnt, GFP_KERNEL);
> + if (!stack) {
> + kfree(st);
> + return -ENOMEM;
> + }
> +
> + st[0] = 1; /* mark 1st insn as discovered */
> + PUSH_INT(0);
> +
> +peak_stack:
> + while ((t = PEAK_INT()) != -1) {
> + if (insns[t].code == (BPF_JMP | BPF_EXIT))
> + goto mark_explored;
> +
> + if (BPF_CLASS(insns[t].code) == BPF_JMP) {
> + u8 opcode = BPF_OP(insns[t].code);
> +
> + if (opcode == BPF_CALL) {
> + PUSH_INSN(t, t + 1, 1);
> + } else if (opcode == BPF_JA) {
> + if (BPF_SRC(insns[t].code) != BPF_X) {
> + ret = -EINVAL;
> + goto free_st;
> + }
> + PUSH_INSN(t, t + insns[t].off + 1, 1);
> + } else {
> + PUSH_INSN(t, t + 1, 1);
> + PUSH_INSN(t, t + insns[t].off + 1, 2);
> + }
> + /* tell verifier to check for equivalent verifier states
> + * after every call and jump
> + */
> + env->branch_landing[t + 1] = STATE_END;
> + } else {
> + PUSH_INSN(t, t + 1, 1);
> + }
> +
> +mark_explored:
> + st[t] = 4; /* explored */
> + if (POP_INT() == -1) {
> + verbose("pop_int internal bug\n");
> + ret = -EFAULT;
> + goto free_st;
> + }
> + }
> +
> +
> + for (i = 0; i < insn_cnt; i++) {
> + if (st[i] != 4) {
> + verbose("unreachable insn %d\n", i);
> + ret = -EINVAL;
> + goto free_st;
> + }
> + }
> +
> +free_st:
> + kfree(st);
> + kfree(stack);
> + return ret;
> +}
> +
> +/* compare two verifier states
> + *
> + * all states stored in state_list are known to be valid, since
> + * verifier reached 'bpf_exit' instruction through them
> + *
> + * this function is called when verifier exploring different branches of
> + * execution popped from the state stack. If it sees an old state that has
> + * more strict register state and more strict stack state then this execution
> + * branch doesn't need to be explored further, since verifier already
> + * concluded that more strict state leads to valid finish.
> + *
> + * Therefore two states are equivalent if register state is more conservative
> + * and explored stack state is more conservative than the current one.
> + * Example:
> + * explored current
> + * (slot1=INV slot2=MISC) == (slot1=MISC slot2=MISC)
> + * (slot1=MISC slot2=MISC) != (slot1=INV slot2=MISC)
> + *
> + * In other words if current stack state (one being explored) has more
> + * valid slots than old one that already passed validation, it means
> + * the verifier can stop exploring and conclude that current state is valid too
> + *
> + * Similarly with registers. If explored state has register type as invalid
> + * whereas register type in current state is meaningful, it means that
> + * the current state will reach 'bpf_exit' instruction safely
> + */
> +static bool states_equal(struct verifier_state *old, struct verifier_state *cur)
> +{
> + int i;
> +
> + for (i = 0; i < MAX_BPF_REG; i++) {
> + if (memcmp(&old->regs[i], &cur->regs[i],
> + sizeof(old->regs[0])) != 0) {
> + if (!old->regs[i].read_ok)
> + continue;
> + if (old->regs[i].ptr == INVALID_PTR)
> + continue;
> + return false;
> + }
> + }
> +
> + for (i = 0; i < MAX_BPF_STACK; i++) {
> + if (memcmp(&old->stack[i], &cur->stack[i],
> + sizeof(old->stack[0])) != 0) {
> + if (old->stack[i].type == STACK_INVALID)
> + continue;
> + return false;
> + }
> + }
> + return true;
> +}
> +
> +static int is_state_visited(struct verifier_env *env, int insn_idx)
> +{
> + struct verifier_state_list *new_sl;
> + struct verifier_state_list *sl;
> +
> + sl = env->branch_landing[insn_idx];
> + if (!sl)
> + /* no branch jump to this insn, ignore it */
> + return 0;
> +
> + while (sl != STATE_END) {
> + if (states_equal(&sl->state, &env->cur_state))
> + /* reached equivalent register/stack state,
> + * prune the search
> + */
> + return 1;
> + sl = sl->next;
> + }
> + new_sl = kmalloc(sizeof(struct verifier_state_list), GFP_KERNEL);
> +
> + if (!new_sl)
> + /* ignore ENOMEM, it doesn't affect correctness */
> + return 0;
> +
> + /* add new state to the head of linked list */
> + memcpy(&new_sl->state, &env->cur_state, sizeof(env->cur_state));
> + new_sl->next = env->branch_landing[insn_idx];
> + env->branch_landing[insn_idx] = new_sl;
> + return 0;
> +}
> +
> +static int do_check(struct verifier_env *env)
> +{
> + struct verifier_state *state = &env->cur_state;
> + struct sock_filter_int *insns = env->prog->insnsi;
> + struct reg_state *regs = state->regs;
> + int insn_cnt = env->prog->len;
> + int insn_idx, prev_insn_idx = 0;
> + int insn_processed = 0;
> + bool do_print_state = false;
> +
> + init_reg_state(regs);
> + insn_idx = 0;
> + for (;;) {
> + struct sock_filter_int *insn;
> + u8 class;
> +
> + if (insn_idx >= insn_cnt) {
> + verbose("invalid insn idx %d insn_cnt %d\n",
> + insn_idx, insn_cnt);
> + return -EFAULT;
> + }
> +
> + insn = &insns[insn_idx];
> + class = BPF_CLASS(insn->code);
> +
> + if (++insn_processed > 32768) {
> + verbose("BPF program is too large. Proccessed %d insn\n",
> + insn_processed);
> + return -E2BIG;
> + }
> +
> + if (is_state_visited(env, insn_idx)) {
> + if (verbose_on) {
> + if (do_print_state)
> + pr_cont("\nfrom %d to %d: safe\n",
> + prev_insn_idx, insn_idx);
> + else
> + pr_cont("%d: safe\n", insn_idx);
> + }
> + goto process_bpf_exit;
> + }
> +
> + if (verbose_on && do_print_state) {
> + pr_cont("\nfrom %d to %d:", prev_insn_idx, insn_idx);
> + pr_cont_verifier_state(env);
> + do_print_state = false;
> + }
> +
> + if (verbose_on) {
> + pr_cont("%d: ", insn_idx);
> + pr_cont_bpf_insn(insn);
> + }
> +
> + if (class == BPF_ALU || class == BPF_ALU64) {
> + _(check_alu_op(regs, insn));
> +
> + } else if (class == BPF_LDX) {
> + if (BPF_MODE(insn->code) != BPF_MEM)
> + return -EINVAL;
> +
> + /* check src operand */
> + _(check_reg_arg(regs, insn->src_reg, 1));
> +
> + _(check_mem_access(env, insn->src_reg, insn->off,
> + BPF_SIZE(insn->code), BPF_READ,
> + insn->dst_reg));
> +
> + /* dest reg state will be updated by mem_access */
> +
> + } else if (class == BPF_STX) {
> + /* check src1 operand */
> + _(check_reg_arg(regs, insn->src_reg, 1));
> + /* check src2 operand */
> + _(check_reg_arg(regs, insn->dst_reg, 1));
> + _(check_mem_access(env, insn->dst_reg, insn->off,
> + BPF_SIZE(insn->code), BPF_WRITE,
> + insn->src_reg));
> +
> + } else if (class == BPF_ST) {
> + if (BPF_MODE(insn->code) != BPF_MEM)
> + return -EINVAL;
> + /* check src operand */
> + _(check_reg_arg(regs, insn->dst_reg, 1));
> + _(check_mem_access(env, insn->dst_reg, insn->off,
> + BPF_SIZE(insn->code), BPF_WRITE,
> + -1));
> +
> + } else if (class == BPF_JMP) {
> + u8 opcode = BPF_OP(insn->code);
> +
> + if (opcode == BPF_CALL) {
> + _(check_call(env, insn->imm));
> + } else if (opcode == BPF_JA) {
> + if (BPF_SRC(insn->code) != BPF_X)
> + return -EINVAL;
> + insn_idx += insn->off + 1;
> + continue;
> + } else if (opcode == BPF_EXIT) {
> + /* eBPF calling convetion is such that R0 is used
> + * to return the value from eBPF program.
> + * Make sure that it's readable at this time
> + * of bpf_exit, which means that program wrote
> + * something into it earlier
> + */
> + _(check_reg_arg(regs, BPF_REG_0, 1));
> +process_bpf_exit:
> + insn_idx = pop_stack(env, &prev_insn_idx);
> + if (insn_idx < 0) {
> + break;
> + } else {
> + do_print_state = true;
> + continue;
> + }
> + } else {
> + _(check_cond_jmp_op(env, insn, &insn_idx));
> + }
> + } else if (class == BPF_LD) {
> + _(check_ld_abs(env, insn));
> + } else {
> + verbose("unknown insn class %d\n", class);
> + return -EINVAL;
> + }
> +
> + insn_idx++;
> + }
> +
> + return 0;
> +}
> +
> +static void free_states(struct verifier_env *env, int insn_cnt)
> +{
> + struct verifier_state_list *sl, *sln;
> + int i;
> +
> + for (i = 0; i < insn_cnt; i++) {
> + sl = env->branch_landing[i];
> +
> + if (sl)
> + while (sl != STATE_END) {
> + sln = sl->next;
> + kfree(sl);
> + sl = sln;
> + }
> + }
> +
> + kfree(env->branch_landing);
> +}
> +
> +int bpf_check(struct sk_filter *prog)
> +{
> + struct verifier_env *env;
> + int ret;
> +
> + if (prog->len <= 0 || prog->len > BPF_MAXINSNS)
> + return -E2BIG;
> +
> + env = kzalloc(sizeof(struct verifier_env), GFP_KERNEL);
> + if (!env)
> + return -ENOMEM;
> +
> + verbose_on = false;
> +retry:
> + env->prog = prog;
> + env->branch_landing = kcalloc(prog->len,
> + sizeof(struct verifier_state_list *),
> + GFP_KERNEL);
> +
> + if (!env->branch_landing) {
> + kfree(env);
> + return -ENOMEM;
> + }
> +
> + ret = check_cfg(env);
> + if (ret < 0)
> + goto free_env;
> +
> + ret = do_check(env);
> +
> +free_env:
> + while (pop_stack(env, NULL) >= 0);
> + free_states(env, prog->len);
> +
> + if (ret < 0 && !verbose_on && capable(CAP_SYS_ADMIN)) {
> + /* verification failed, redo it with verbose on */
> + memset(env, 0, sizeof(struct verifier_env));
> + verbose_on = true;
> + goto retry;
> + }
> +
> + if (ret == 0 && env->used_map_cnt) {
> + /* if program passed verifier, update used_maps in bpf_prog_info */
> + prog->info->used_maps = kmalloc_array(env->used_map_cnt,
> + sizeof(u32), GFP_KERNEL);
> + if (!prog->info->used_maps) {
> + kfree(env);
> + return -ENOMEM;
> + }
> + memcpy(prog->info->used_maps, env->used_maps,
> + sizeof(u32) * env->used_map_cnt);
> + prog->info->used_map_cnt = env->used_map_cnt;
> + }
> +
> + kfree(env);
> + return ret;
> +}
> --
> 1.7.9.5
>
^ permalink raw reply
* Re: [patch 3/4] timerfd: Implement timerfd_ioctl method to restore timerfd_ctx::ticks
From: Cyrill Gorcunov @ 2014-07-02 19:36 UTC (permalink / raw)
To: Arnd Bergmann
Cc: Christopher Covington, linux-kernel-u79uwXL29TY76Z2rM5mHXA,
linux-api-u79uwXL29TY76Z2rM5mHXA, Michael Kerrisk,
Thomas Gleixner, Andrew Morton, Andrey Vagin, Pavel Emelyanov,
Vladimir Davydov, Linux ARM kernel mailing list
In-Reply-To: <4188254.Av1Z2pQssC@wuerfel>
Updated variant, thanks a lot for feedback!
---
From: Cyrill Gorcunov <gorcunov-GEFAQzZX7r8dnm+yROfE0A@public.gmane.org>
Subject: timerfd: Implement timerfd_ioctl method to restore timerfd_ctx::ticks, v3
The read() of timerfd files allows to fetch the number of timer ticks
while there is no way to set it back from userspace.
To restore the timer's state as it was at checkpoint moment we need
a path to bring @ticks back. Initially I thought about writing ticks
back via write() interface but it seems such API is somehow obscure.
Instead implement timerfd_ioctl() method with TFD_IOC_SET_TICKS
command which allows to adjust @ticks into non-zero value waking
up the waiters.
I wrapped code with CONFIG_CHECKPOINT_RESTORE which can be
dropped off if there users except c/r camp appear.
v2 (by akpm@):
- Use define timerfd_ioctl NULL for non c/r config
v3:
- Use copy_from_user for @ticks fetching since
not all arch support get_user for 8 byte argument
CC: Thomas Gleixner <tglx-hfZtesqFncYOwBW4kG4KsQ@public.gmane.org>
CC: Andrew Morton <akpm-de/tnXTf+JLsfHDXvbKv3WD2FQJk+8+b@public.gmane.org>
CC: Andrey Vagin <avagin-GEFAQzZX7r8dnm+yROfE0A@public.gmane.org>
CC: Arnd Bergmann <arnd-r2nGTMty4D4@public.gmane.org>
CC: Christopher Covington <cov-sgV2jX0FEOL9JmXXK+q4OQ@public.gmane.org>
CC: Pavel Emelyanov <xemul-bzQdu9zFT3WakBO8gow8eQ@public.gmane.org>
CC: Vladimir Davydov <vdavydov-bzQdu9zFT3WakBO8gow8eQ@public.gmane.org>
Signed-off-by: Cyrill Gorcunov <gorcunov-GEFAQzZX7r8dnm+yROfE0A@public.gmane.org>
---
fs/timerfd.c | 37 +++++++++++++++++++++++++++++++++++++
include/linux/timerfd.h | 5 +++++
2 files changed, 42 insertions(+)
Index: linux-2.6.git/fs/timerfd.c
===================================================================
--- linux-2.6.git.orig/fs/timerfd.c
+++ linux-2.6.git/fs/timerfd.c
@@ -315,12 +315,49 @@ static int timerfd_show(struct seq_file
#define timerfd_show NULL
#endif
+#ifdef CONFIG_CHECKPOINT_RESTORE
+static long timerfd_ioctl(struct file *file, unsigned int cmd, unsigned long arg)
+{
+ struct timerfd_ctx *ctx = file->private_data;
+ int ret = 0;
+
+ switch (cmd) {
+ case TFD_IOC_SET_TICKS: {
+ u64 ticks;
+
+ if (copy_from_user(&ticks, (u64 __user *)arg, sizeof(ticks)))
+ return -EFAULT;
+ if (!ticks)
+ return -EINVAL;
+
+ spin_lock_irq(&ctx->wqh.lock);
+ if (!timerfd_canceled(ctx)) {
+ ctx->ticks = ticks;
+ if (ticks)
+ wake_up_locked(&ctx->wqh);
+ } else
+ ret = -ECANCELED;
+ spin_unlock_irq(&ctx->wqh.lock);
+ break;
+ }
+ default:
+ ret = -ENOTTY;
+ break;
+ }
+
+ return ret;
+}
+#else
+#define timerfd_ioctl NULL
+#endif
+
static const struct file_operations timerfd_fops = {
.release = timerfd_release,
.poll = timerfd_poll,
.read = timerfd_read,
.llseek = noop_llseek,
.show_fdinfo = timerfd_show,
+ .unlocked_ioctl = timerfd_ioctl,
};
static int timerfd_fget(int fd, struct fd *p)
Index: linux-2.6.git/include/linux/timerfd.h
===================================================================
--- linux-2.6.git.orig/include/linux/timerfd.h
+++ linux-2.6.git/include/linux/timerfd.h
@@ -11,6 +11,9 @@
/* For O_CLOEXEC and O_NONBLOCK */
#include <linux/fcntl.h>
+/* For _IO helpers */
+#include <linux/ioctl.h>
+
/*
* CAREFUL: Check include/asm-generic/fcntl.h when defining
* new flags, since they might collide with O_* ones. We want
@@ -29,4 +32,6 @@
/* Flags for timerfd_settime. */
#define TFD_SETTIME_FLAGS (TFD_TIMER_ABSTIME | TFD_TIMER_CANCEL_ON_SET)
+#define TFD_IOC_SET_TICKS _IOW('T', 0, u64)
+
#endif /* _LINUX_TIMERFD_H */
^ permalink raw reply
* Re: [patch 3/4] timerfd: Implement timerfd_ioctl method to restore timerfd_ctx::ticks
From: Cyrill Gorcunov @ 2014-07-02 19:07 UTC (permalink / raw)
To: Arnd Bergmann
Cc: Christopher Covington, linux-kernel-u79uwXL29TY76Z2rM5mHXA,
linux-api-u79uwXL29TY76Z2rM5mHXA, Michael Kerrisk,
Thomas Gleixner, Andrew Morton, Andrey Vagin, Pavel Emelyanov,
Vladimir Davydov, Linux ARM kernel mailing list
In-Reply-To: <4188254.Av1Z2pQssC@wuerfel>
On Wed, Jul 02, 2014 at 09:01:02PM +0200, Arnd Bergmann wrote:
> > >
> > > 64-bit get_user is currently unsupported on ARM, although it appears work is
> > > ongoing [1].
> > >
> > > 1. https://lkml.org/lkml/2014/6/17/260
> >
> > Thanks for info, Christopher! What arm camp is using then, copy-from-user?
> >
>
> copy_from_user should work on all architectures. I believe a 64-bit get_user
> is currently unsupported on most 32-bit architectures, x86-32 being a notable
> exception.
Thanks, I'll update.
^ permalink raw reply
* Re: [patch 3/4] timerfd: Implement timerfd_ioctl method to restore timerfd_ctx::ticks
From: Arnd Bergmann @ 2014-07-02 19:01 UTC (permalink / raw)
To: Cyrill Gorcunov
Cc: Christopher Covington, linux-kernel, linux-api, Michael Kerrisk,
Thomas Gleixner, Andrew Morton, Andrey Vagin, Pavel Emelyanov,
Vladimir Davydov, Linux ARM kernel mailing list
In-Reply-To: <20140702170416.GG12440@moon>
On Wednesday 02 July 2014 21:04:16 Cyrill Gorcunov wrote:
> On Wed, Jul 02, 2014 at 12:49:51PM -0400, Christopher Covington wrote:
> > >
> > > +#ifdef CONFIG_CHECKPOINT_RESTORE
> > > +static long timerfd_ioctl(struct file *file, unsigned int cmd, unsigned long arg)
> > > +{
> > > + struct timerfd_ctx *ctx = file->private_data;
> > > + int ret = 0;
> > > +
> > > + switch (cmd) {
> > > + case TFD_IOC_SET_TICKS: {
> > > + u64 ticks;
> > > +
> > > + if (get_user(ticks, (u64 __user *)arg))
> >
> > 64-bit get_user is currently unsupported on ARM, although it appears work is
> > ongoing [1].
> >
> > 1. https://lkml.org/lkml/2014/6/17/260
>
> Thanks for info, Christopher! What arm camp is using then, copy-from-user?
>
copy_from_user should work on all architectures. I believe a 64-bit get_user
is currently unsupported on most 32-bit architectures, x86-32 being a notable
exception.
Arnd
^ permalink raw reply
* Re: [PATCH 09/11] capsicum: implementations of new LSM hooks
From: David Drysdale @ 2014-07-02 17:09 UTC (permalink / raw)
To: Paul Moore
Cc: Andy Lutomirski, LSM List,
linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org,
Greg Kroah-Hartman, Alexander Viro, Meredydd Luff, Kees Cook,
James Morris, Linux API
In-Reply-To: <1871630.hB3tXi0r3a@sifl>
On Wed, Jul 2, 2014 at 2:49 PM, Paul Moore <paul-r2n+y4ga6xFZroRs9YW3xA@public.gmane.org> wrote:
> On Monday, June 30, 2014 09:05:38 AM Andy Lutomirski wrote:
>> On Mon, Jun 30, 2014 at 3:28 AM, David Drysdale <drysdale-hpIqsD4AKlfQT0dZR+AlfA@public.gmane.org> wrote:
>> > If the LSM does not provide implementations of the .file_lookup and
>> > .file_install LSM hooks, always use the Capsicum implementations.
>> >
>> > The Capsicum implementation of file_lookup checks for a Capsicum
>> > capability wrapper file and unwraps to if the appropriate rights
>> > are available.
>> >
>> > The Capsicum implementation of file_install checks whether the file
>> > has restricted rights associated with it. If it does, it is replaced
>> > with a Capsicum capability wrapper file before installation into the
>> > fdtable.
>>
>> I think I fall on the "no LSM" side of the fence. This kind of stuff
>> should be available regardless of selected LSM (as it is in your
>> code) ...
>
> I agree. Looking quickly at the patches, the code seems to take an odd
> approach of living largely outside the LSM framework, but then relying on a
> couple of LSM hooks. Capsicum should either live fully as a LSM or fully
> outside of it, this mix seems a bit silly to me.
Yeah, the end result was definitely a bit odd, hence the queries in the
cover email. The consensus so far seems to be that they don't help,
so I'll remove the gratuitous LSM hooks on the next iteration.
Thanks,
David
> --
> paul moore
> www.paul-moore.com
>
^ permalink raw reply
* Re: [patch 3/4] timerfd: Implement timerfd_ioctl method to restore timerfd_ctx::ticks
From: Cyrill Gorcunov @ 2014-07-02 17:04 UTC (permalink / raw)
To: Christopher Covington
Cc: linux-kernel-u79uwXL29TY76Z2rM5mHXA,
linux-api-u79uwXL29TY76Z2rM5mHXA, Michael Kerrisk,
Thomas Gleixner, Andrew Morton, Andrey Vagin, Pavel Emelyanov,
Vladimir Davydov, Linux ARM kernel mailing list
In-Reply-To: <53B4382F.9030908-sgV2jX0FEOL9JmXXK+q4OQ@public.gmane.org>
On Wed, Jul 02, 2014 at 12:49:51PM -0400, Christopher Covington wrote:
> >
> > +#ifdef CONFIG_CHECKPOINT_RESTORE
> > +static long timerfd_ioctl(struct file *file, unsigned int cmd, unsigned long arg)
> > +{
> > + struct timerfd_ctx *ctx = file->private_data;
> > + int ret = 0;
> > +
> > + switch (cmd) {
> > + case TFD_IOC_SET_TICKS: {
> > + u64 ticks;
> > +
> > + if (get_user(ticks, (u64 __user *)arg))
>
> 64-bit get_user is currently unsupported on ARM, although it appears work is
> ongoing [1].
>
> 1. https://lkml.org/lkml/2014/6/17/260
Thanks for info, Christopher! What arm camp is using then, copy-from-user?
^ permalink raw reply
* Re: [patch 3/4] timerfd: Implement timerfd_ioctl method to restore timerfd_ctx::ticks
From: Christopher Covington @ 2014-07-02 16:49 UTC (permalink / raw)
To: Cyrill Gorcunov
Cc: linux-kernel, linux-api, Michael Kerrisk, Thomas Gleixner,
Andrew Morton, Andrey Vagin, Pavel Emelyanov, Vladimir Davydov,
Linux ARM kernel mailing list
In-Reply-To: <20140624220351.GZ2095@moon>
Hi Cyrill,
On 06/24/2014 06:03 PM, Cyrill Gorcunov wrote:
> The read() of timerfd files allows to fetch the number of timer ticks
> while there is no way to set it back from userspace.
>
> To restore the timer's state as it was at checkpoint moment we need
> a path to bring @ticks back. Initially I thought about writing ticks
> back via write() interface but it seems such API is somehow obscure.
>
> Instead implement timerfd_ioctl() method with TFD_IOC_SET_TICKS
> command which allows to adjust @ticks into non-zero value waking
> up the waiters.
>
> I wrapped code with CONFIG_CHECKPOINT_RESTORE which can be
> dropped off if there users except c/r camp appear.
>
> v2 (by akpm@):
> -Use define timerfd_ioctl NULL for non c/r config
>
> CC: Thomas Gleixner <tglx@linutronix.de>
> CC: Andrew Morton <akpm@linux-foundation.org>
> CC: Andrey Vagin <avagin@openvz.org>
> CC: Pavel Emelyanov <xemul@parallels.com>
> CC: Vladimir Davydov <vdavydov@parallels.com>
> Signed-off-by: Cyrill Gorcunov <gorcunov@openvz.org>
> ---
>
> A nit fixed for for non c/r config in timerfd_ioctl declaration
>
> fs/timerfd.c | 37 +++++++++++++++++++++++++++++++++++++
> include/linux/timerfd.h | 5 +++++
> 2 files changed, 42 insertions(+)
>
> Index: linux-2.6.git/fs/timerfd.c
> ===================================================================
> --- linux-2.6.git.orig/fs/timerfd.c
> +++ linux-2.6.git/fs/timerfd.c
> @@ -315,12 +315,49 @@ static int timerfd_show(struct seq_file
> #define timerfd_show NULL
> #endif
>
> +#ifdef CONFIG_CHECKPOINT_RESTORE
> +static long timerfd_ioctl(struct file *file, unsigned int cmd, unsigned long arg)
> +{
> + struct timerfd_ctx *ctx = file->private_data;
> + int ret = 0;
> +
> + switch (cmd) {
> + case TFD_IOC_SET_TICKS: {
> + u64 ticks;
> +
> + if (get_user(ticks, (u64 __user *)arg))
64-bit get_user is currently unsupported on ARM, although it appears work is
ongoing [1].
1. https://lkml.org/lkml/2014/6/17/260
Regards,
Christopher
--
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum,
hosted by the Linux Foundation.
^ permalink raw reply
* Re: [PATCH RFC net-next 00/14] BPF syscall, maps, verifier, samples
From: Kees Cook @ 2014-07-02 16:39 UTC (permalink / raw)
To: Daniel Borkmann
Cc: Alexei Starovoitov, David S. Miller, Ingo Molnar, Linus Torvalds,
Steven Rostedt, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Arnaldo Carvalho de Melo, Jiri Olsa, Thomas Gleixner,
H. Peter Anvin, Andrew Morton, Linux API, Network Development,
LKML
In-Reply-To: <53B260B3.4040108-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
On Tue, Jul 1, 2014 at 12:18 AM, Daniel Borkmann <dborkman-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
> On 07/01/2014 01:09 AM, Kees Cook wrote:
>>
>> On Fri, Jun 27, 2014 at 5:05 PM, Alexei Starovoitov <ast-uqk4Ao+rVK5Wk0Htik3J/w@public.gmane.org>
>> wrote:
>>>
>>> Hi All,
>>>
>>> this patch set demonstrates the potential of eBPF.
>>>
>>> First patch "net: filter: split filter.c into two files" splits eBPF
>>> interpreter
>>> out of networking into kernel/bpf/. The goal for BPF subsystem is to be
>>> usable
>>> in NET-less configuration. Though the whole set is marked is RFC, the 1st
>>> patch
>>> is good to go. Similar version of the patch that was posted few weeks
>>> ago, but
>>> was deferred. I'm assuming due to lack of forward visibility. I hope that
>>> this
>>> patch set shows what eBPF is capable of and where it's heading.
>>>
>>> Other patches expose eBPF instruction set to user space and introduce
>>> concepts
>>> of maps and programs accessible via syscall.
>>>
>>> 'maps' is a generic storage of different types for sharing data between
>>> kernel
>>> and userspace. Maps are referrenced by global id. Root can create
>>> multiple
>>> maps of different types where key/value are opaque bytes of data. It's up
>>> to
>>> user space and eBPF program to decide what they store in the maps.
>>>
>>> eBPF programs are similar to kernel modules. They live in global space
>>> and
>>> have unique prog_id. Each program is a safe run-to-completion set of
>>> instructions. eBPF verifier statically determines that the program
>>> terminates
>>> and safe to execute. During verification the program takes a hold of maps
>>> that it intends to use, so selected maps cannot be removed until program
>>> is
>>> unloaded. The program can be attached to different events. These events
>>> can
>>> be packets, tracepoint events and other types in the future. New event
>>> triggers
>>> execution of the program which may store information about the event in
>>> the maps.
>>> Beyond storing data the programs may call into in-kernel helper functions
>>> which may, for example, dump stack, do trace_printk or other forms of
>>> live
>>> kernel debugging. Same program can be attached to multiple events.
>>> Different
>>> programs can access the same map:
>>>
>>> tracepoint tracepoint tracepoint sk_buff sk_buff
>>> event A event B event C on eth0 on eth1
>>> | | | | |
>>> | | | | |
>>> --> tracing <-- tracing socket socket
>>> prog_1 prog_2 prog_3 prog_4
>>> | | | |
>>> |--- -----| |-------| map_3
>>> map_1 map_2
>>>
>>> User space (via syscall) and eBPF programs access maps concurrently.
>>>
>>> Last two patches are sample code. 1st demonstrates stateful packet
>>> inspection.
>>> It counts tcp and udp packets on eth0. Should be easy to see how this
>>> eBPF
>>> framework can be used for network analytics.
>>> 2nd sample does simple 'drop monitor'. It attaches to kfree_skb
>>> tracepoint
>>> event and counts number of packet drops at particular $pc location.
>>> User space periodically summarizes what eBPF programs recorded.
>>> In these two samples the eBPF programs are tiny and written in
>>> 'assembler'
>>> with macroses. More complex programs can be written C (llvm backend is
>>> not
>>> part of this diff to reduce 'huge' perception).
>>> Since eBPF is fully JITed on x64, the cost of running eBPF program is
>>> very
>>> small even for high frequency events. Here are the numbers comparing
>>> flow_dissector in C vs eBPF:
>>> x86_64 skb_flow_dissect() same skb (all cached) - 42 nsec per
>>> call
>>> x86_64 skb_flow_dissect() different skbs (cache misses) - 141 nsec per
>>> call
>>> eBPF+jit skb_flow_dissect() same skb (all cached) - 51 nsec per
>>> call
>>> eBPF+jit skb_flow_dissect() different skbs (cache misses) - 135 nsec per
>>> call
>>>
>>> Detailed explanation on eBPF verifier and safety is in patch 08/14
>>
>>
>> This is very exciting! Thanks for working on it. :)
>>
>> Between the new eBPF syscall and the new seccomp syscall, I'm really
>> looking forward to using lookup tables for seccomp filters. Under
>> certain types of filters, we'll likely see some non-trivial
>> performance improvements.
>
> Well, if I read this correctly, the eBPF syscall lets you set up maps, etc,
> but the only way to attach eBPF is via setsockopt for network filters right
> now (and via tracing). Seccomp will still make use of classic BPF, so you
> won't be able to use it there.
Currently, yes. But once this is in, and the new seccomp syscall is
in, we can add a SECCOMP_FILTER_EBPF flag to the "flags" field to
instruct seccomp to load an eBPF instead of a classic BPF. I'm excited
for the future. :)
-Kees
--
Kees Cook
Chrome OS Security
^ permalink raw reply
* Re: [PATCH v2] Documentation: sysfs-bus-usb: update power/persist description
From: Alan Stern @ 2014-07-02 14:36 UTC (permalink / raw)
To: Paul Bolle
Cc: Greg Kroah-Hartman, linux-api-u79uwXL29TY76Z2rM5mHXA,
linux-usb-u79uwXL29TY76Z2rM5mHXA,
linux-kernel-u79uwXL29TY76Z2rM5mHXA
In-Reply-To: <1404295845.12021.29.camel@x220>
On Wed, 2 Jul 2014, Paul Bolle wrote:
> There's no power/persist file for hubs. And CONFIG_USB_PERSIST was
> removed in v2.6.26. Update the description of power/persist accordingly.
> Also remove the line on its default value. It is not entirely correct, as
> CONFIG_USB_DEFAULT_PERSIST and the USB_QUIRK_RESET flag influence the
> default. It is not needed to understand this file anyhow.
>
> Signed-off-by: Paul Bolle <pebolle-IWqWACnzNjzz+pZb47iToQ@public.gmane.org>
> ---
> v2: incorporate Alan's feedback. The clearest way to do that was to not
> mention the default value at all. Trying to do handle the default
> correctly made the text way too complicated. I hope Alan agrees.
>
> Perhaps the line on hubs should not be added, as the text now states
> that device directories "can" contain this file.
>
> Documentation/ABI/stable/sysfs-bus-usb | 14 +++++++-------
> 1 file changed, 7 insertions(+), 7 deletions(-)
>
> diff --git a/Documentation/ABI/stable/sysfs-bus-usb b/Documentation/ABI/stable/sysfs-bus-usb
> index a6b685724740..e2bc700a6f9c 100644
> --- a/Documentation/ABI/stable/sysfs-bus-usb
> +++ b/Documentation/ABI/stable/sysfs-bus-usb
> @@ -3,13 +3,13 @@ Date: May 2007
> KernelVersion: 2.6.23
> Contact: Alan Stern <stern-nwvwT67g6+6dFdvTe/nMLpVzexx5G7lz@public.gmane.org>
> Description:
> - If CONFIG_USB_PERSIST is set, then each USB device directory
> - will contain a file named power/persist. The file holds a
> - boolean value (0 or 1) indicating whether or not the
> - "USB-Persist" facility is enabled for the device. Since the
> - facility is inherently dangerous, it is disabled by default
> - for all devices except hubs. For more information, see
> - Documentation/usb/persist.txt.
> + USB device directories can contain a file named power/persist.
> + The file holds a boolean value (0 or 1) indicating whether or
> + not the "USB-Persist" facility is enabled for the device. For
> + hubs this facility is always enabled and their device
> + directories will not contain this file.
> +
> + For more information, see Documentation/usb/persist.txt.
>
> What: /sys/bus/usb/devices/.../power/autosuspend
> Date: March 2007
>
Acked-by: Alan Stern <stern-nwvwT67g6+6dFdvTe/nMLpVzexx5G7lz@public.gmane.org>
^ permalink raw reply
* Re: [PATCH 09/11] capsicum: implementations of new LSM hooks
From: Paul Moore @ 2014-07-02 13:49 UTC (permalink / raw)
To: David Drysdale
Cc: Andy Lutomirski, LSM List,
linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org,
Greg Kroah-Hartman, Alexander Viro, Meredydd Luff, Kees Cook,
James Morris, Linux API
In-Reply-To: <CALCETrUBCL1jKfooLaqrJCb-uYrMwYPQL2v-M04NTVf2LoD_fw-JsoAwUIsXosN+BqQ9rBEUg@public.gmane.org>
On Monday, June 30, 2014 09:05:38 AM Andy Lutomirski wrote:
> On Mon, Jun 30, 2014 at 3:28 AM, David Drysdale <drysdale-hpIqsD4AKlfQT0dZR+AlfA@public.gmane.org> wrote:
> > If the LSM does not provide implementations of the .file_lookup and
> > .file_install LSM hooks, always use the Capsicum implementations.
> >
> > The Capsicum implementation of file_lookup checks for a Capsicum
> > capability wrapper file and unwraps to if the appropriate rights
> > are available.
> >
> > The Capsicum implementation of file_install checks whether the file
> > has restricted rights associated with it. If it does, it is replaced
> > with a Capsicum capability wrapper file before installation into the
> > fdtable.
>
> I think I fall on the "no LSM" side of the fence. This kind of stuff
> should be available regardless of selected LSM (as it is in your
> code) ...
I agree. Looking quickly at the patches, the code seems to take an odd
approach of living largely outside the LSM framework, but then relying on a
couple of LSM hooks. Capsicum should either live fully as a LSM or fully
outside of it, this mix seems a bit silly to me.
--
paul moore
www.paul-moore.com
^ permalink raw reply
* [PATCH v2] Documentation: sysfs-bus-usb: update power/persist description
From: Paul Bolle @ 2014-07-02 10:10 UTC (permalink / raw)
To: Greg Kroah-Hartman, Alan Stern
Cc: linux-api-u79uwXL29TY76Z2rM5mHXA,
linux-usb-u79uwXL29TY76Z2rM5mHXA,
linux-kernel-u79uwXL29TY76Z2rM5mHXA
In-Reply-To: <Pine.LNX.4.44L0.1406241316550.888-100000-IYeN2dnnYyZXsRXLowluHWD2FQJk+8+b@public.gmane.org>
There's no power/persist file for hubs. And CONFIG_USB_PERSIST was
removed in v2.6.26. Update the description of power/persist accordingly.
Also remove the line on its default value. It is not entirely correct, as
CONFIG_USB_DEFAULT_PERSIST and the USB_QUIRK_RESET flag influence the
default. It is not needed to understand this file anyhow.
Signed-off-by: Paul Bolle <pebolle-IWqWACnzNjzz+pZb47iToQ@public.gmane.org>
---
v2: incorporate Alan's feedback. The clearest way to do that was to not
mention the default value at all. Trying to do handle the default
correctly made the text way too complicated. I hope Alan agrees.
Perhaps the line on hubs should not be added, as the text now states
that device directories "can" contain this file.
Documentation/ABI/stable/sysfs-bus-usb | 14 +++++++-------
1 file changed, 7 insertions(+), 7 deletions(-)
diff --git a/Documentation/ABI/stable/sysfs-bus-usb b/Documentation/ABI/stable/sysfs-bus-usb
index a6b685724740..e2bc700a6f9c 100644
--- a/Documentation/ABI/stable/sysfs-bus-usb
+++ b/Documentation/ABI/stable/sysfs-bus-usb
@@ -3,13 +3,13 @@ Date: May 2007
KernelVersion: 2.6.23
Contact: Alan Stern <stern-nwvwT67g6+6dFdvTe/nMLpVzexx5G7lz@public.gmane.org>
Description:
- If CONFIG_USB_PERSIST is set, then each USB device directory
- will contain a file named power/persist. The file holds a
- boolean value (0 or 1) indicating whether or not the
- "USB-Persist" facility is enabled for the device. Since the
- facility is inherently dangerous, it is disabled by default
- for all devices except hubs. For more information, see
- Documentation/usb/persist.txt.
+ USB device directories can contain a file named power/persist.
+ The file holds a boolean value (0 or 1) indicating whether or
+ not the "USB-Persist" facility is enabled for the device. For
+ hubs this facility is always enabled and their device
+ directories will not contain this file.
+
+ For more information, see Documentation/usb/persist.txt.
What: /sys/bus/usb/devices/.../power/autosuspend
Date: March 2007
--
1.9.3
^ permalink raw reply related
* RE: [PATCH RFC net-next 08/14] bpf: add eBPF verifier
From: David Laight @ 2014-07-02 8:11 UTC (permalink / raw)
To: 'Alexei Starovoitov', Daniel Borkmann
Cc: David S. Miller, Ingo Molnar, Linus Torvalds, Steven Rostedt,
Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Arnaldo Carvalho de Melo, Jiri Olsa, Thomas Gleixner,
H. Peter Anvin, Andrew Morton, Kees Cook, Linux API,
Network Development, LKML
In-Reply-To: <CAMEtUuyc3+jrxG4r4=fk=Gc9OMhO8a2X1oyWPx1LsKzewVf01w@mail.gmail.com>
From: Alexei Starovoitov
...
> >> +#define _(OP) ({ int ret = OP; if (ret < 0) return ret; })
...
> >> + _(get_map_info(env, map_id, &map));
> >
> > Nit: such macros should be removed, please.
>
> It may surely look unconventional, but alternative is to replace
> every usage of _ macro with:
> err =
> if (err)
> return err;
>
> and since this macro is used 38 times, it will add ~120 unnecessary
> lines that will only make code much harder to follow.
> I tried not using macro and results were not pleasing.
The problem is that they are hidden control flow.
As such they make flow analysis harder for the casual reader.
The extra lines really shouldn't matter.
David
^ permalink raw reply
* Re: [PATCH RFC net-next 11/14] tracing: allow eBPF programs to be attached to events
From: Alexei Starovoitov @ 2014-07-02 7:29 UTC (permalink / raw)
To: Namhyung Kim
Cc: David S. Miller, Ingo Molnar, Linus Torvalds, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Arnaldo Carvalho de Melo, Jiri Olsa, Thomas Gleixner,
H. Peter Anvin, Andrew Morton, Kees Cook, Linux API,
Network Development, LKML
In-Reply-To: <CAM9d7cisUq9nJbSXZMtD+nQ_g+ZCKSsu_ghRDZY9vvkq51oiKQ@mail.gmail.com>
On Tue, Jul 1, 2014 at 11:39 PM, Namhyung Kim <namhyung@kernel.org> wrote:
> On Wed, Jul 2, 2014 at 3:14 PM, Alexei Starovoitov <ast@plumgrid.com> wrote:
>>
>> Can manipulate what at compile time? Entry records of tracepoints are
>> hard coded based on the event. For verifier it's easier to treat all
>> tracepoint events as they received the same 'struct bpf_context'
>> of N arguments then the same program can be attached to multiple
>> tracepoint events at the same time.
>
> I was thinking about perf creates a bpf program for filtering some
> events like recording kfree_skb if protocol == xx. So perf can
> calculate the offset and size of the protocol field and make
> appropriate insns for the filter.
When I'm saying 'tracing filter' in patch 11/14, I really mean
stap/dtrace-like facility for live debugging, where tracing infra plays
a key role. At the end the programs are written in C with annotations
and perf orchestrates compilation, insertion, attaching, printing results.
Your meaning of 'tracing filter' is canonical: a filter that says whether
event should be recorded or not. And it makes sense.
When perf sees 'protocol==xx' on command line it can generate
ebpf program for it. In such case my earlier proposal for replacing
predicate tree walker with ebpf programs in kernel becomes obsolete?
If I understood correctly, you're proposing to teach perf to generate
ebpf programs for existing command line interface and use it instead
of predicate tree. This way predicate tree can be removed, right?
In such case programs would need to access event records.
> Maybe it needs to pass the event format to the verifier somehow then.
The integer fields are easy to verify. dynamic_array part is tricky, since
16-bit offset + 16-bit length accessors are very tracing specific.
I need to think it through.
> Your scenario looks like just calling a bpf program when it hits a
> event. It could use event triggering for that purpose IMHO.
Sure. Calling ebpf program can be one of even trigger types.
On the other side ebpf programs themselves can replace the whole
triggering, filtering, recording code. We can have events that
do nothing or call ebpf programs. Then programs walk all necessary
data structures, store stuff into a maps, etc Just look at amount of
events that perf processes. Some of it can be done in kernel by
dynamic program.
^ permalink raw reply
* Re: [PATCH RFC net-next 11/14] tracing: allow eBPF programs to be attached to events
From: Namhyung Kim @ 2014-07-02 6:39 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: David S. Miller, Ingo Molnar, Linus Torvalds, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Arnaldo Carvalho de Melo, Jiri Olsa, Thomas Gleixner,
H. Peter Anvin, Andrew Morton, Kees Cook, Linux API,
Network Development, LKML
In-Reply-To: <CAMEtUuzHakFzJYRR0WgwRBnsQL24KGsNax5DTfRNMJrGhvfQMA@mail.gmail.com>
On Wed, Jul 2, 2014 at 3:14 PM, Alexei Starovoitov <ast@plumgrid.com> wrote:
> On Tue, Jul 1, 2014 at 10:32 PM, Namhyung Kim <namhyung@gmail.com> wrote:
>> On Fri, 27 Jun 2014 17:06:03 -0700, Alexei Starovoitov wrote:
>>> User interface:
>>> cat bpf_123 > /sys/kernel/debug/tracing/__event__/filter
>>>
>>> where 123 is an id of the eBPF program priorly loaded.
>>> __event__ is static tracepoint event.
>>> (kprobe events will be supported in the future patches)
>>>
>>> eBPF programs can call in-kernel helper functions to:
>>> - lookup/update/delete elements in maps
>>> - memcmp
>>> - trace_printk
>>
>> ISTR Steve doesn't like to use trace_printk() (at least for production
>> kernels) anymore. And I'm not sure it'd work if there's no existing
>> trace_printk() on a system.
>
> yes. I saw big warning that trace_printk_init_buffers() emits.
> The idea here is to use eBPF programs for live kernel debugging.
> Instead of adding printk() and recompiling, just write a program,
> attach it to some event, and printk whatever is interesting.
> My only concern about printk() was that it dumps things into trace
> buffers (which is still better than dumping stuff to syslog), but now
> (since Andy almost convinced me to switch to 'fd' based interface)
> we can have seq_printk-like that prints into special buffer. So that
> user space does 'read(ufd)' and receives whatever program has
> printed. I think that would be much cleaner.
>
>>> + if (unlikely(ftrace_file->flags & FTRACE_EVENT_FL_FILTERED) && \
>>> + unlikely(ftrace_file->event_call->flags & TRACE_EVENT_FL_BPF)) { \
>>> + struct bpf_context __ctx; \
>>> + \
>>> + populate_bpf_context(&__ctx, args, 0, 0, 0, 0, 0); \
>>> + trace_filter_call_bpf(ftrace_file->filter, &__ctx); \
>>> + return; \
>>> + } \
>>> + \
>>
>> Hmm.. But it seems the eBPF prog is not a filter - it'd always drop the
>> event. And I think it's better to use a recorded entry rather then args
>> as a bpf_context so that tools like perf can manipulate it at compile
>> time based on the event format.
>
> Can manipulate what at compile time? Entry records of tracepoints are
> hard coded based on the event. For verifier it's easier to treat all
> tracepoint events as they received the same 'struct bpf_context'
> of N arguments then the same program can be attached to multiple
> tracepoint events at the same time.
I was thinking about perf creates a bpf program for filtering some
events like recording kfree_skb if protocol == xx. So perf can
calculate the offset and size of the protocol field and make
appropriate insns for the filter.
Maybe it needs to pass the event format to the verifier somehow then.
> I thought about making verifier specific for _every_ tracepoint event,
> but it complicates the user interface, since 'bpf_context' is now different
> for every program. I think args are much easier to deal with from C
> programming point of view, since program can go a fetch the same
> fields that tracepoint 'fast_assign' macro does.
> Also skipping buffer allocation and fast_assign gives very sizable
> performance boost, since the program will access only what it needs to.
>
> The return value of eBPF program is ignored, since I couldn't think
> of use case for it. We can change it to be more 'filter' like and interpret
> return value as true/false, whether to record this event or not. Thoughts?
Your scenario looks like just calling a bpf program when it hits a
event. It could use event triggering for that purpose IMHO.
But for filtering, it needs to add checking of the return value.
Thanks,
Namhyung
^ permalink raw reply
* Re: [PATCH RFC net-next 11/14] tracing: allow eBPF programs to be attached to events
From: Alexei Starovoitov @ 2014-07-02 6:14 UTC (permalink / raw)
To: Namhyung Kim
Cc: David S. Miller, Ingo Molnar, Linus Torvalds, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Arnaldo Carvalho de Melo, Jiri Olsa, Thomas Gleixner,
H. Peter Anvin, Andrew Morton, Kees Cook, Linux API,
Network Development, LKML
In-Reply-To: <87tx70496q.fsf-vfBCOVm4yAnB69T4xOojN9BPR1lH4CV8@public.gmane.org>
On Tue, Jul 1, 2014 at 10:32 PM, Namhyung Kim <namhyung-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> On Fri, 27 Jun 2014 17:06:03 -0700, Alexei Starovoitov wrote:
>> User interface:
>> cat bpf_123 > /sys/kernel/debug/tracing/__event__/filter
>>
>> where 123 is an id of the eBPF program priorly loaded.
>> __event__ is static tracepoint event.
>> (kprobe events will be supported in the future patches)
>>
>> eBPF programs can call in-kernel helper functions to:
>> - lookup/update/delete elements in maps
>> - memcmp
>> - trace_printk
>
> ISTR Steve doesn't like to use trace_printk() (at least for production
> kernels) anymore. And I'm not sure it'd work if there's no existing
> trace_printk() on a system.
yes. I saw big warning that trace_printk_init_buffers() emits.
The idea here is to use eBPF programs for live kernel debugging.
Instead of adding printk() and recompiling, just write a program,
attach it to some event, and printk whatever is interesting.
My only concern about printk() was that it dumps things into trace
buffers (which is still better than dumping stuff to syslog), but now
(since Andy almost convinced me to switch to 'fd' based interface)
we can have seq_printk-like that prints into special buffer. So that
user space does 'read(ufd)' and receives whatever program has
printed. I think that would be much cleaner.
>> + if (unlikely(ftrace_file->flags & FTRACE_EVENT_FL_FILTERED) && \
>> + unlikely(ftrace_file->event_call->flags & TRACE_EVENT_FL_BPF)) { \
>> + struct bpf_context __ctx; \
>> + \
>> + populate_bpf_context(&__ctx, args, 0, 0, 0, 0, 0); \
>> + trace_filter_call_bpf(ftrace_file->filter, &__ctx); \
>> + return; \
>> + } \
>> + \
>
> Hmm.. But it seems the eBPF prog is not a filter - it'd always drop the
> event. And I think it's better to use a recorded entry rather then args
> as a bpf_context so that tools like perf can manipulate it at compile
> time based on the event format.
Can manipulate what at compile time? Entry records of tracepoints are
hard coded based on the event. For verifier it's easier to treat all
tracepoint events as they received the same 'struct bpf_context'
of N arguments then the same program can be attached to multiple
tracepoint events at the same time.
I thought about making verifier specific for _every_ tracepoint event,
but it complicates the user interface, since 'bpf_context' is now different
for every program. I think args are much easier to deal with from C
programming point of view, since program can go a fetch the same
fields that tracepoint 'fast_assign' macro does.
Also skipping buffer allocation and fast_assign gives very sizable
performance boost, since the program will access only what it needs to.
The return value of eBPF program is ignored, since I couldn't think
of use case for it. We can change it to be more 'filter' like and interpret
return value as true/false, whether to record this event or not. Thoughts?
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox