Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1351252

[PATCH net-next 2/9] bpf: introduce percpu_freelist

Show all headers | View raw

Introduce simple percpu_freelist to keep single list of elements
spread across per-cpu singly linked lists.

/* push element into the list */
void pcpu_freelist_push(struct pcpu_freelist *, struct pcpu_freelist_node *);

/* pop element from the list */
struct pcpu_freelist_node *pcpu_freelist_pop(struct pcpu_freelist *);

The object is pushed to the current cpu list.
Pop first trying to get the object from the current cpu list,
if it's empty goes to the neigbour cpu list.

For bpf program usage pattern the collision rate is very low,
since programs push and pop the objects typically on the same cpu.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 kernel/bpf/Makefile          |  2 +-
 kernel/bpf/percpu_freelist.c | 81 ++++++++++++++++++++++++++++++++++++++++++++
 kernel/bpf/percpu_freelist.h | 31 +++++++++++++++++
 3 files changed, 113 insertions(+), 1 deletion(-)
 create mode 100644 kernel/bpf/percpu_freelist.c
 create mode 100644 kernel/bpf/percpu_freelist.h

diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile
index 8a932d079c24..eed911d091da 100644
--- a/kernel/bpf/Makefile
+++ b/kernel/bpf/Makefile
@@ -1,7 +1,7 @@
 obj-y := core.o
 
 obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o
-obj-$(CONFIG_BPF_SYSCALL) += hashtab.o arraymap.o
+obj-$(CONFIG_BPF_SYSCALL) += hashtab.o arraymap.o percpu_freelist.o
 ifeq ($(CONFIG_PERF_EVENTS),y)
 obj-$(CONFIG_BPF_SYSCALL) += stackmap.o
 endif
diff --git a/kernel/bpf/percpu_freelist.c b/kernel/bpf/percpu_freelist.c
new file mode 100644
index 000000000000..250e45c223a1
--- /dev/null
+++ b/kernel/bpf/percpu_freelist.c
@@ -0,0 +1,81 @@
+/* Copyright (c) 2016 Facebook
+ *
+ * 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.
+ */
+#include "percpu_freelist.h"
+
+int pcpu_freelist_init(struct pcpu_freelist *s)
+{
+	int cpu;
+
+	s->freelist = alloc_percpu(struct pcpu_freelist_head);
+	if (!s->freelist)
+		return -ENOMEM;
+
+	for_each_possible_cpu(cpu) {
+		struct pcpu_freelist_head *head = per_cpu_ptr(s->freelist, cpu);
+
+		raw_spin_lock_init(&head->lock);
+		head->first = NULL;
+	}
+	return 0;
+}
+
+void pcpu_freelist_destroy(struct pcpu_freelist *s)
+{
+	free_percpu(s->freelist);
+}
+
+static inline void __pcpu_freelist_push(struct pcpu_freelist_head *head,
+					struct pcpu_freelist_node *node)
+{
+	raw_spin_lock(&head->lock);
+	node->next = head->first;
+	head->first = node;
+	raw_spin_unlock(&head->lock);
+}
+
+/* must be called with preemption disabled */
+void pcpu_freelist_push(struct pcpu_freelist *s,
+			struct pcpu_freelist_node *node)
+{
+	struct pcpu_freelist_head *head = this_cpu_ptr(s->freelist);
+
+	__pcpu_freelist_push(head, node);
+}
+
+void pcpu_freelist_push_cpu(struct pcpu_freelist *s,
+			    struct pcpu_freelist_node *node, int cpu)
+{
+	struct pcpu_freelist_head *head = per_cpu_ptr(s->freelist, cpu);
+
+	__pcpu_freelist_push(head, node);
+}
+
+/* must be called with preemption disabled */
+struct pcpu_freelist_node *pcpu_freelist_pop(struct pcpu_freelist *s)
+{
+	struct pcpu_freelist_head *head;
+	struct pcpu_freelist_node *node;
+	int orig_cpu, cpu;
+
+	orig_cpu = cpu = raw_smp_processor_id();
+	while (1) {
+		head = per_cpu_ptr(s->freelist, cpu);
+		raw_spin_lock(&head->lock);
+		node = head->first;
+		if (node) {
+			head->first = node->next;
+			raw_spin_unlock(&head->lock);
+			return node;
+		}
+		raw_spin_unlock(&head->lock);
+		cpu = cpumask_next(cpu, cpu_possible_mask);
+		if (cpu >= nr_cpu_ids)
+			cpu = 0;
+		if (cpu == orig_cpu)
+			return NULL;
+	}
+}
diff --git a/kernel/bpf/percpu_freelist.h b/kernel/bpf/percpu_freelist.h
new file mode 100644
index 000000000000..4150da61dd13
--- /dev/null
+++ b/kernel/bpf/percpu_freelist.h
@@ -0,0 +1,31 @@
+/* Copyright (c) 2016 Facebook
+ *
+ * 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.
+ */
+#ifndef __PERCPU_FREELIST_H__
+#define __PERCPU_FREELIST_H__
+#include <linux/spinlock.h>
+#include <linux/percpu.h>
+
+struct pcpu_freelist_head {
+	struct pcpu_freelist_node *first;
+	raw_spinlock_t lock;
+};
+
+struct pcpu_freelist {
+	struct pcpu_freelist_head __percpu *freelist;
+};
+
+struct pcpu_freelist_node {
+	struct pcpu_freelist_node *next;
+};
+
+void pcpu_freelist_push(struct pcpu_freelist *, struct pcpu_freelist_node *);
+void pcpu_freelist_push_cpu(struct pcpu_freelist *, struct pcpu_freelist_node *,
+			    int);
+struct pcpu_freelist_node *pcpu_freelist_pop(struct pcpu_freelist *);
+int pcpu_freelist_init(struct pcpu_freelist *);
+void pcpu_freelist_destroy(struct pcpu_freelist *s);
+#endif
-- 
2.6.5

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[PATCH net-next 0/9] bpf: hash map pre-alloc Alexei Starovoitov <ast@fb.com> - 2016-03-07 03:00 +0100
  [PATCH net-next 1/9] bpf: prevent kprobe+bpf deadlocks Alexei Starovoitov <ast@fb.com> - 2016-03-07 03:00 +0100
    Re: [PATCH net-next 1/9] bpf: prevent kprobe+bpf deadlocks Daniel Borkmann <daniel@iogearbox.net> - 2016-03-07 11:10 +0100
  [PATCH net-next 7/9] samples/bpf: test both pre-alloc and normal maps Alexei Starovoitov <ast@fb.com> - 2016-03-07 03:00 +0100
  [PATCH net-next 6/9] samples/bpf: add map_flags to bpf loader Alexei Starovoitov <ast@fb.com> - 2016-03-07 03:10 +0100
  [PATCH net-next 2/9] bpf: introduce percpu_freelist Alexei Starovoitov <ast@fb.com> - 2016-03-07 03:10 +0100
    Re: [PATCH net-next 2/9] bpf: introduce percpu_freelist Daniel Borkmann <daniel@iogearbox.net> - 2016-03-07 11:40 +0100
      Re: [PATCH net-next 2/9] bpf: introduce percpu_freelist Alexei Starovoitov <ast@fb.com> - 2016-03-07 19:30 +0100
  [PATCH net-next 4/9] samples/bpf: make map creation more verbose Alexei Starovoitov <ast@fb.com> - 2016-03-07 03:10 +0100
  [PATCH net-next 9/9] samples/bpf: add map performance test Alexei Starovoitov <ast@fb.com> - 2016-03-07 03:10 +0100
  [PATCH net-next 5/9] samples/bpf: move ksym_search() into library Alexei Starovoitov <ast@fb.com> - 2016-03-07 03:10 +0100
  [PATCH net-next 8/9] samples/bpf: add bpf map stress test Alexei Starovoitov <ast@fb.com> - 2016-03-07 03:10 +0100
  [PATCH net-next 3/9] bpf: pre-allocate hash map elements Alexei Starovoitov <ast@fb.com> - 2016-03-07 03:10 +0100
    Re: [PATCH net-next 3/9] bpf: pre-allocate hash map elements Daniel Borkmann <daniel@iogearbox.net> - 2016-03-07 12:40 +0100
      Re: [PATCH net-next 3/9] bpf: pre-allocate hash map elements Alexei Starovoitov <ast@fb.com> - 2016-03-07 19:40 +0100

csiph-web