Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1509715 > unrolled thread
| Started by | David Herrmann <dh.herrmann@gmail.com> |
|---|---|
| First post | 2016-10-26 21:30 +0200 |
| Last post | 2016-10-28 15:40 +0200 |
| Articles | 20 on this page of 53 — 11 participants |
Back to article view | Back to linux.kernel
[RFC v1 00/14] Bus1 Kernel Message Bus David Herrmann <dh.herrmann@gmail.com> - 2016-10-26 21:30 +0200
[RFC v1 02/14] bus1: provide stub cdev /dev/bus1 David Herrmann <dh.herrmann@gmail.com> - 2016-10-26 21:30 +0200
Re: [RFC v1 02/14] bus1: provide stub cdev /dev/bus1 Andy Lutomirski <luto@amacapital.net> - 2016-10-27 01:30 +0200
Re: [RFC v1 02/14] bus1: provide stub cdev /dev/bus1 Tom Gundersen <teg@jklm.no> - 2016-10-27 02:00 +0200
Re: [RFC v1 02/14] bus1: provide stub cdev /dev/bus1 Arnd Bergmann <arnd@arndb.de> - 2016-10-27 11:20 +0200
Re: [RFC v1 02/14] bus1: provide stub cdev /dev/bus1 Tom Gundersen <teg@jklm.no> - 2016-10-27 17:30 +0200
Re: [RFC v1 02/14] bus1: provide stub cdev /dev/bus1 Linus Torvalds <torvalds@linux-foundation.org> - 2016-10-27 18:40 +0200
Re: [RFC v1 02/14] bus1: provide stub cdev /dev/bus1 Tom Gundersen <teg@jklm.no> - 2016-10-27 18:50 +0200
Re: [RFC v1 02/14] bus1: provide stub cdev /dev/bus1 Arnd Bergmann <arnd@arndb.de> - 2016-10-30 00:20 +0200
[RFC v1 09/14] bus1: provide transaction context for multicasts David Herrmann <dh.herrmann@gmail.com> - 2016-10-26 21:30 +0200
Re: [RFC v1 09/14] bus1: provide transaction context for multicasts Peter Zijlstra <peterz@infradead.org> - 2016-10-28 16:40 +0200
[RFC v1 07/14] bus1: tracking user contexts David Herrmann <dh.herrmann@gmail.com> - 2016-10-26 21:30 +0200
[RFC v1 03/14] bus1: util - active reference utility library David Herrmann <dh.herrmann@gmail.com> - 2016-10-26 21:30 +0200
[RFC v1 05/14] bus1: util - pool utility library David Herrmann <dh.herrmann@gmail.com> - 2016-10-26 21:30 +0200
Re: [RFC v1 05/14] bus1: util - pool utility library Peter Zijlstra <peterz@infradead.org> - 2016-10-27 16:00 +0200
Re: [RFC v1 05/14] bus1: util - pool utility library Peter Zijlstra <peterz@infradead.org> - 2016-10-27 17:10 +0200
Re: [RFC v1 05/14] bus1: util - pool utility library Peter Zijlstra <peterz@infradead.org> - 2016-10-27 16:00 +0200
Re: [RFC v1 05/14] bus1: util - pool utility library Peter Zijlstra <peterz@infradead.org> - 2016-10-27 17:20 +0200
[RFC v1 04/14] bus1: util - fixed list utility library David Herrmann <dh.herrmann@gmail.com> - 2016-10-26 21:30 +0200
Re: [RFC v1 04/14] bus1: util - fixed list utility library Peter Zijlstra <peterz@infradead.org> - 2016-10-27 16:30 +0200
Re: [RFC v1 04/14] bus1: util - fixed list utility library David Herrmann <dh.herrmann@gmail.com> - 2016-10-27 16:50 +0200
[RFC v1 13/14] bus1: limit and protect resources David Herrmann <dh.herrmann@gmail.com> - 2016-10-26 21:30 +0200
[RFC v1 08/14] bus1: implement peer management context David Herrmann <dh.herrmann@gmail.com> - 2016-10-26 21:30 +0200
Re: [RFC v1 08/14] bus1: implement peer management context Richard Weinberger <richard.weinberger@gmail.com> - 2016-10-28 14:10 +0200
Re: [RFC v1 08/14] bus1: implement peer management context Tom Gundersen <teg@jklm.no> - 2016-10-28 15:20 +0200
Re: [RFC v1 08/14] bus1: implement peer management context Richard Weinberger <richard@nod.at> - 2016-10-28 15:30 +0200
Re: [RFC v1 08/14] bus1: implement peer management context Richard Weinberger <richard.weinberger@gmail.com> - 2016-10-28 15:10 +0200
Re: [RFC v1 08/14] bus1: implement peer management context Tom Gundersen <teg@jklm.no> - 2016-10-28 15:30 +0200
Re: [RFC v1 08/14] bus1: implement peer management context Richard Weinberger <richard@nod.at> - 2016-10-28 16:00 +0200
[RFC v1 14/14] bus1: basic user-space kselftests David Herrmann <dh.herrmann@gmail.com> - 2016-10-26 21:30 +0200
[RFC v1 12/14] bus1: hook up file-operations David Herrmann <dh.herrmann@gmail.com> - 2016-10-26 21:30 +0200
[RFC v1 01/14] bus1: add bus1(7) man-page David Herrmann <dh.herrmann@gmail.com> - 2016-10-26 21:30 +0200
Re: [RFC v1 01/14] bus1: add bus1(7) man-page "Kirill A. Shutemov" <kirill@shutemov.name> - 2016-10-29 22:30 +0200
[RFC v1 11/14] bus1: implement message transmission David Herrmann <dh.herrmann@gmail.com> - 2016-10-26 21:30 +0200
[RFC v1 06/14] bus1: util - queue utility library David Herrmann <dh.herrmann@gmail.com> - 2016-10-26 21:30 +0200
Re: [RFC v1 06/14] bus1: util - queue utility library Peter Zijlstra <peterz@infradead.org> - 2016-10-27 17:30 +0200
Re: [RFC v1 06/14] bus1: util - queue utility library Peter Zijlstra <peterz@infradead.org> - 2016-10-27 18:50 +0200
Re: [RFC v1 06/14] bus1: util - queue utility library Tom Gundersen <teg@jklm.no> - 2016-10-28 13:40 +0200
Re: [RFC v1 06/14] bus1: util - queue utility library Peter Zijlstra <peterz@infradead.org> - 2016-10-28 15:40 +0200
Re: [RFC v1 06/14] bus1: util - queue utility library Tom Gundersen <teg@jklm.no> - 2016-10-28 15:50 +0200
Re: [RFC v1 06/14] bus1: util - queue utility library Peter Zijlstra <peterz@infradead.org> - 2016-10-28 16:00 +0200
Re: [RFC v1 06/14] bus1: util - queue utility library Tom Gundersen <teg@jklm.no> - 2016-10-28 16:40 +0200
Re: [RFC v1 06/14] bus1: util - queue utility library Peter Zijlstra <peterz@infradead.org> - 2016-10-28 18:50 +0200
Re: [RFC v1 00/14] Bus1 Kernel Message Bus Linus Torvalds <torvalds@linux-foundation.org> - 2016-10-26 21:50 +0200
Re: [RFC v1 00/14] Bus1 Kernel Message Bus David Herrmann <dh.herrmann@gmail.com> - 2016-10-26 22:40 +0200
Re: [RFC v1 00/14] Bus1 Kernel Message Bus "Kirill A. Shutemov" <kirill@shutemov.name> - 2016-10-29 22:30 +0200
Re: [RFC v1 00/14] Bus1 Kernel Message Bus Josh Triplett <josh@joshtriplett.org> - 2016-10-29 23:10 +0200
Re: [RFC v1 00/14] Bus1 Kernel Message Bus David Herrmann <dh.herrmann@gmail.com> - 2016-11-02 15:50 +0100
Re: [RFC v1 04/14] bus1: util - fixed list utility library Arnd Bergmann <arnd@arndb.de> - 2016-10-27 16:00 +0200
Re: [RFC v1 04/14] bus1: util - fixed list utility library David Herrmann <dh.herrmann@gmail.com> - 2016-10-27 16:00 +0200
Re: [RFC v1 00/14] Bus1 Kernel Message Bus Michael Kerrisk <mtk.manpages@gmail.com> - 2016-10-27 16:40 +0200
Re: [RFC v1 00/14] Bus1 Kernel Message Bus Richard Weinberger <richard.weinberger@gmail.com> - 2016-10-28 15:20 +0200
Re: [RFC v1 00/14] Bus1 Kernel Message Bus Tom Gundersen <teg@jklm.no> - 2016-10-28 15:40 +0200
Page 1 of 3 [1] 2 3 Next page →
| From | David Herrmann <dh.herrmann@gmail.com> |
|---|---|
| Date | 2016-10-26 21:30 +0200 |
| Subject | [RFC v1 00/14] Bus1 Kernel Message Bus |
| Message-ID | <swC3D-87o-1@gated-at.bofh.it> |
Hi
This proposal introduces bus1.ko, a kernel messaging bus. This is not a request
for inclusion, yet. It is rather an initial draft and a Request For Comments.
While bus1 emerged out of the kdbus project, bus1 was started from scratch and
the concepts have little in common. In a nutshell, bus1 provides a
capability-based IPC system, similar in nature to Android Binder, Cap'n Proto,
and seL4. The module is completely generic and does neither require nor mandate
a user-space counter-part.
o Description
Bus1 is a local IPC system, which provides a decentralized infrastructure to
share objects between local peers. The main building blocks are nodes and
handles. Nodes represent objects of a local peer, while handles represent
descriptors that point to a node. Nodes can be created and destroyed by any
peer, and they will always remain owned by their respective creator. Handles
on the other hand, are used to refer to nodes and can be passed around with
messages as auxiliary data. Whenever a handle is transferred, the receiver
will get its own handle allocated, pointing to the same node as the original
handle.
Any peer can send messages directed at one of their handles. This will
transfer the message to the owner of the node the handle points to. If a
peer does not posess a handle to a given node, it will not be able to send a
message to that node. That is, handles provide exclusive access management.
Anyone that somehow acquired a handle to a node is privileged to further
send this handle to other peers. As such, access management is transitive.
Once a peer acquired a handle, it cannot be revoked again. However, a node
owner can, at anytime, destroy a node. This will effectively unbind all
existing handles to that node on any peer, notifying each one of the
destruction.
Unlike nodes and handles, peers cannot be addressed directly. In fact, peers
are completely disconnected entities. A peer is merely an anchor of a set of
nodes and handles, including an incoming message queue for any of those.
Whether multiple nodes are all part of the same peer, or part of different
peers does not affect the remote view of those. Peers solely exist as
management entity and command dispatcher to local processes.
The set of actors on a system is completely decentralized. There is no
global component involved that provides a central registry or discovery
mechanism. Furthermore, communication between peers only involves those
peers, and does not affect any other peer in any way. No global
communication lock is taken. However, any communication is still globally
ordered, including unicasts, multicasts, and notifications.
o Prior Art
The concepts behind bus1 are almost identical to capability systems like
Android Binder, Google Mojo, Cap'n Proto, seL4, and more. Bus1 differs from
them by supporting Global Ordering, Multicasts, Resource Accounting, No
Global Locking, No Global Context.
While the bus1 UAPI does not expose all features (like soft-references as
supported by Binder), the in-kernel code includes support for it. Multiple
UAPIs can be supported on top of the in-kernel bus1 code, including support
for the Binder UAPI. Efforts on this are still on-going.
o Documentation
The first patch in this series provides the bus1(7) man-page. It explains
all concepts in bus1 in more detail. Furthermore, it describes the API that
is available on bus1 file descriptors. The pre-compiled man-page is
available at:
http://www.bus1.org/bus1.html
There is also a great bunch of in-source documentation available. All
cross-source-file APIs have KernelDoc annotations. Furthermore, we have an
introduction for each subsystem, to be found in the header files. The total
number in lines of code for bus1 is roughly ~4.5k. The remaining ~5k LOC
are comments and documentation.
o Upstream
The upstream development repository is available on github:
http://github.com/bus1/bus1
It is an out-of-tree repository that allows easy and fast development of
new bus1 features. The in-tree integration repository is available at:
http://github.com/bus1/linux
o Conferences
Tom and I will be attending Linux Plumbers Conf next week. Please do not
hesitate to contact us there in person. There will also be a presentation
[1] of bus1 on the last day of the conference.
Thanks
Tom & David
[1] https://www.linuxplumbersconf.org/2016/ocw/proposals/3819
Tom Gundersen (14):
bus1: add bus1(7) man-page
bus1: provide stub cdev /dev/bus1
bus1: util - active reference utility library
bus1: util - fixed list utility library
bus1: util - pool utility library
bus1: util - queue utility library
bus1: tracking user contexts
bus1: implement peer management context
bus1: provide transaction context for multicasts
bus1: add handle management
bus1: implement message transmission
bus1: hook up file-operations
bus1: limit and protect resources
bus1: basic user-space kselftests
Documentation/bus1/.gitignore | 2 +
Documentation/bus1/Makefile | 41 +
Documentation/bus1/bus1.xml | 833 +++++++++++++++++++++
Documentation/bus1/stylesheet.xsl | 16 +
include/uapi/linux/bus1.h | 138 ++++
init/Kconfig | 17 +
ipc/Makefile | 1 +
ipc/bus1/Makefile | 16 +
ipc/bus1/handle.c | 823 ++++++++++++++++++++
ipc/bus1/handle.h | 312 ++++++++
ipc/bus1/main.c | 146 ++++
ipc/bus1/main.h | 88 +++
ipc/bus1/message.c | 656 ++++++++++++++++
ipc/bus1/message.h | 171 +++++
ipc/bus1/peer.c | 1163 +++++++++++++++++++++++++++++
ipc/bus1/peer.h | 163 ++++
ipc/bus1/security.h | 45 ++
ipc/bus1/tests.c | 19 +
ipc/bus1/tests.h | 32 +
ipc/bus1/tx.c | 360 +++++++++
ipc/bus1/tx.h | 102 +++
ipc/bus1/user.c | 628 ++++++++++++++++
ipc/bus1/user.h | 140 ++++
ipc/bus1/util.c | 214 ++++++
ipc/bus1/util.h | 141 ++++
ipc/bus1/util/active.c | 419 +++++++++++
ipc/bus1/util/active.h | 154 ++++
ipc/bus1/util/flist.c | 116 +++
ipc/bus1/util/flist.h | 202 +++++
ipc/bus1/util/pool.c | 572 ++++++++++++++
ipc/bus1/util/pool.h | 164 ++++
ipc/bus1/util/queue.c | 445 +++++++++++
ipc/bus1/util/queue.h | 351 +++++++++
tools/testing/selftests/bus1/.gitignore | 2 +
tools/testing/selftests/bus1/Makefile | 19 +
tools/testing/selftests/bus1/bus1-ioctl.h | 111 +++
tools/testing/selftests/bus1/test-api.c | 532 +++++++++++++
tools/testing/selftests/bus1/test-io.c | 198 +++++
tools/testing/selftests/bus1/test.h | 114 +++
39 files changed, 9666 insertions(+)
create mode 100644 Documentation/bus1/.gitignore
create mode 100644 Documentation/bus1/Makefile
create mode 100644 Documentation/bus1/bus1.xml
create mode 100644 Documentation/bus1/stylesheet.xsl
create mode 100644 include/uapi/linux/bus1.h
create mode 100644 ipc/bus1/Makefile
create mode 100644 ipc/bus1/handle.c
create mode 100644 ipc/bus1/handle.h
create mode 100644 ipc/bus1/main.c
create mode 100644 ipc/bus1/main.h
create mode 100644 ipc/bus1/message.c
create mode 100644 ipc/bus1/message.h
create mode 100644 ipc/bus1/peer.c
create mode 100644 ipc/bus1/peer.h
create mode 100644 ipc/bus1/security.h
create mode 100644 ipc/bus1/tests.c
create mode 100644 ipc/bus1/tests.h
create mode 100644 ipc/bus1/tx.c
create mode 100644 ipc/bus1/tx.h
create mode 100644 ipc/bus1/user.c
create mode 100644 ipc/bus1/user.h
create mode 100644 ipc/bus1/util.c
create mode 100644 ipc/bus1/util.h
create mode 100644 ipc/bus1/util/active.c
create mode 100644 ipc/bus1/util/active.h
create mode 100644 ipc/bus1/util/flist.c
create mode 100644 ipc/bus1/util/flist.h
create mode 100644 ipc/bus1/util/pool.c
create mode 100644 ipc/bus1/util/pool.h
create mode 100644 ipc/bus1/util/queue.c
create mode 100644 ipc/bus1/util/queue.h
create mode 100644 tools/testing/selftests/bus1/.gitignore
create mode 100644 tools/testing/selftests/bus1/Makefile
create mode 100644 tools/testing/selftests/bus1/bus1-ioctl.h
create mode 100644 tools/testing/selftests/bus1/test-api.c
create mode 100644 tools/testing/selftests/bus1/test-io.c
create mode 100644 tools/testing/selftests/bus1/test.h
--
2.10.1
[toc] | [next] | [standalone]
| From | David Herrmann <dh.herrmann@gmail.com> |
|---|---|
| Date | 2016-10-26 21:30 +0200 |
| Subject | [RFC v1 02/14] bus1: provide stub cdev /dev/bus1 |
| Message-ID | <swC3D-87o-5@gated-at.bofh.it> |
| In reply to | #1509715 |
From: Tom Gundersen <teg@jklm.no>
Add the CONFIG_BUS1 option to enable the bus1 kernel messaging bus. If
enabled, provide the bus1.ko module with a stub cdev /dev/bus1. So far
it does not expose any API, but the full intended uapi is provided in
include/uapi/linux/bus1.h already.
Signed-off-by: Tom Gundersen <teg@jklm.no>
Signed-off-by: David Herrmann <dh.herrmann@gmail.com>
---
include/uapi/linux/bus1.h | 138 ++++++++++++++++++++++++++++++++++++++++++++++
init/Kconfig | 17 ++++++
ipc/Makefile | 1 +
ipc/bus1/Makefile | 6 ++
ipc/bus1/main.c | 80 +++++++++++++++++++++++++++
ipc/bus1/main.h | 74 +++++++++++++++++++++++++
ipc/bus1/tests.c | 19 +++++++
ipc/bus1/tests.h | 32 +++++++++++
8 files changed, 367 insertions(+)
create mode 100644 include/uapi/linux/bus1.h
create mode 100644 ipc/bus1/Makefile
create mode 100644 ipc/bus1/main.c
create mode 100644 ipc/bus1/main.h
create mode 100644 ipc/bus1/tests.c
create mode 100644 ipc/bus1/tests.h
diff --git a/include/uapi/linux/bus1.h b/include/uapi/linux/bus1.h
new file mode 100644
index 0000000..8ec3357
--- /dev/null
+++ b/include/uapi/linux/bus1.h
@@ -0,0 +1,138 @@
+#ifndef _UAPI_LINUX_BUS1_H
+#define _UAPI_LINUX_BUS1_H
+
+/*
+ * Copyright (C) 2013-2016 Red Hat, Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by the
+ * Free Software Foundation; either version 2.1 of the License, or (at
+ * your option) any later version.
+ */
+
+#include <linux/ioctl.h>
+#include <linux/types.h>
+
+#define BUS1_FD_MAX (256)
+
+#define BUS1_IOCTL_MAGIC 0x96
+#define BUS1_HANDLE_INVALID ((__u64)-1)
+#define BUS1_OFFSET_INVALID ((__u64)-1)
+
+enum {
+ BUS1_HANDLE_FLAG_MANAGED = 1ULL << 0,
+ BUS1_HANDLE_FLAG_REMOTE = 1ULL << 1,
+};
+
+enum {
+ BUS1_PEER_FLAG_WANT_SECCTX = 1ULL << 0,
+};
+
+enum {
+ BUS1_PEER_RESET_FLAG_FLUSH = 1ULL << 0,
+ BUS1_PEER_RESET_FLAG_FLUSH_SEED = 1ULL << 1,
+};
+
+struct bus1_cmd_peer_reset {
+ __u64 flags;
+ __u64 peer_flags;
+ __u32 max_slices;
+ __u32 max_handles;
+ __u32 max_inflight_bytes;
+ __u32 max_inflight_fds;
+} __attribute__((__aligned__(8)));
+
+struct bus1_cmd_handle_transfer {
+ __u64 flags;
+ __u64 src_handle;
+ __u64 dst_fd;
+ __u64 dst_handle;
+} __attribute__((__aligned__(8)));
+
+enum {
+ BUS1_NODES_DESTROY_FLAG_RELEASE_HANDLES = 1ULL << 0,
+};
+
+struct bus1_cmd_nodes_destroy {
+ __u64 flags;
+ __u64 ptr_nodes;
+ __u64 n_nodes;
+} __attribute__((__aligned__(8)));
+
+enum {
+ BUS1_SEND_FLAG_CONTINUE = 1ULL << 0,
+ BUS1_SEND_FLAG_SEED = 1ULL << 1,
+};
+
+struct bus1_cmd_send {
+ __u64 flags;
+ __u64 ptr_destinations;
+ __u64 ptr_errors;
+ __u64 n_destinations;
+ __u64 ptr_vecs;
+ __u64 n_vecs;
+ __u64 ptr_handles;
+ __u64 n_handles;
+ __u64 ptr_fds;
+ __u64 n_fds;
+} __attribute__((__aligned__(8)));
+
+enum {
+ BUS1_RECV_FLAG_PEEK = 1ULL << 0,
+ BUS1_RECV_FLAG_SEED = 1ULL << 1,
+ BUS1_RECV_FLAG_INSTALL_FDS = 1ULL << 2,
+};
+
+enum {
+ BUS1_MSG_NONE,
+ BUS1_MSG_DATA,
+ BUS1_MSG_NODE_DESTROY,
+ BUS1_MSG_NODE_RELEASE,
+};
+
+enum {
+ BUS1_MSG_FLAG_HAS_SECCTX = 1ULL << 0,
+ BUS1_MSG_FLAG_CONTINUE = 1ULL << 1,
+};
+
+struct bus1_cmd_recv {
+ __u64 flags;
+ __u64 max_offset;
+ struct {
+ __u64 type;
+ __u64 flags;
+ __u64 destination;
+ __u32 uid;
+ __u32 gid;
+ __u32 pid;
+ __u32 tid;
+ __u64 offset;
+ __u64 n_bytes;
+ __u64 n_handles;
+ __u64 n_fds;
+ __u64 n_secctx;
+ } __attribute__((__aligned__(8))) msg;
+} __attribute__((__aligned__(8)));
+
+enum {
+ BUS1_CMD_PEER_DISCONNECT = _IOWR(BUS1_IOCTL_MAGIC, 0x00,
+ __u64),
+ BUS1_CMD_PEER_QUERY = _IOWR(BUS1_IOCTL_MAGIC, 0x01,
+ struct bus1_cmd_peer_reset),
+ BUS1_CMD_PEER_RESET = _IOWR(BUS1_IOCTL_MAGIC, 0x02,
+ struct bus1_cmd_peer_reset),
+ BUS1_CMD_HANDLE_RELEASE = _IOWR(BUS1_IOCTL_MAGIC, 0x10,
+ __u64),
+ BUS1_CMD_HANDLE_TRANSFER = _IOWR(BUS1_IOCTL_MAGIC, 0x11,
+ struct bus1_cmd_handle_transfer),
+ BUS1_CMD_NODES_DESTROY = _IOWR(BUS1_IOCTL_MAGIC, 0x20,
+ struct bus1_cmd_nodes_destroy),
+ BUS1_CMD_SLICE_RELEASE = _IOWR(BUS1_IOCTL_MAGIC, 0x30,
+ __u64),
+ BUS1_CMD_SEND = _IOWR(BUS1_IOCTL_MAGIC, 0x40,
+ struct bus1_cmd_send),
+ BUS1_CMD_RECV = _IOWR(BUS1_IOCTL_MAGIC, 0x50,
+ struct bus1_cmd_recv),
+};
+
+#endif /* _UAPI_LINUX_BUS1_H */
diff --git a/init/Kconfig b/init/Kconfig
index 34407f1..04c7daf 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -273,6 +273,23 @@ config POSIX_MQUEUE_SYSCTL
depends on SYSCTL
default y
+config BUS1
+ tristate "Bus1 Kernel Message Bus"
+ help
+ The Bus1 Kernel Message Bus defines and implements a distributed
+ object model. It provides a capability-based IPC system for machine
+ local communication.
+
+ The Bus1 IPC system is exposed via /dev/bus1. If debugfs is enabled,
+ bus1 exposes additional debug information there.
+
+config BUS1_TESTS
+ bool "Bus1 Self-Tests"
+ depends on BUS1
+ help
+ Enable and run the bus1 self-tests before loading the module. The
+ overhead is minimal, so there is generally no harm in enabling it.
+
config CROSS_MEMORY_ATTACH
bool "Enable process_vm_readv/writev syscalls"
depends on MMU
diff --git a/ipc/Makefile b/ipc/Makefile
index 86c7300..eee12d1 100644
--- a/ipc/Makefile
+++ b/ipc/Makefile
@@ -9,4 +9,5 @@ obj_mq-$(CONFIG_COMPAT) += compat_mq.o
obj-$(CONFIG_POSIX_MQUEUE) += mqueue.o msgutil.o $(obj_mq-y)
obj-$(CONFIG_IPC_NS) += namespace.o
obj-$(CONFIG_POSIX_MQUEUE_SYSCTL) += mq_sysctl.o
+obj-$(CONFIG_BUS1) += bus1/
diff --git a/ipc/bus1/Makefile b/ipc/bus1/Makefile
new file mode 100644
index 0000000..d3a4491
--- /dev/null
+++ b/ipc/bus1/Makefile
@@ -0,0 +1,6 @@
+bus1-y := \
+ main.o
+
+obj-$(CONFIG_BUS1) += bus1.o
+
+bus1-$(CONFIG_BUS1_TESTS) += tests.o
diff --git a/ipc/bus1/main.c b/ipc/bus1/main.c
new file mode 100644
index 0000000..02412a7
--- /dev/null
+++ b/ipc/bus1/main.c
@@ -0,0 +1,80 @@
+/*
+ * Copyright (C) 2013-2016 Red Hat, Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by the
+ * Free Software Foundation; either version 2.1 of the License, or (at
+ * your option) any later version.
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+#include <linux/debugfs.h>
+#include <linux/err.h>
+#include <linux/fs.h>
+#include <linux/init.h>
+#include <linux/miscdevice.h>
+#include <linux/module.h>
+#include "main.h"
+#include "tests.h"
+
+static int bus1_fop_open(struct inode *inode, struct file *file)
+{
+ return 0;
+}
+
+static int bus1_fop_release(struct inode *inode, struct file *file)
+{
+ return 0;
+}
+
+const struct file_operations bus1_fops = {
+ .owner = THIS_MODULE,
+ .open = bus1_fop_open,
+ .release = bus1_fop_release,
+ .llseek = noop_llseek,
+};
+
+static struct miscdevice bus1_misc = {
+ .fops = &bus1_fops,
+ .minor = MISC_DYNAMIC_MINOR,
+ .name = KBUILD_MODNAME,
+ .mode = S_IRUGO | S_IWUGO,
+};
+
+struct dentry *bus1_debugdir;
+
+static int __init bus1_modinit(void)
+{
+ int r;
+
+ r = bus1_tests_run();
+ if (r < 0)
+ return r;
+
+ bus1_debugdir = debugfs_create_dir(KBUILD_MODNAME, NULL);
+ if (!bus1_debugdir)
+ pr_err("cannot create debugfs root\n");
+
+ r = misc_register(&bus1_misc);
+ if (r < 0)
+ goto error;
+
+ pr_info("loaded\n");
+ return 0;
+
+error:
+ debugfs_remove(bus1_debugdir);
+ return r;
+}
+
+static void __exit bus1_modexit(void)
+{
+ misc_deregister(&bus1_misc);
+ debugfs_remove(bus1_debugdir);
+ pr_info("unloaded\n");
+}
+
+module_init(bus1_modinit);
+module_exit(bus1_modexit);
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("Bus based interprocess communication");
diff --git a/ipc/bus1/main.h b/ipc/bus1/main.h
new file mode 100644
index 0000000..76fce66
--- /dev/null
+++ b/ipc/bus1/main.h
@@ -0,0 +1,74 @@
+#ifndef __BUS1_MAIN_H
+#define __BUS1_MAIN_H
+
+/*
+ * Copyright (C) 2013-2016 Red Hat, Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by the
+ * Free Software Foundation; either version 2.1 of the License, or (at
+ * your option) any later version.
+ */
+
+/**
+ * DOC: Bus1 Overview
+ *
+ * bus1 is a local IPC system, which provides a decentralized infrastructure to
+ * share objects between local peers. The main building blocks are nodes and
+ * handles. Nodes represent objects of a local peer, while handles represent
+ * descriptors that point to a node. Nodes can be created and destroyed by any
+ * peer, and they will always remain owned by their respective creator. Handles,
+ * on the other hand, are used to refer to nodes and can be passed around with
+ * messages as auxiliary data. Whenever a handle is transferred, the receiver
+ * will get its own handle allocated, pointing to the same node as the original
+ * handle.
+ *
+ * Any peer can send messages directed at one of their handles. This will
+ * transfer the message to the owner of the node the handle points to. If a
+ * peer does not posess a handle to a given node, it will not be able to send a
+ * message to that node. That is, handles provide exclusive access management.
+ * Anyone that somehow acquired a handle to a node is privileged to further
+ * send this handle to other peers. As such, access management is transitive.
+ * Once a peer acquired a handle, it cannot be revoked again. However, a node
+ * owner can, at anytime, destroy a node. This will effectively unbind all
+ * existing handles to that node on any peer, notifying each one of the
+ * destruction.
+ *
+ * Unlike nodes and handles, peers cannot be addressed directly. In fact, peers
+ * are completely disconnected entities. A peer is merely an anchor of a set of
+ * nodes and handles, including an incoming message queue for any of those.
+ * Whether multiple nodes are all part of the same peer, or part of different
+ * peers does not affect the remote view of those. Peers solely exist as
+ * management entity and command dispatcher to local processes.
+ *
+ * The set of actors on a system is completely decentralized. There is no
+ * global component involved that provides a central registry or discovery
+ * mechanism. Furthermore, communication between peers only involves those
+ * peers, and does not affect any other peer in any way. No global
+ * communication lock is taken. However, any communication is still globally
+ * ordered, including unicasts, multicasts, and notifications.
+ */
+
+struct dentry;
+struct file_operations;
+
+/**
+ * bus1_fops - file-operations of bus1 character devices
+ *
+ * All bus1 peers are backed by a character device with @bus1_fops used as
+ * file-operations. That is, a file is a bus1 peer if, and only if, its f_op
+ * pointer contains @bus1_fops.
+ */
+extern const struct file_operations bus1_fops;
+
+/**
+ * bus1_debugdir - debugfs root directory
+ *
+ * If debugfs is enabled, this is set to point to the debugfs root directory
+ * for this module. If debugfs is disabled, or if the root directory could not
+ * be created, this is set to NULL or ERR_PTR (which debugfs functions can deal
+ * with seamlessly).
+ */
+extern struct dentry *bus1_debugdir;
+
+#endif /* __BUS1_MAIN_H */
diff --git a/ipc/bus1/tests.c b/ipc/bus1/tests.c
new file mode 100644
index 0000000..6fd2946
--- /dev/null
+++ b/ipc/bus1/tests.c
@@ -0,0 +1,19 @@
+/*
+ * Copyright (C) 2013-2016 Red Hat, Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by the
+ * Free Software Foundation; either version 2.1 of the License, or (at
+ * your option) any later version.
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+#include <linux/err.h>
+#include <linux/kernel.h>
+#include "tests.h"
+
+int bus1_tests_run(void)
+{
+ pr_info("run selftests..\n");
+ return 0;
+}
diff --git a/ipc/bus1/tests.h b/ipc/bus1/tests.h
new file mode 100644
index 0000000..fb554e2
--- /dev/null
+++ b/ipc/bus1/tests.h
@@ -0,0 +1,32 @@
+#ifndef __BUS1_TESTS_H
+#define __BUS1_TESTS_H
+
+/*
+ * Copyright (C) 2013-2016 Red Hat, Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by the
+ * Free Software Foundation; either version 2.1 of the License, or (at
+ * your option) any later version.
+ */
+
+/**
+ * Kernel Selftests
+ *
+ * These tests are built into the kernel module itself if, and only if, the
+ * required configuration is selected. On every module load, the selftests will
+ * be run. On production builds, this option should not be selected.
+ */
+
+#include <linux/kernel.h>
+
+#if IS_ENABLED(CONFIG_BUS1_TESTS)
+int bus1_tests_run(void);
+#else
+static inline int bus1_tests_run(void)
+{
+ return 0;
+}
+#endif
+
+#endif /* __BUS1_TESTS_H */
--
2.10.1
[toc] | [prev] | [next] | [standalone]
| From | Andy Lutomirski <luto@amacapital.net> |
|---|---|
| Date | 2016-10-27 01:30 +0200 |
| Subject | Re: [RFC v1 02/14] bus1: provide stub cdev /dev/bus1 |
| Message-ID | <swFNU-28S-49@gated-at.bofh.it> |
| In reply to | #1509716 |
On Oct 26, 2016 12:21 PM, "David Herrmann" <dh.herrmann@gmail.com> wrote: > > From: Tom Gundersen <teg@jklm.no> > > Add the CONFIG_BUS1 option to enable the bus1 kernel messaging bus. If > enabled, provide the bus1.ko module with a stub cdev /dev/bus1. So far > it does not expose any API, but the full intended uapi is provided in > include/uapi/linux/bus1.h already. > This may have been covered elsewhere, but could this use syscalls instead?
[toc] | [prev] | [next] | [standalone]
| From | Tom Gundersen <teg@jklm.no> |
|---|---|
| Date | 2016-10-27 02:00 +0200 |
| Subject | Re: [RFC v1 02/14] bus1: provide stub cdev /dev/bus1 |
| Message-ID | <swGh1-2j3-23@gated-at.bofh.it> |
| In reply to | #1509945 |
On Thu, Oct 27, 2016 at 1:19 AM, Andy Lutomirski <luto@amacapital.net> wrote: > This may have been covered elsewhere, but could this use syscalls instead? Yes, syscalls would work essentially the same. For now, we are using a cdev as it makes it a lot more convenient to develop and test as an out-of-tree module, but that could be changed easily before the final submission, if that's what we want. Cheers, Tom
[toc] | [prev] | [next] | [standalone]
| From | Arnd Bergmann <arnd@arndb.de> |
|---|---|
| Date | 2016-10-27 11:20 +0200 |
| Subject | Re: [RFC v1 02/14] bus1: provide stub cdev /dev/bus1 |
| Message-ID | <swP0R-8pq-15@gated-at.bofh.it> |
| In reply to | #1509959 |
On Thursday, October 27, 2016 1:54:05 AM CEST Tom Gundersen wrote:
> On Thu, Oct 27, 2016 at 1:19 AM, Andy Lutomirski <luto@amacapital.net> wrote:
> > This may have been covered elsewhere, but could this use syscalls instead?
>
> Yes, syscalls would work essentially the same. For now, we are using a
> cdev as it makes it a lot more convenient to develop and test as an
> out-of-tree module, but that could be changed easily before the final
> submission, if that's what we want.
Generally speaking, I think syscalls would be appropriate here, and put
bus1 into a similar category as the other ipc interfaces (shm, msg, sem,
mqueue, ...).
However, syscall API design is nontrivial, and will require a bit of
work to come to a set of syscalls that is fairly compact but also
extensible enough. I think it makes sense to go through the exercise
of working out what the syscall interface would end up looking like,
and then make a decision.
There is currently a set of file operations:
@@ -48,7 +90,11 @@ const struct file_operations bus1_fops = {
.owner = THIS_MODULE,
.open = bus1_fop_open,
.release = bus1_fop_release,
+ .poll = bus1_fop_poll,
.llseek = noop_llseek,
+ .mmap = bus1_fop_mmap,
+ .unlocked_ioctl = bus1_peer_ioctl,
+ .compat_ioctl = bus1_peer_ioctl,
.show_fdinfo = bus1_fop_show_fdinfo,
};
and then another set of ioctls:
+enum {
+ BUS1_CMD_PEER_DISCONNECT = _IOWR(BUS1_IOCTL_MAGIC, 0x00,
+ __u64),
+ BUS1_CMD_PEER_QUERY = _IOWR(BUS1_IOCTL_MAGIC, 0x01,
+ struct bus1_cmd_peer_reset),
+ BUS1_CMD_PEER_RESET = _IOWR(BUS1_IOCTL_MAGIC, 0x02,
+ struct bus1_cmd_peer_reset),
+ BUS1_CMD_HANDLE_RELEASE = _IOWR(BUS1_IOCTL_MAGIC, 0x10,
+ __u64),
+ BUS1_CMD_HANDLE_TRANSFER = _IOWR(BUS1_IOCTL_MAGIC, 0x11,
+ struct bus1_cmd_handle_transfer),
+ BUS1_CMD_NODES_DESTROY = _IOWR(BUS1_IOCTL_MAGIC, 0x20,
+ struct bus1_cmd_nodes_destroy),
+ BUS1_CMD_SLICE_RELEASE = _IOWR(BUS1_IOCTL_MAGIC, 0x30,
+ __u64),
+ BUS1_CMD_SEND = _IOWR(BUS1_IOCTL_MAGIC, 0x40,
+ struct bus1_cmd_send),
+ BUS1_CMD_RECV = _IOWR(BUS1_IOCTL_MAGIC, 0x50,
+ struct bus1_cmd_recv),
+};
I think there is no alternative to having some sort of file descriptor
with the basic operations you have above, but there is a question of
how to get that file descriptor if the ioctls get changed to a syscall,
the basic options being:
- Keep using a chardev. This works, but feels a little odd to me,
and I can't think of any other interfaces combining syscalls with
a chardev.
- Have one syscall that returns an open file descriptor, replacing
the fops->open() function. One advantage is that you can pass
additional arguments in that you can't have with open.
An example for this would be mqueue_open().
- Have a mountable file system, and use open() on that to create
connections. Advantages are that it's fairly easy to have one
instance per fs-namespace, and you can have user-defined naming
of objects in the file system.
For the other operations, the obvious translation would be to
turn each ioctl command into one syscall, but that may not always
be the best representation. One limitation is that you cannot
generally have more than six 'long' arguments on a lot of
architectures, and passing 'u64' arguments to syscalls is awkward.
For some of the commands, the transformation would be straightforward
if we assume that the 'u64' arguments can actually be 'long',
I guess like this:
+struct bus1_cmd_handle_transfer {
+ __u64 flags;
+ __u64 src_handle;
+ __u64 dst_fd;
+ __u64 dst_handle;
+} __attribute__((__aligned__(8)));
long bus1_handle_transfer(int fd, unsigned long handle,
int dst_fd, unsigned long *dst_handle, unsigned int flags);
+struct bus1_cmd_nodes_destroy {
+ __u64 flags;
+ __u64 ptr_nodes;
+ __u64 n_nodes;
+} __attribute__((__aligned__(8)));
long bus1_nodes_destroy(int fd, u64 *ptr_nodes,
long n_nodes, unsigned int flags);
However, the peer_reset would exceed the 6-argument limit when you count
the initial file descriptor even if you assume that 'flags' can be
made 32-bit:
+struct bus1_cmd_peer_reset {
+ __u64 flags;
+ __u64 peer_flags;
+ __u32 max_slices;
+ __u32 max_handles;
+ __u32 max_inflight_bytes;
+ __u32 max_inflight_fds;
+} __attribute__((__aligned__(8)));
maybe something slightly ugly like
long bus1_peer_reset(int fd, const struct bus1_peer_limits *param,
unsigned int flags);
a library might provide a wrapper that passes all the limits
as separate arguments.
The receive function would be fairly straightforward again, as
we just pass a pointer to the returned message, and all inputs
can be arguments, but the send command with this structure
+struct bus1_cmd_send {
+ __u64 flags;
+ __u64 ptr_destinations;
+ __u64 ptr_errors;
+ __u64 n_destinations;
+ __u64 ptr_vecs;
+ __u64 n_vecs;
+ __u64 ptr_handles;
+ __u64 n_handles;
+ __u64 ptr_fds;
+ __u64 n_fds;
+} __attribute__((__aligned__(8)));
is really tricky, as it's such a central interface but it's
also really complex, with its five indirect pointers to
variable-length arrays, making a total of 11 arguments
(including the first fd). Turning this into a syscall would
probably make a more efficient interface, so maybe some
of the arrays can be turned into a single argument and
require the user to call it multiple times instead of the
kernel looping around it.
The minimal version would be something like
long bus1_send(int fd, long dst, struct iovec *vecs, int n_vecs,
long handle, int dst_fd);
so you already get to six arguments with one destination, one
handle and one fd but no flags. Replacing vecs/n_vecs with pointer
and length doesn't help either, so I guess whatever we do here
we have to use some indirect structure.
Arnd
[toc] | [prev] | [next] | [standalone]
| From | Tom Gundersen <teg@jklm.no> |
|---|---|
| Date | 2016-10-27 17:30 +0200 |
| Subject | Re: [RFC v1 02/14] bus1: provide stub cdev /dev/bus1 |
| Message-ID | <swUMV-3F9-5@gated-at.bofh.it> |
| In reply to | #1510133 |
On Thu, Oct 27, 2016 at 11:11 AM, Arnd Bergmann <arnd@arndb.de> wrote:
> On Thursday, October 27, 2016 1:54:05 AM CEST Tom Gundersen wrote:
>> On Thu, Oct 27, 2016 at 1:19 AM, Andy Lutomirski <luto@amacapital.net> wrote:
>> > This may have been covered elsewhere, but could this use syscalls instead?
>>
>> Yes, syscalls would work essentially the same. For now, we are using a
>> cdev as it makes it a lot more convenient to develop and test as an
>> out-of-tree module, but that could be changed easily before the final
>> submission, if that's what we want.
>
>
> Generally speaking, I think syscalls would be appropriate here, and put
> bus1 into a similar category as the other ipc interfaces (shm, msg, sem,
> mqueue, ...).
Could you elaborate on why you think syscalls would be more
appropriate than ioctls?
> However, syscall API design is nontrivial, and will require a bit of
> work to come to a set of syscalls that is fairly compact but also
> extensible enough. I think it makes sense to go through the exercise
> of working out what the syscall interface would end up looking like,
> and then make a decision.
>
> There is currently a set of file operations:
>
> @@ -48,7 +90,11 @@ const struct file_operations bus1_fops = {
> .owner = THIS_MODULE,
> .open = bus1_fop_open,
> .release = bus1_fop_release,
> + .poll = bus1_fop_poll,
> .llseek = noop_llseek,
> + .mmap = bus1_fop_mmap,
> + .unlocked_ioctl = bus1_peer_ioctl,
> + .compat_ioctl = bus1_peer_ioctl,
> .show_fdinfo = bus1_fop_show_fdinfo,
> };
>
> and then another set of ioctls:
>
> +enum {
> + BUS1_CMD_PEER_DISCONNECT = _IOWR(BUS1_IOCTL_MAGIC, 0x00,
> + __u64),
> + BUS1_CMD_PEER_QUERY = _IOWR(BUS1_IOCTL_MAGIC, 0x01,
> + struct bus1_cmd_peer_reset),
> + BUS1_CMD_PEER_RESET = _IOWR(BUS1_IOCTL_MAGIC, 0x02,
> + struct bus1_cmd_peer_reset),
> + BUS1_CMD_HANDLE_RELEASE = _IOWR(BUS1_IOCTL_MAGIC, 0x10,
> + __u64),
> + BUS1_CMD_HANDLE_TRANSFER = _IOWR(BUS1_IOCTL_MAGIC, 0x11,
> + struct bus1_cmd_handle_transfer),
> + BUS1_CMD_NODES_DESTROY = _IOWR(BUS1_IOCTL_MAGIC, 0x20,
> + struct bus1_cmd_nodes_destroy),
> + BUS1_CMD_SLICE_RELEASE = _IOWR(BUS1_IOCTL_MAGIC, 0x30,
> + __u64),
> + BUS1_CMD_SEND = _IOWR(BUS1_IOCTL_MAGIC, 0x40,
> + struct bus1_cmd_send),
> + BUS1_CMD_RECV = _IOWR(BUS1_IOCTL_MAGIC, 0x50,
> + struct bus1_cmd_recv),
> +};
>
> I think there is no alternative to having some sort of file descriptor
> with the basic operations you have above, but there is a question of
> how to get that file descriptor if the ioctls get changed to a syscall,
> the basic options being:
I could see the point of wanting a syscall to get the fd (your second
option below), but as I said, not sure I see why we would want to use
syscalls instead of ioctls.
> - Keep using a chardev. This works, but feels a little odd to me,
> and I can't think of any other interfaces combining syscalls with
> a chardev.
>
> - Have one syscall that returns an open file descriptor, replacing
> the fops->open() function. One advantage is that you can pass
> additional arguments in that you can't have with open.
> An example for this would be mqueue_open().
If we are going to change it, this might makes sense to me. It would
allow you to get the fd without having to have access to some
character device.
> - Have a mountable file system, and use open() on that to create
> connections. Advantages are that it's fairly easy to have one
> instance per fs-namespace, and you can have user-defined naming
> of objects in the file system.
Note that currently we only have one object (/dev/bus1) and each fd is
disconnected from anything else on creation, so not sure what benefits
a filesystem (or several instances of it) would give?
> For the other operations, the obvious translation would be to
> turn each ioctl command into one syscall, but that may not always
> be the best representation. One limitation is that you cannot
> generally have more than six 'long' arguments on a lot of
> architectures, and passing 'u64' arguments to syscalls is awkward.
>
> For some of the commands, the transformation would be straightforward
> if we assume that the 'u64' arguments can actually be 'long',
> I guess like this:
>
> +struct bus1_cmd_handle_transfer {
> + __u64 flags;
> + __u64 src_handle;
> + __u64 dst_fd;
> + __u64 dst_handle;
> +} __attribute__((__aligned__(8)));
>
> long bus1_handle_transfer(int fd, unsigned long handle,
> int dst_fd, unsigned long *dst_handle, unsigned int flags);
>
> +struct bus1_cmd_nodes_destroy {
> + __u64 flags;
> + __u64 ptr_nodes;
> + __u64 n_nodes;
> +} __attribute__((__aligned__(8)));
>
> long bus1_nodes_destroy(int fd, u64 *ptr_nodes,
> long n_nodes, unsigned int flags);
>
> However, the peer_reset would exceed the 6-argument limit when you count
> the initial file descriptor even if you assume that 'flags' can be
> made 32-bit:
>
> +struct bus1_cmd_peer_reset {
> + __u64 flags;
> + __u64 peer_flags;
> + __u32 max_slices;
> + __u32 max_handles;
> + __u32 max_inflight_bytes;
> + __u32 max_inflight_fds;
> +} __attribute__((__aligned__(8)));
>
> maybe something slightly ugly like
>
> long bus1_peer_reset(int fd, const struct bus1_peer_limits *param,
> unsigned int flags);
>
> a library might provide a wrapper that passes all the limits
> as separate arguments.
>
> The receive function would be fairly straightforward again, as
> we just pass a pointer to the returned message, and all inputs
> can be arguments, but the send command with this structure
>
> +struct bus1_cmd_send {
> + __u64 flags;
> + __u64 ptr_destinations;
> + __u64 ptr_errors;
> + __u64 n_destinations;
> + __u64 ptr_vecs;
> + __u64 n_vecs;
> + __u64 ptr_handles;
> + __u64 n_handles;
> + __u64 ptr_fds;
> + __u64 n_fds;
> +} __attribute__((__aligned__(8)));
>
> is really tricky, as it's such a central interface but it's
> also really complex, with its five indirect pointers to
> variable-length arrays, making a total of 11 arguments
> (including the first fd). Turning this into a syscall would
> probably make a more efficient interface, so maybe some
> of the arrays can be turned into a single argument and
> require the user to call it multiple times instead of the
> kernel looping around it.
>
> The minimal version would be something like
>
> long bus1_send(int fd, long dst, struct iovec *vecs, int n_vecs,
> long handle, int dst_fd);
>
> so you already get to six arguments with one destination, one
> handle and one fd but no flags. Replacing vecs/n_vecs with pointer
> and length doesn't help either, so I guess whatever we do here
> we have to use some indirect structure.
>
> Arnd
[toc] | [prev] | [next] | [standalone]
| From | Linus Torvalds <torvalds@linux-foundation.org> |
|---|---|
| Date | 2016-10-27 18:40 +0200 |
| Subject | Re: [RFC v1 02/14] bus1: provide stub cdev /dev/bus1 |
| Message-ID | <swVSG-4lA-25@gated-at.bofh.it> |
| In reply to | #1510389 |
On Thu, Oct 27, 2016 at 8:25 AM, Tom Gundersen <teg@jklm.no> wrote:
>
> Could you elaborate on why you think syscalls would be more
> appropriate than ioctls?
ioctl's tend to be a horrid mess both for things like compat.but also
for things like system call tracing and filtering (ie BPF).
The compat mess is fixable by making sure you always use 64-bit fields
rather than pointers everywhere and everything is aligned. The
tracing and filtering one not so much.
Linus
[toc] | [prev] | [next] | [standalone]
| From | Tom Gundersen <teg@jklm.no> |
|---|---|
| Date | 2016-10-27 18:50 +0200 |
| Subject | Re: [RFC v1 02/14] bus1: provide stub cdev /dev/bus1 |
| Message-ID | <swW2m-4oW-23@gated-at.bofh.it> |
| In reply to | #1510470 |
On Thu, Oct 27, 2016 at 6:37 PM, Linus Torvalds <torvalds@linux-foundation.org> wrote: > On Thu, Oct 27, 2016 at 8:25 AM, Tom Gundersen <teg@jklm.no> wrote: >> >> Could you elaborate on why you think syscalls would be more >> appropriate than ioctls? > > ioctl's tend to be a horrid mess both for things like compat.but also > for things like system call tracing and filtering (ie BPF). > > The compat mess is fixable by making sure you always use 64-bit fields > rather than pointers everywhere and everything is aligned. This we do. > The > tracing and filtering one not so much. Got it. Thanks. Tom
[toc] | [prev] | [next] | [standalone]
| From | Arnd Bergmann <arnd@arndb.de> |
|---|---|
| Date | 2016-10-30 00:20 +0200 |
| Subject | Re: [RFC v1 02/14] bus1: provide stub cdev /dev/bus1 |
| Message-ID | <sxK8N-4kU-1@gated-at.bofh.it> |
| In reply to | #1510389 |
On Thursday 27 October 2016, Tom Gundersen wrote: > On Thu, Oct 27, 2016 at 11:11 AM, Arnd Bergmann <arnd@arndb.de> wrote: > > On Thursday, October 27, 2016 1:54:05 AM CEST Tom Gundersen wrote: > >> On Thu, Oct 27, 2016 at 1:19 AM, Andy Lutomirski <luto@amacapital.net> wrote: > >> > This may have been covered elsewhere, but could this use syscalls instead? > >> > >> Yes, syscalls would work essentially the same. For now, we are using a > >> cdev as it makes it a lot more convenient to develop and test as an > >> out-of-tree module, but that could be changed easily before the final > >> submission, if that's what we want. > > > > > > Generally speaking, I think syscalls would be appropriate here, and put > > bus1 into a similar category as the other ipc interfaces (shm, msg, sem, > > mqueue, ...). > > Could you elaborate on why you think syscalls would be more > appropriate than ioctls? Linus already answered this, but I'd also add that core kernel features just make sense to be syscalls, rather than stuffing them in a random device driver. > > - Have a mountable file system, and use open() on that to create > > connections. Advantages are that it's fairly easy to have one > > instance per fs-namespace, and you can have user-defined naming > > of objects in the file system. > > Note that currently we only have one object (/dev/bus1) and each fd is > disconnected from anything else on creation, so not sure what benefits > a filesystem (or several instances of it) would give? I have not tried to understand some of the main concepts of bus1, so I simply assumed that there was some way of looking up handles of other instances. Using a file system gives you a natural way to look up resources by name the way we do e.g. for mq_open(), and it lets you easy decide whether containers should share a view of the same namespace by mounting the same instance of the file system into them or having separate instances. If you don't ever need to look up a handle by name in bus1, using a mountable file system would not help you. Arnd
[toc] | [prev] | [next] | [standalone]
| From | David Herrmann <dh.herrmann@gmail.com> |
|---|---|
| Date | 2016-10-26 21:30 +0200 |
| Subject | [RFC v1 09/14] bus1: provide transaction context for multicasts |
| Message-ID | <swC3D-87o-7@gated-at.bofh.it> |
| In reply to | #1509715 |
From: Tom Gundersen <teg@jklm.no>
The transaction engine is an object that lives on the stack and is used
to stage and commit multicasts properly. Unlike unicasts, a multicast
cannot just be queued on each destination, but must be properly
synchronized. This requires us to first stage each message on their
respective destination, then sync and tick the clocks, and eventual
commit all messages.
The transaction context implements this logic for both, unicasts and
multicasts. It hides the timestamp handling and takes care to properly
synchronize accesses to the peer queues.
Signed-off-by: Tom Gundersen <teg@jklm.no>
Signed-off-by: David Herrmann <dh.herrmann@gmail.com>
---
ipc/bus1/Makefile | 1 +
ipc/bus1/peer.c | 2 +
ipc/bus1/peer.h | 3 +
ipc/bus1/tx.c | 360 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
ipc/bus1/tx.h | 102 ++++++++++++++++
5 files changed, 468 insertions(+)
create mode 100644 ipc/bus1/tx.c
create mode 100644 ipc/bus1/tx.h
diff --git a/ipc/bus1/Makefile b/ipc/bus1/Makefile
index c689917..e3c7dd7 100644
--- a/ipc/bus1/Makefile
+++ b/ipc/bus1/Makefile
@@ -1,6 +1,7 @@
bus1-y := \
main.o \
peer.o \
+ tx.o \
user.o \
util.o \
util/active.o \
diff --git a/ipc/bus1/peer.c b/ipc/bus1/peer.c
index a6fbca01..3421f8c 100644
--- a/ipc/bus1/peer.c
+++ b/ipc/bus1/peer.c
@@ -70,6 +70,7 @@ struct bus1_peer *bus1_peer_new(void)
/* initialize data section */
mutex_init(&peer->data.lock);
+ bus1_queue_init(&peer->data.queue);
/* initialize peer-private section */
mutex_init(&peer->local.lock);
@@ -131,6 +132,7 @@ struct bus1_peer *bus1_peer_free(struct bus1_peer *peer)
mutex_destroy(&peer->local.lock);
/* deinitialize data section */
+ bus1_queue_deinit(&peer->data.queue);
mutex_destroy(&peer->data.lock);
/* deinitialize constant fields */
diff --git a/ipc/bus1/peer.h b/ipc/bus1/peer.h
index 277fcf8..149ddf6 100644
--- a/ipc/bus1/peer.h
+++ b/ipc/bus1/peer.h
@@ -54,6 +54,7 @@
#include <linux/wait.h>
#include "user.h"
#include "util/active.h"
+#include "util/queue.h"
struct cred;
struct dentry;
@@ -71,6 +72,7 @@ struct pid_namespace;
* @active: active references
* @debugdir: debugfs root of this peer, or NULL/ERR_PTR
* @data.lock: data lock
+ * @data.queue: message queue
* @local.lock: local peer runtime lock
*/
struct bus1_peer {
@@ -86,6 +88,7 @@ struct bus1_peer {
struct {
struct mutex lock;
+ struct bus1_queue queue;
} data;
struct {
diff --git a/ipc/bus1/tx.c b/ipc/bus1/tx.c
new file mode 100644
index 0000000..6ff8949
--- /dev/null
+++ b/ipc/bus1/tx.c
@@ -0,0 +1,360 @@
+/*
+ * Copyright (C) 2013-2016 Red Hat, Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by the
+ * Free Software Foundation; either version 2.1 of the License, or (at
+ * your option) any later version.
+ */
+
+#include <linux/bitops.h>
+#include <linux/err.h>
+#include <linux/kernel.h>
+#include <linux/mutex.h>
+#include <linux/wait.h>
+#include "peer.h"
+#include "tx.h"
+#include "util/active.h"
+#include "util/queue.h"
+
+static void bus1_tx_push(struct bus1_tx *tx,
+ struct bus1_queue_node **list,
+ struct bus1_queue_node *qnode)
+{
+ struct bus1_peer *peer = qnode->owner;
+
+ /*
+ * Push @qnode onto one of the lists in @tx (specified as @list). Note
+ * that each list has different locking/ordering requirements, which
+ * the caller has to verify. This helper does not check them.
+ *
+ * Whenever something is pushed on a list, we make sure it has the tx
+ * set as group. Furthermore, we tell lockdep that its peer was
+ * released. This is required to allow holding hundreds of peers in a
+ * multicast without exceeding the lockdep limits of allowed locks held
+ * in parallel.
+ * Note that pushing a qnode on a list consumes the qnode together with
+ * its set owner. The caller must not access it, except by popping it
+ * from the list or using one of the internal list-iterators. In other
+ * words, we say that a caller must be aware of lockdep limitations
+ * whenever they hold an unlimited number of peers. However, if they
+ * make sure they only ever hold a fixed number, but use transaction
+ * lists to stash them, the transaction lists make sure to properly
+ * avoid lockdep limitations.
+ */
+
+ WARN_ON(qnode->group && tx != qnode->group);
+ WARN_ON(qnode->next || qnode == *list);
+
+ qnode->group = tx;
+ qnode->next = *list;
+ *list = qnode;
+
+ if (peer)
+ bus1_active_lockdep_released(&peer->active);
+}
+
+static struct bus1_queue_node *
+bus1_tx_pop(struct bus1_tx *tx, struct bus1_queue_node **list)
+{
+ struct bus1_queue_node *qnode = *list;
+ struct bus1_peer *peer;
+
+ /*
+ * This pops the first entry off a list on a transaction. Different
+ * lists have different locking requirements. This helper does not
+ * validate the context.
+ *
+ * Note that we need to tell lockdep about the acquired peer when
+ * returning the qnode. See bus1_tx_push() for details.
+ */
+
+ if (qnode) {
+ *list = qnode->next;
+ qnode->next = NULL;
+ peer = qnode->owner;
+ if (peer)
+ bus1_active_lockdep_acquired(&peer->active);
+ }
+
+ return qnode;
+}
+
+/*
+ * This starts an iterator for a singly-linked list with head-elements given as
+ * @list. @iter is filled with the first element, and its *acquired* peer is
+ * returned. You *must* call bus1_tx_next() on @iter, otherwise you will run
+ * into lockdep-ref-leaks. IOW: don't bail out of your loop with 'break'.
+ *
+ * It is supposed to be used like this:
+ *
+ * for (peer = bus1_tx_first(tx, &tx->foo, &qnode);
+ * qnode;
+ * peer = bus1_tx_next(tx, &qnode))
+ * bar();
+ */
+static struct bus1_peer *bus1_tx_first(struct bus1_tx *tx,
+ struct bus1_queue_node *list,
+ struct bus1_queue_node **iter)
+{
+ struct bus1_peer *peer;
+
+ if ((*iter = list)) {
+ peer = list->owner;
+ if (!peer)
+ return tx->origin;
+
+ bus1_active_lockdep_acquired(&peer->active);
+ return peer;
+ }
+
+ return NULL;
+}
+
+/*
+ * This continues an iteration of a singly-linked list started via
+ * bus1_tx_first(). It returns the same information (see it for details).
+ */
+static struct bus1_peer *bus1_tx_next(struct bus1_tx *tx,
+ struct bus1_queue_node **iter)
+{
+ struct bus1_queue_node *qnode = *iter;
+ struct bus1_peer *peer = qnode->owner;
+
+ if (peer)
+ bus1_active_lockdep_released(&peer->active);
+
+ return bus1_tx_first(tx, qnode->next, iter);
+}
+
+static void bus1_tx_stage(struct bus1_tx *tx,
+ struct bus1_queue_node *qnode,
+ struct bus1_queue_node **list,
+ u64 *timestamp)
+{
+ struct bus1_peer *peer = qnode->owner ?: tx->origin;
+
+ WARN_ON(test_bit(BUS1_TX_BIT_SEALED, &tx->flags));
+ WARN_ON(bus1_queue_node_is_queued(qnode));
+ lockdep_assert_held(&peer->data.lock);
+
+ bus1_tx_push(tx, list, qnode);
+ *timestamp = bus1_queue_stage(&peer->data.queue, qnode, *timestamp);
+}
+
+/**
+ * bus1_tx_stage_sync() - stage message
+ * @tx: transaction to operate on
+ * @qnode: message to stage
+ *
+ * This stages @qnode on the transaction @tx. It is an error to call this on a
+ * qnode that is already staged. The caller must set qnode->owner to the
+ * destination peer and acquire it. If it is NULL, it is assumed to be the same
+ * as the origin of the transaction.
+ *
+ * The caller must hold the data-lock of the destination peer.
+ *
+ * This consumes @qnode. The caller must increment the required reference
+ * counts to make sure @qnode does not vanish.
+ */
+void bus1_tx_stage_sync(struct bus1_tx *tx, struct bus1_queue_node *qnode)
+{
+ bus1_tx_stage(tx, qnode, &tx->sync, &tx->timestamp);
+}
+
+/**
+ * bus1_tx_stage_later() - postpone message
+ * @tx: transaction to operate on
+ * @qnode: message to postpone
+ *
+ * This queues @qnode on @tx, but does not stage it. It will be staged just
+ * before the transaction is committed. This can be used over
+ * bus1_tx_stage_sync() if no immediate staging is necessary, or if required
+ * locks cannot be taken.
+ *
+ * It is a caller-error if @qnode is already part of a transaction.
+ */
+void bus1_tx_stage_later(struct bus1_tx *tx, struct bus1_queue_node *qnode)
+{
+ bus1_tx_push(tx, &tx->postponed, qnode);
+}
+
+/**
+ * bus1_tx_join() - HIC SUNT DRACONES!
+ * @whom: whom to join
+ * @qnode: who joins
+ *
+ * This makes @qnode join the on-going transaction of @whom. That is, it is
+ * semantically equivalent of calling:
+ *
+ * bus1_tx_stage_sync(whom->group, qnode);
+ *
+ * However, you can only dereference whom->group while it is still ongoing.
+ * Once committed, it might be a stale pointer. This function safely checks for
+ * the required conditions and bails out if too late.
+ *
+ * The caller must hold the data locks of both peers (target of @whom and
+ * @qnode). @node->owner must not be NULL! Furthermore, @qnode must not be
+ * staged into any transaction, yet.
+ *
+ * In general, this function is not what you want. There is no guarantee that
+ * you can join the transaction, hence a negative return value must be expected
+ * by the caller and handled gracefully. In that case, this function guarantees
+ * that the clock of the holder of @qnode is synced with the transaction of
+ * @whom, and as such is correctly ordered against the transaction.
+ *
+ * If this function returns "false", you must settle on the transaction before
+ * visibly reacting to it. That is, user-space must not see that you failed to
+ * join the transaction before the transaction is settled!
+ *
+ * Return: True if successfull, false if too late.
+ */
+bool bus1_tx_join(struct bus1_queue_node *whom, struct bus1_queue_node *qnode)
+{
+ struct bus1_peer *peer = qnode->owner;
+ struct bus1_tx *tx;
+ u64 timestamp;
+
+ WARN_ON(!peer);
+ WARN_ON(qnode->group);
+ lockdep_assert_held(&peer->data.lock);
+
+ if (bus1_queue_node_is_staging(whom)) {
+ /*
+ * The anchor we want to join is marked as staging. We know its
+ * holder is locked by the caller, hence we know that its
+ * transaction must still be ongoing and at some point commit
+ * @whom (blocking on the lock we currently hold). This means,
+ * we are allowed to dereference @whom->group safely.
+ * Now, if the transaction has not yet acquired a commit
+ * timestamp, we simply stage @qnode and asynchronously join
+ * the transaction. But if the transaction is already sealed,
+ * we cannot join anymore. Hence, we instead copy the timestamp
+ * for our fallback.
+ */
+ WARN_ON(!(tx = whom->group));
+ lockdep_assert_held(&tx->origin->data.lock);
+
+ if (!test_bit(BUS1_TX_BIT_SEALED, &tx->flags)) {
+ bus1_tx_stage(tx, qnode, &tx->async, &tx->async_ts);
+ return true;
+ }
+
+ timestamp = tx->timestamp;
+ } else {
+ /*
+ * The anchor to join is not marked as staging, hence we cannot
+ * dereference its transaction (the stack-frame might be gone
+ * already). Instead, we just copy the timestamp and try our
+ * fallback below.
+ */
+ timestamp = bus1_queue_node_get_timestamp(whom);
+ }
+
+ /*
+ * The transaction of @whom has already acquired a commit timestamp.
+ * Hence, we cannot join the transaction. However, we can try to inject
+ * a synthetic entry into the queue of @peer. All we must make sure is
+ * that there is at least one entry ordered in front of it. Hence, we
+ * use bus1_queue_commit_synthetic(). If this synthetic entry would be
+ * the new front, the commit fails. This is, because we cannot know
+ * whether this peer already dequeued something to-be-ordered after
+ * this fake entry.
+ * In the case that the insertion fails, we make sure to have synced
+ * its clock before. This guarantees that any further actions of this
+ * peer are guaranteed to be ordered after the transaction to join.
+ */
+ qnode->group = whom->group;
+ bus1_queue_sync(&peer->data.queue, timestamp);
+ return bus1_queue_commit_synthetic(&peer->data.queue, qnode, timestamp);
+}
+
+/**
+ * bus1_tx_commit() - commit transaction
+ * @tx: transaction to operate on
+ *
+ * Commit a transaction. First all postponed entries are staged, then we commit
+ * all messages that belong to this transaction. This works with any number of
+ * messages.
+ *
+ * Return: This returns the commit timestamp used.
+ */
+u64 bus1_tx_commit(struct bus1_tx *tx)
+{
+ struct bus1_queue_node *qnode, **tail;
+ struct bus1_peer *peer, *origin = tx->origin;
+
+ if (WARN_ON(test_bit(BUS1_TX_BIT_SEALED, &tx->flags)))
+ return tx->timestamp;
+
+ /*
+ * Stage Round
+ * Callers can stage messages manually via bus1_tx_stage_*(). However,
+ * if they cannot lock the destination queue for whatever reason, we
+ * support postponing it. In that case, it is linked into tx->postponed
+ * and we stage it here for them.
+ */
+ while ((qnode = bus1_tx_pop(tx, &tx->postponed))) {
+ peer = qnode->owner ?: tx->origin;
+
+ mutex_lock(&peer->data.lock);
+ bus1_tx_stage_sync(tx, qnode);
+ mutex_unlock(&peer->data.lock);
+ }
+
+ /*
+ * Acquire Commit TS
+ * Now that everything is staged, we atomically acquire a commit
+ * timestamp from the transaction origin. We store it on the
+ * transaction, so async joins are still possible. We also seal the
+ * transaction at the same time, to prevent async stages.
+ */
+ mutex_lock(&origin->data.lock);
+ bus1_queue_sync(&origin->data.queue, max(tx->timestamp, tx->async_ts));
+ tx->timestamp = bus1_queue_tick(&origin->data.queue);
+ WARN_ON(test_and_set_bit(BUS1_TX_BIT_SEALED, &tx->flags));
+ mutex_unlock(&origin->data.lock);
+
+ /*
+ * Sync Round
+ * Before any effect of this transaction is visible, we must make sure
+ * to sync all clocks. This guarantees that the first receiver of the
+ * message cannot (via side-channels) induce messages into the queue of
+ * the other receivers, before they get the message as well.
+ */
+ tail = &tx->sync;
+ do {
+ for (peer = bus1_tx_first(tx, *tail, &qnode);
+ qnode;
+ peer = bus1_tx_next(tx, &qnode)) {
+ tail = &qnode->next;
+
+ mutex_lock(&peer->data.lock);
+ bus1_queue_sync(&peer->data.queue, tx->timestamp);
+ mutex_unlock(&peer->data.lock);
+ }
+
+ /* append async-list to the tail of the previous list */
+ *tail = tx->async;
+ tx->async = NULL;
+ } while (*tail);
+
+ /*
+ * Commit Round
+ * Now that everything is staged and the clocks synced, we can finally
+ * commit all the messages on their respective queues. Iterate over
+ * each message again, commit it, and release the pinned destination.
+ */
+ while ((qnode = bus1_tx_pop(tx, &tx->sync))) {
+ peer = qnode->owner ?: tx->origin;
+
+ mutex_lock(&peer->data.lock);
+ bus1_queue_commit_staged(&peer->data.queue, &peer->waitq,
+ qnode, tx->timestamp);
+ mutex_unlock(&peer->data.lock);
+
+ bus1_peer_release(qnode->owner);
+ }
+
+ return tx->timestamp;
+}
diff --git a/ipc/bus1/tx.h b/ipc/bus1/tx.h
new file mode 100644
index 0000000..a057df4
--- /dev/null
+++ b/ipc/bus1/tx.h
@@ -0,0 +1,102 @@
+#ifndef __BUS1_TX_H
+#define __BUS1_TX_H
+
+/*
+ * Copyright (C) 2013-2016 Red Hat, Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by the
+ * Free Software Foundation; either version 2.1 of the License, or (at
+ * your option) any later version.
+ */
+
+/**
+ * DOC: Transactions
+ *
+ * The transaction engine is an object that lives an the stack and is used to
+ * stage and commit multicasts properly. Unlike unicasts, a multicast cannot
+ * just be queued on each destination, but must be properly synchronized. This
+ * requires us to first stage each message on their respective destination,
+ * then sync and tick the clocks, and eventual commit all messages.
+ */
+
+#include <linux/err.h>
+#include <linux/kernel.h>
+
+struct bus1_peer;
+struct bus1_queue_node;
+
+/**
+ * enum bus1_tx_bits - transaction flags
+ * @BUS1_TX_BIT_SEALED: The transaction is sealed, no new messages can
+ * be added to the transaction. The commit of all
+ * staged messages is ongoing.
+ */
+enum bus1_tx_bits {
+ BUS1_TX_BIT_SEALED,
+};
+
+/**
+ * struct bus1_tx - transaction context
+ * @origin: origin of this transaction
+ * @sync: unlocked list of staged messages
+ * @async: locked list of staged messages
+ * @postponed: unlocked list of unstaged messages
+ * @flags: transaction flags
+ * @timestamp: unlocked timestamp of this transaction
+ * @async_ts: locked timestamp cache of async list
+ */
+struct bus1_tx {
+ struct bus1_peer *origin;
+ struct bus1_queue_node *sync;
+ struct bus1_queue_node *async;
+ struct bus1_queue_node *postponed;
+ unsigned long flags;
+ u64 timestamp;
+ u64 async_ts;
+};
+
+void bus1_tx_stage_sync(struct bus1_tx *tx, struct bus1_queue_node *qnode);
+void bus1_tx_stage_later(struct bus1_tx *tx, struct bus1_queue_node *qnode);
+
+bool bus1_tx_join(struct bus1_queue_node *whom, struct bus1_queue_node *qnode);
+
+u64 bus1_tx_commit(struct bus1_tx *tx);
+
+/**
+ * bus1_tx_init() - initialize transaction context
+ * @tx: transaction context to operate on
+ * @origin: origin of this transaction
+ *
+ * This initializes a transaction context. The initiating peer must be pinned
+ * by the caller for the entire lifetime of @tx (until bus1_tx_deinit() is
+ * called) and given as @origin.
+ */
+static inline void bus1_tx_init(struct bus1_tx *tx, struct bus1_peer *origin)
+{
+ tx->origin = origin;
+ tx->sync = NULL;
+ tx->async = NULL;
+ tx->postponed = NULL;
+ tx->flags = 0;
+ tx->timestamp = 0;
+ tx->async_ts = 0;
+}
+
+/**
+ * bus1_tx_deinit() - deinitialize transaction context
+ * @tx: transaction context to operate on
+ *
+ * This deinitializes a transaction context previously created via
+ * bus1_tx_init(). This is merely for debugging, as no resources are pinned on
+ * the transaction. However, if any message was staged on the transaction, it
+ * must be committed via bus1_tx_commit() before it is deinitialized.
+ */
+static inline void bus1_tx_deinit(struct bus1_tx *tx)
+{
+ WARN_ON(tx->sync);
+ WARN_ON(tx->async);
+ WARN_ON(tx->postponed);
+}
+
+#endif /* __BUS1_TX_H */
--
2.10.1
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2016-10-28 16:40 +0200 |
| Subject | Re: [RFC v1 09/14] bus1: provide transaction context for multicasts |
| Message-ID | <sxgu5-15Y-5@gated-at.bofh.it> |
| In reply to | #1509717 |
On Wed, Oct 26, 2016 at 09:18:05PM +0200, David Herrmann wrote: > From: Tom Gundersen <teg@jklm.no> > > The transaction engine is an object that lives on the stack and is used > to stage and commit multicasts properly. Unlike unicasts, a multicast > cannot just be queued on each destination, but must be properly > synchronized. This requires us to first stage each message on their > respective destination, then sync and tick the clocks, and eventual > commit all messages. > > The transaction context implements this logic for both, unicasts and > multicasts. It hides the timestamp handling and takes care to properly > synchronize accesses to the peer queues. > > Signed-off-by: Tom Gundersen <teg@jklm.no> > Signed-off-by: David Herrmann <dh.herrmann@gmail.com> > --- > ipc/bus1/Makefile | 1 + > ipc/bus1/peer.c | 2 + > ipc/bus1/peer.h | 3 + > ipc/bus1/tx.c | 360 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ > ipc/bus1/tx.h | 102 ++++++++++++++++ See, this is way more than 4 lines. You don't need any of this for causality.
[toc] | [prev] | [next] | [standalone]
| From | David Herrmann <dh.herrmann@gmail.com> |
|---|---|
| Date | 2016-10-26 21:30 +0200 |
| Subject | [RFC v1 07/14] bus1: tracking user contexts |
| Message-ID | <swC3D-87o-9@gated-at.bofh.it> |
| In reply to | #1509715 |
From: Tom Gundersen <teg@jklm.no>
Different users can communicate via bus1, and many resources are shared
between multiple users. The bus1_user object represents the UID of a
user, like "struct user_struct" does in the kernel core. It is used to
account global resources, apply limits, and calculate quotas if
different UIDs communicate with each other.
All dynamic resources have global per-user limits, which cannot be
exceeded by a user. They prevent a single user from exhausting local
resources. Each peer that is created is always owned by the user that
initialized it. All resources allocated on that peer are accounted on
that pinned user. Additionally to global resources, there are local
limits per peer, that can be controlled by each peer individually
(e.g., specifying a maximum pool size). Those local limits allow a user
to distribute the globally available resources across its peer
instances.
Since bus1 allows communication across UID boundaries, any such
transmission of resources must be properly accounted. Bus1 employs
dynamic quotas to fairly distribute available resources. Those quotas
make sure that available resources of a peer cannot be exhausted by
remote UIDs, but are fairly divided among all communicating peers.
This only implements the user tracking, the resource limits will be
added in follow-up patches.
Signed-off-by: Tom Gundersen <teg@jklm.no>
Signed-off-by: David Herrmann <dh.herrmann@gmail.com>
---
ipc/bus1/Makefile | 1 +
ipc/bus1/main.c | 3 ++
ipc/bus1/user.c | 153 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
ipc/bus1/user.h | 67 ++++++++++++++++++++++++
4 files changed, 224 insertions(+)
create mode 100644 ipc/bus1/user.c
create mode 100644 ipc/bus1/user.h
diff --git a/ipc/bus1/Makefile b/ipc/bus1/Makefile
index 3c90657..94d79e0 100644
--- a/ipc/bus1/Makefile
+++ b/ipc/bus1/Makefile
@@ -1,5 +1,6 @@
bus1-y := \
main.o \
+ user.o \
util/active.o \
util/flist.o \
util/pool.o \
diff --git a/ipc/bus1/main.c b/ipc/bus1/main.c
index 02412a7..526347d 100644
--- a/ipc/bus1/main.c
+++ b/ipc/bus1/main.c
@@ -16,6 +16,7 @@
#include <linux/module.h>
#include "main.h"
#include "tests.h"
+#include "user.h"
static int bus1_fop_open(struct inode *inode, struct file *file)
{
@@ -64,6 +65,7 @@ static int __init bus1_modinit(void)
error:
debugfs_remove(bus1_debugdir);
+ bus1_user_modexit();
return r;
}
@@ -71,6 +73,7 @@ static void __exit bus1_modexit(void)
{
misc_deregister(&bus1_misc);
debugfs_remove(bus1_debugdir);
+ bus1_user_modexit();
pr_info("unloaded\n");
}
diff --git a/ipc/bus1/user.c b/ipc/bus1/user.c
new file mode 100644
index 0000000..0498ab4
--- /dev/null
+++ b/ipc/bus1/user.c
@@ -0,0 +1,153 @@
+/*
+ * Copyright (C) 2013-2016 Red Hat, Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by the
+ * Free Software Foundation; either version 2.1 of the License, or (at
+ * your option) any later version.
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+#include <linux/err.h>
+#include <linux/idr.h>
+#include <linux/kernel.h>
+#include <linux/kref.h>
+#include <linux/moduleparam.h>
+#include <linux/mutex.h>
+#include <linux/rcupdate.h>
+#include <linux/sched.h>
+#include <linux/slab.h>
+#include <linux/uidgid.h>
+#include "user.h"
+
+static DEFINE_MUTEX(bus1_user_lock);
+static DEFINE_IDR(bus1_user_idr);
+
+/**
+ * bus1_user_modexit() - clean up global resources of user accounting
+ *
+ * This function cleans up any remaining global resources that were allocated
+ * by the user accounting helpers. The caller must make sure that no user
+ * object is referenced anymore, before calling this. This function just clears
+ * caches and verifies nothing is leaked.
+ *
+ * This is meant to be called on module-exit.
+ */
+void bus1_user_modexit(void)
+{
+ WARN_ON(!idr_is_empty(&bus1_user_idr));
+ idr_destroy(&bus1_user_idr);
+ idr_init(&bus1_user_idr);
+}
+
+static struct bus1_user *bus1_user_new(void)
+{
+ struct bus1_user *user;
+
+ user = kmalloc(sizeof(*user), GFP_KERNEL);
+ if (!user)
+ return ERR_PTR(-ENOMEM);
+
+ kref_init(&user->ref);
+ user->uid = INVALID_UID;
+ mutex_init(&user->lock);
+
+ return user;
+}
+
+static void bus1_user_free(struct kref *ref)
+{
+ struct bus1_user *user = container_of(ref, struct bus1_user, ref);
+
+ lockdep_assert_held(&bus1_user_lock);
+
+ if (likely(uid_valid(user->uid)))
+ idr_remove(&bus1_user_idr, __kuid_val(user->uid));
+ mutex_destroy(&user->lock);
+ kfree_rcu(user, rcu);
+}
+
+/**
+ * bus1_user_ref_by_uid() - get a user object for a uid
+ * @uid: uid of the user
+ *
+ * Find and return the user object for the uid if it exists, otherwise create
+ * it first.
+ *
+ * Return: A user object for the given uid, ERR_PTR on failure.
+ */
+struct bus1_user *bus1_user_ref_by_uid(kuid_t uid)
+{
+ struct bus1_user *user;
+ int r;
+
+ if (WARN_ON(!uid_valid(uid)))
+ return ERR_PTR(-ENOTRECOVERABLE);
+
+ /* fast-path: acquire reference via rcu */
+ rcu_read_lock();
+ user = idr_find(&bus1_user_idr, __kuid_val(uid));
+ if (user && !kref_get_unless_zero(&user->ref))
+ user = NULL;
+ rcu_read_unlock();
+ if (user)
+ return user;
+
+ /* slow-path: try again with IDR locked */
+ mutex_lock(&bus1_user_lock);
+ user = idr_find(&bus1_user_idr, __kuid_val(uid));
+ if (likely(!bus1_user_ref(user))) {
+ user = bus1_user_new();
+ if (!IS_ERR(user)) {
+ user->uid = uid;
+ r = idr_alloc(&bus1_user_idr, user, __kuid_val(uid),
+ __kuid_val(uid) + 1, GFP_KERNEL);
+ if (r < 0) {
+ user->uid = INVALID_UID; /* couldn't insert */
+ kref_put(&user->ref, bus1_user_free);
+ user = ERR_PTR(r);
+ }
+ }
+ }
+ mutex_unlock(&bus1_user_lock);
+
+ return user;
+}
+
+/**
+ * bus1_user_ref() - acquire reference
+ * @user: user to acquire, or NULL
+ *
+ * Acquire an additional reference to a user-object. The caller must already
+ * own a reference.
+ *
+ * If NULL is passed, this is a no-op.
+ *
+ * Return: @user is returned.
+ */
+struct bus1_user *bus1_user_ref(struct bus1_user *user)
+{
+ if (user)
+ kref_get(&user->ref);
+ return user;
+}
+
+/**
+ * bus1_user_unref() - release reference
+ * @user: user to release, or NULL
+ *
+ * Release a reference to a user-object.
+ *
+ * If NULL is passed, this is a no-op.
+ *
+ * Return: NULL is returned.
+ */
+struct bus1_user *bus1_user_unref(struct bus1_user *user)
+{
+ if (user) {
+ if (kref_put_mutex(&user->ref, bus1_user_free, &bus1_user_lock))
+ mutex_unlock(&bus1_user_lock);
+ }
+
+ return NULL;
+}
diff --git a/ipc/bus1/user.h b/ipc/bus1/user.h
new file mode 100644
index 0000000..6cdc264
--- /dev/null
+++ b/ipc/bus1/user.h
@@ -0,0 +1,67 @@
+#ifndef __BUS1_USER_H
+#define __BUS1_USER_H
+
+/*
+ * Copyright (C) 2013-2016 Red Hat, Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by the
+ * Free Software Foundation; either version 2.1 of the License, or (at
+ * your option) any later version.
+ */
+
+/**
+ * DOC: Users
+ *
+ * Different users can communicate via bus1, and many resources are shared
+ * between multiple users. The bus1_user object represents the UID of a user,
+ * like "struct user_struct" does in the kernel core. It is used to account
+ * global resources, apply limits, and calculate quotas if different UIDs
+ * communicate with each other.
+ *
+ * All dynamic resources have global per-user limits, which cannot be exceeded
+ * by a user. They prevent a single user from exhausting local resources. Each
+ * peer that is created is always owned by the user that initialized it. All
+ * resources allocated on that peer are accounted on that pinned user.
+ * Additionally to global resources, there are local limits per peer, that can
+ * be controlled by each peer individually (e.g., specifying a maximum pool
+ * size). Those local limits allow a user to distribute the globally available
+ * resources across its peer instances.
+ *
+ * Since bus1 allows communication across UID boundaries, any such transmission
+ * of resources must be properly accounted. Bus1 employs dynamic quotas to
+ * fairly distribute available resources. Those quotas make sure that available
+ * resources of a peer cannot be exhausted by remote UIDs, but are fairly
+ * divided among all communicating peers.
+ */
+
+#include <linux/atomic.h>
+#include <linux/idr.h>
+#include <linux/kref.h>
+#include <linux/mutex.h>
+#include <linux/types.h>
+#include <linux/uidgid.h>
+
+/**
+ * struct bus1_user - resource accounting for users
+ * @ref: reference counter
+ * @uid: UID of the user
+ * @lock: object lock
+ * @rcu: rcu
+ */
+struct bus1_user {
+ struct kref ref;
+ kuid_t uid;
+ struct mutex lock;
+ struct rcu_head rcu;
+};
+
+/* module cleanup */
+void bus1_user_modexit(void);
+
+/* users */
+struct bus1_user *bus1_user_ref_by_uid(kuid_t uid);
+struct bus1_user *bus1_user_ref(struct bus1_user *user);
+struct bus1_user *bus1_user_unref(struct bus1_user *user);
+
+#endif /* __BUS1_USER_H */
--
2.10.1
[toc] | [prev] | [next] | [standalone]
| From | David Herrmann <dh.herrmann@gmail.com> |
|---|---|
| Date | 2016-10-26 21:30 +0200 |
| Subject | [RFC v1 03/14] bus1: util - active reference utility library |
| Message-ID | <swC3D-87o-11@gated-at.bofh.it> |
| In reply to | #1509715 |
From: Tom Gundersen <teg@jklm.no>
The bus1_active object implements active references. They work
similarly to plain object reference counters, but allow disabling
any new references from being taken.
Each bus1_active object goes through a set of states:
NEW: Initial state, no active references can be acquired
ACTIVE: Live state, active references can be acquired
DRAINING: Deactivated but lingering, no active references
can be acquired
DRAINED: Deactivated and all active references were dropped
RELEASED: Fully drained and synchronously released
Initially, all bus1_active objects are in state NEW. As soon as they're
activated, they enter ACTIVE and active references can be acquired.
This is the normal, live state. Once the object is deactivated, it
enters state DRAINING. No new active references can be acquired, but
some threads might still own active references. Once all those are
dropped, the object enters state DRAINED. Now the object can be
released a *single* time, before it enters state RELEASED and is
finished. It cannot be re-used anymore.
Active-references are very useful to track threads that invoke callbacks
on an object. As long as a callback is running, an active reference is
held, and as such the object is usually protected from being destroyed.
The destructor of the object needs to deactivate *and* drain the object,
before releasing resources.
Active references will be used heavy by the upcoming bus1_peer object.
Whenever a peer operates on a remote peer, it must acquire and hold an
active reference on that remote peer. This guarantees that the remote
peer will wait for this operation to finish before possibly
disconnecting from the bus.
In concept, active-references can be seen as rw-locks. However, they
have much more strict state-transitions. Prior art can be seen in
super-blocks ('atomic_t s_active'), and kernfs ('atomic_t active').
Signed-off-by: Tom Gundersen <teg@jklm.no>
Signed-off-by: David Herrmann <dh.herrmann@gmail.com>
---
ipc/bus1/Makefile | 3 +-
ipc/bus1/util/active.c | 419 +++++++++++++++++++++++++++++++++++++++++++++++++
ipc/bus1/util/active.h | 154 ++++++++++++++++++
3 files changed, 575 insertions(+), 1 deletion(-)
create mode 100644 ipc/bus1/util/active.c
create mode 100644 ipc/bus1/util/active.h
diff --git a/ipc/bus1/Makefile b/ipc/bus1/Makefile
index d3a4491..9e491691 100644
--- a/ipc/bus1/Makefile
+++ b/ipc/bus1/Makefile
@@ -1,5 +1,6 @@
bus1-y := \
- main.o
+ main.o \
+ util/active.o
obj-$(CONFIG_BUS1) += bus1.o
diff --git a/ipc/bus1/util/active.c b/ipc/bus1/util/active.c
new file mode 100644
index 0000000..5f5fdaa
--- /dev/null
+++ b/ipc/bus1/util/active.c
@@ -0,0 +1,419 @@
+/*
+ * Copyright (C) 2013-2016 Red Hat, Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by the
+ * Free Software Foundation; either version 2.1 of the License, or (at
+ * your option) any later version.
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+#include <linux/atomic.h>
+#include <linux/kernel.h>
+#include <linux/sched.h>
+#include <linux/wait.h>
+#include "active.h"
+
+/*
+ * Bias values track states of "active references". They're all negative. If an
+ * object is active, its active-ref-counter is >=0 and tracks all active
+ * references. Once an object is deactivated, we subtract ACTIVE_BIAS. This
+ * means, the counter is now negative but still counts the active references.
+ * Once it drops to exactly ACTIVE_BIAS, we know all active references were
+ * dropped. Exactly one thread will change it to ACTIVE_RELEASE now, perform
+ * cleanup and then put it into ACTIVE_DONE. Once released, all other threads
+ * that tried deactivating the node will now be woken up (thus, they wait until
+ * the object is fully done).
+ * The initial state during object setup is ACTIVE_NEW. If an object is
+ * directly deactivated without having ever been active, it is put into
+ * ACTIVE_RELEASE_DIRECT instead of ACTIVE_BIAS. This tracks this one-bit state
+ * across deactivation. The task putting it into ACTIVE_RELEASE now knows
+ * whether the object was active before or not.
+ *
+ * We support lockdep annotations for 'active references'. We treat active
+ * references as a read-trylock, and deactivation as a write-lock.
+ *
+ * Some archs implement atomic_sub(v) with atomic_add(-v), so reserve INT_MIN
+ * to avoid overflows if multiplied by -1.
+ */
+#define BUS1_ACTIVE_RELEASE_DIRECT (BUS1_ACTIVE_BIAS - 1)
+#define BUS1_ACTIVE_RELEASE (BUS1_ACTIVE_BIAS - 2)
+#define BUS1_ACTIVE_DONE (BUS1_ACTIVE_BIAS - 3)
+#define BUS1_ACTIVE_NEW (BUS1_ACTIVE_BIAS - 4)
+#define _BUS1_ACTIVE_RESERVED (BUS1_ACTIVE_BIAS - 5)
+
+/**
+ * bus1_active_init_private() - initialize object
+ * @active: object to initialize
+ *
+ * This initializes an active-object. The initial state is NEW, and as such no
+ * active reference can be acquired. The object must be activated first.
+ *
+ * This is an internal helper. Always use the public bus1_active_init() macro
+ * which does proper lockdep initialization for private key classes.
+ */
+void bus1_active_init_private(struct bus1_active *active)
+{
+ atomic_set(&active->count, BUS1_ACTIVE_NEW);
+}
+
+/**
+ * bus1_active_deinit() - destroy object
+ * @active: object to destroy
+ *
+ * Destroy an active-object. The object must have been initialized via
+ * bus1_active_init(), deactivated via bus1_active_deactivate(), drained via
+ * bus1_active_drain() and cleaned via bus1_active_cleanup(), before you can
+ * destroy it. Alternatively, it can also be destroyed if still in state NEW.
+ *
+ * This function only does sanity checks, it does not modify the object itself.
+ * There is no allocated memory, so there is nothing to do.
+ */
+void bus1_active_deinit(struct bus1_active *active)
+{
+ int v;
+
+ v = atomic_read(&active->count);
+ WARN_ON(v != BUS1_ACTIVE_NEW && v != BUS1_ACTIVE_DONE);
+}
+
+/**
+ * bus1_active_is_new() - check whether object is new
+ * @active: object to check
+ *
+ * This checks whether the object is new, that is, it was never activated nor
+ * deactivated.
+ *
+ * Return: True if new, false if not.
+ */
+bool bus1_active_is_new(struct bus1_active *active)
+{
+ return atomic_read(&active->count) == BUS1_ACTIVE_NEW;
+}
+
+/**
+ * bus1_active_is_active() - check whether object is active
+ * @active: object to check
+ *
+ * This checks whether the given active-object is active. That is, the object
+ * was already activated, but not deactivated, yet.
+ *
+ * Note that this function does not give any guarantee that the object is still
+ * active/inactive at the time this call returns. It only serves as a barrier.
+ *
+ * Return: True if active, false if not.
+ */
+bool bus1_active_is_active(struct bus1_active *active)
+{
+ return atomic_read(&active->count) >= 0;
+}
+
+/**
+ * bus1_active_is_deactivated() - check whether object was deactivated
+ * @active: object to check
+ *
+ * This checks whether the given active-object was already deactivated. That
+ * is, the object was actively deactivated (state NEW does *not* count as
+ * deactivated) via bus1_active_deactivate().
+ *
+ * Once this function returns true, it cannot change again on this object.
+ *
+ * Return: True if already deactivated, false if not.
+ */
+bool bus1_active_is_deactivated(struct bus1_active *active)
+{
+ int v = atomic_read(&active->count);
+
+ return v > BUS1_ACTIVE_NEW && v < 0;
+}
+
+/**
+ * bus1_active_is_drained() - check whether object is drained
+ * @active: object to check
+ *
+ * This checks whether the given object was already deactivated and is fully
+ * drained. That is, no active references to the object exist, nor can they be
+ * acquired, anymore.
+ *
+ * Return: True if drained, false if not.
+ */
+bool bus1_active_is_drained(struct bus1_active *active)
+{
+ int v = atomic_read(&active->count);
+
+ return v > BUS1_ACTIVE_NEW && v <= BUS1_ACTIVE_BIAS;
+}
+
+/**
+ * bus1_active_activate() - activate object
+ * @active: object to activate
+ *
+ * This activates the given object, if it is still in state NEW. Otherwise, it
+ * is a no-op (and the object might already be deactivated).
+ *
+ * Once this returns successfully, active references can be acquired.
+ *
+ * Return: True if this call activated it, false if it was already activated,
+ * or deactivated.
+ */
+bool bus1_active_activate(struct bus1_active *active)
+{
+ return atomic_cmpxchg(&active->count,
+ BUS1_ACTIVE_NEW, 0) == BUS1_ACTIVE_NEW;
+}
+
+/**
+ * bus1_active_deactivate() - deactivate object
+ * @active: object to deactivate
+ *
+ * This deactivates the given object, if not already done by someone else. Once
+ * this returns, no new active references can be acquired.
+ *
+ * Return: True if this call deactivated the object, false if it was already
+ * deactivated by someone else.
+ */
+bool bus1_active_deactivate(struct bus1_active *active)
+{
+ int v, v1;
+
+ v = atomic_cmpxchg(&active->count,
+ BUS1_ACTIVE_NEW, BUS1_ACTIVE_RELEASE_DIRECT);
+ if (unlikely(v == BUS1_ACTIVE_NEW))
+ return true;
+
+ /*
+ * This adds BUS1_ACTIVE_BIAS to the counter, unless its negative:
+ * atomic_add_unless_negative(&active->count, BUS1_ACTIVE_BIAS)
+ * No such global helper exists, so it is inline here.
+ */
+ for (v = atomic_read(&active->count); v >= 0; v = v1) {
+ v1 = atomic_cmpxchg(&active->count, v, v + BUS1_ACTIVE_BIAS);
+ if (likely(v1 == v))
+ return true;
+ }
+
+ return false;
+}
+
+/**
+ * bus1_active_drain() - drain active references
+ * @active: object to drain
+ * @waitq: wait-queue linked to @active
+ *
+ * This waits for all active-references on @active to be dropped. It uses the
+ * passed wait-queue to sleep. It must be the same wait-queue that is used when
+ * calling bus1_active_release().
+ *
+ * The caller must guarantee that bus1_active_deactivate() was called before.
+ *
+ * This function can be safely called in parallel on multiple CPUs.
+ *
+ * Semantically (and also enforced by lockdep), this call behaves like a
+ * down_write(), followed by an up_write(), on this active object.
+ */
+void bus1_active_drain(struct bus1_active *active, wait_queue_head_t *waitq)
+{
+ if (WARN_ON(!bus1_active_is_deactivated(active)))
+ return;
+
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+ /*
+ * We pretend this is a down_write_interruptible() and all but
+ * the release-context get interrupted. This is required, as we
+ * cannot call lock_acquired() on multiple threads without
+ * synchronization. Hence, only the release-context will do
+ * this, all others just release the lock.
+ */
+ lock_acquire_exclusive(&active->dep_map, /* lock */
+ 0, /* subclass */
+ 0, /* try-lock */
+ NULL, /* nest underneath */
+ _RET_IP_); /* IP */
+ if (atomic_read(&active->count) > BUS1_ACTIVE_BIAS)
+ lock_contended(&active->dep_map, _RET_IP_);
+#endif
+
+ /* wait until all active references were dropped */
+ wait_event(*waitq, atomic_read(&active->count) <= BUS1_ACTIVE_BIAS);
+
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+ /*
+ * Pretend that no-one got the lock, but everyone got interrupted
+ * instead. That is, they released the lock without ever actually
+ * getting it locked.
+ */
+ lock_release(&active->dep_map, /* lock */
+ 1, /* nested (no-op) */
+ _RET_IP_); /* instruction pointer */
+#endif
+}
+
+/**
+ * bus1_active_cleanup() - cleanup drained object
+ * @active: object to release
+ * @waitq: wait-queue linked to @active, or NULL
+ * @cleanup: cleanup callback, or NULL
+ * @userdata: userdata for callback
+ *
+ * This performs the final object cleanup. The caller must guarantee that the
+ * object is drained, by calling bus1_active_drain().
+ *
+ * This function invokes the passed cleanup callback on the object. However, it
+ * guarantees that this is done exactly once. If there're multiple parallel
+ * callers, this will pick one randomly and make all others wait until it is
+ * done. If you call this after it was already cleaned up, this is a no-op
+ * and only serves as barrier.
+ *
+ * If @waitq is NULL, the wait is skipped and the call returns immediately. In
+ * this case, another thread has entered before, but there is no guarantee that
+ * they finished executing the cleanup callback, yet.
+ *
+ * If @waitq is non-NULL, this call behaves like a down_write(), followed by an
+ * up_write(), just like bus1_active_drain(). If @waitq is NULL, this rather
+ * behaves like a down_write_trylock(), optionally followed by an up_write().
+ *
+ * Return: True if this is the thread that released it, false otherwise.
+ */
+bool bus1_active_cleanup(struct bus1_active *active,
+ wait_queue_head_t *waitq,
+ void (*cleanup)(struct bus1_active *, void *),
+ void *userdata)
+{
+ int v;
+
+ if (WARN_ON(!bus1_active_is_drained(active)))
+ return false;
+
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+ /*
+ * We pretend this is a down_write_interruptible() and all but
+ * the release-context get interrupted. This is required, as we
+ * cannot call lock_acquired() on multiple threads without
+ * synchronization. Hence, only the release-context will do
+ * this, all others just release the lock.
+ */
+ lock_acquire_exclusive(&active->dep_map,/* lock */
+ 0, /* subclass */
+ !waitq, /* try-lock */
+ NULL, /* nest underneath */
+ _RET_IP_); /* IP */
+#endif
+
+ /* mark object as RELEASE */
+ v = atomic_cmpxchg(&active->count,
+ BUS1_ACTIVE_RELEASE_DIRECT, BUS1_ACTIVE_RELEASE);
+ if (v != BUS1_ACTIVE_RELEASE_DIRECT)
+ v = atomic_cmpxchg(&active->count,
+ BUS1_ACTIVE_BIAS, BUS1_ACTIVE_RELEASE);
+
+ /*
+ * If this is the thread that marked the object as RELEASE, we
+ * perform the actual release. Otherwise, we wait until the
+ * release is done and the node is marked as DRAINED.
+ */
+ if (v == BUS1_ACTIVE_BIAS || v == BUS1_ACTIVE_RELEASE_DIRECT) {
+
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+ /* we're the release-context and acquired the lock */
+ lock_acquired(&active->dep_map, _RET_IP_);
+#endif
+
+ if (cleanup)
+ cleanup(active, userdata);
+
+ /* mark as DONE */
+ atomic_set(&active->count, BUS1_ACTIVE_DONE);
+ if (waitq)
+ wake_up_all(waitq);
+ } else if (waitq) {
+
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+ /* we're contended against the release context */
+ lock_contended(&active->dep_map, _RET_IP_);
+#endif
+
+ /* wait until object is DONE */
+ wait_event(*waitq,
+ atomic_read(&active->count) == BUS1_ACTIVE_DONE);
+ }
+
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+ /*
+ * No-one but the release-context acquired the lock. However,
+ * that does not matter as we simply treat this as
+ * 'interrupted'. Everyone releases the lock, but only one
+ * caller really got it.
+ */
+ lock_release(&active->dep_map, /* lock */
+ 1, /* nested (no-op) */
+ _RET_IP_); /* instruction pointer */
+#endif
+
+ /* true if we released it */
+ return v == BUS1_ACTIVE_BIAS || v == BUS1_ACTIVE_RELEASE_DIRECT;
+}
+
+/**
+ * bus1_active_lockdep_acquired() - acquire lockdep reader
+ * @active: object to acquire lockdep reader of, or NULL
+ *
+ * Whenever you acquire an active reference via bus1_active_acquire(), this
+ * function is implicitly called afterwards. It enables lockdep annotations and
+ * tells lockdep that you acquired the active reference.
+ *
+ * However, lockdep cannot support arbitrary depths, hence, we allow
+ * temporarily dropping the lockdep-annotation via
+ * bus1_active_lockdep_release(), and acquiring them later again via
+ * bus1_active_lockdep_acquire().
+ *
+ * Example: If you need to pin a large number of objects, you would acquire each
+ * of them individually via bus1_active_acquire(). Then you would
+ * perform state tracking, etc. on that object. Before you continue
+ * with the next, you call bus1_active_lockdep_released(), to pretend
+ * you released the lock (but you still retain your active reference).
+ * Now you continue with pinning the next object, etc. until you
+ * pinned all objects you need.
+ *
+ * If you now need to access one of your pinned objects (or want to
+ * release them eventually), you call bus1_active_lockdep_acquired()
+ * before accessing the object. This enables the lockdep annotations
+ * again. This cannot fail, ever. You still own the active reference
+ * at all times.
+ * Once you're done with the single object, you either release your
+ * entire active reference via bus1_active_release(), or you
+ * temporarily disable lockdep via bus1_active_lockdep_released()
+ * again, in case you need the pinned object again later.
+ *
+ * Note that you can acquired multiple active references just fine. The only
+ * reason those lockdep helpers are provided, is if you need to acquire a
+ * *large* number at the same time. Lockdep is usually limited to a depths of 64
+ * so you cannot hold more locks at the same time.
+ */
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+void bus1_active_lockdep_acquired(struct bus1_active *active)
+{
+ if (active)
+ lock_acquire_shared(&active->dep_map, /* lock */
+ 0, /* subclass */
+ 1, /* try-lock */
+ NULL, /* nest underneath */
+ _RET_IP_); /* IP */
+}
+#endif
+
+/**
+ * bus1_active_lockdep_released() - release lockdep reader
+ * @active: object to release lockdep reader of, or NULL
+ *
+ * This is the counterpart of bus1_active_lockdep_acquired(). See its
+ * documentation for details.
+ */
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+void bus1_active_lockdep_released(struct bus1_active *active)
+{
+ if (active)
+ lock_release(&active->dep_map, /* lock */
+ 1, /* nested (no-op) */
+ _RET_IP_); /* instruction pointer */
+}
+#endif
diff --git a/ipc/bus1/util/active.h b/ipc/bus1/util/active.h
new file mode 100644
index 0000000..462e7cf
--- /dev/null
+++ b/ipc/bus1/util/active.h
@@ -0,0 +1,154 @@
+#ifndef __BUS1_ACTIVE_H
+#define __BUS1_ACTIVE_H
+
+/*
+ * Copyright (C) 2013-2016 Red Hat, Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by the
+ * Free Software Foundation; either version 2.1 of the License, or (at
+ * your option) any later version.
+ */
+
+/**
+ * DOC: Active References
+ *
+ * The bus1_active object implements active references. They work similarly to
+ * plain object reference counters, but allow disabling any new references from
+ * being taken.
+ *
+ * Each bus1_active object goes through a set of states:
+ * NEW: Initial state, no active references can be acquired
+ * ACTIVE: Live state, active references can be acquired
+ * DRAINING: Deactivated but lingering, no active references can be acquired
+ * DRAINED: Deactivated and all active references were dropped
+ * RELEASED: Fully drained and synchronously released
+ *
+ * Initially, all bus1_active objects are in state NEW. As soon as they're
+ * activated, they enter ACTIVE and active references can be acquired. This is
+ * the normal, live state. Once the object is deactivated, it enters state
+ * DRAINING. No new active references can be acquired, but some threads might
+ * still own active references. Once all those are dropped, the object enters
+ * state DRAINED. Now the object can be released a *single* time, before it
+ * enters state RELEASED and is finished. It cannot be re-used anymore.
+ *
+ * Active-references are very useful to track threads that call methods on an
+ * object. As long as a method is running, an active reference is held, and as
+ * such the object is usually protected from being destroyed. The destructor of
+ * the object needs to deactivate *and* drain the object, before releasing
+ * resources.
+ *
+ * Note that active-references cannot be used to manage their own backing
+ * memory. That is, they do not replace normal reference counts.
+ */
+
+#include <linux/atomic.h>
+#include <linux/lockdep.h>
+#include <linux/sched.h>
+#include <linux/wait.h>
+
+/* base value for counter-bias, see BUS1_ACTIVE_* constants for details */
+#define BUS1_ACTIVE_BIAS (INT_MIN + 5)
+
+/**
+ * struct bus1_active - active references
+ * @count: active reference counter
+ * @dep_map: lockdep annotations
+ *
+ * This object should be treated like a simple atomic_t. It will only contain
+ * more fields in the case of lockdep-enabled compilations.
+ *
+ * Users must embed this object into their parent structures and create/destroy
+ * it via bus1_active_init() and bus1_active_deinit().
+ */
+struct bus1_active {
+ atomic_t count;
+
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+ struct lockdep_map dep_map;
+#endif
+};
+
+void bus1_active_init_private(struct bus1_active *active);
+void bus1_active_deinit(struct bus1_active *active);
+bool bus1_active_is_new(struct bus1_active *active);
+bool bus1_active_is_active(struct bus1_active *active);
+bool bus1_active_is_deactivated(struct bus1_active *active);
+bool bus1_active_is_drained(struct bus1_active *active);
+bool bus1_active_activate(struct bus1_active *active);
+bool bus1_active_deactivate(struct bus1_active *active);
+void bus1_active_drain(struct bus1_active *active, wait_queue_head_t *waitq);
+bool bus1_active_cleanup(struct bus1_active *active,
+ wait_queue_head_t *waitq,
+ void (*cleanup) (struct bus1_active *, void *),
+ void *userdata);
+
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+# define bus1_active_init(_active) \
+ ({ \
+ static struct lock_class_key bus1_active_lock_key; \
+ lockdep_init_map(&(_active)->dep_map, "bus1.active", \
+ &bus1_active_lock_key, 0); \
+ bus1_active_init_private(_active); \
+ })
+void bus1_active_lockdep_acquired(struct bus1_active *active);
+void bus1_active_lockdep_released(struct bus1_active *active);
+#else
+# define bus1_active_init(_active) bus1_active_init_private(_active)
+static inline void bus1_active_lockdep_acquired(struct bus1_active *active) {}
+static inline void bus1_active_lockdep_released(struct bus1_active *active) {}
+#endif
+
+/**
+ * bus1_active_acquire() - acquire active reference
+ * @active: object to acquire active reference to, or NULL
+ *
+ * This acquires an active reference to the passed object. If the object was
+ * not activated, yet, or if it was already deactivated, this will fail and
+ * return NULL. If a reference was successfully acquired, this will return
+ * @active.
+ *
+ * If NULL is passed, this is a no-op and always returns NULL.
+ *
+ * This behaves as a down_read_trylock(). Use bus1_active_release() to release
+ * the reference again and get the matching up_read().
+ *
+ * Return: @active if reference was acquired, NULL if not.
+ */
+static inline struct bus1_active *
+bus1_active_acquire(struct bus1_active *active)
+{
+ if (active && atomic_inc_unless_negative(&active->count))
+ bus1_active_lockdep_acquired(active);
+ else
+ active = NULL;
+ return active;
+}
+
+/**
+ * bus1_active_release() - release active reference
+ * @active: object to release active reference of, or NULL
+ * @waitq: wait-queue linked to @active, or NULL
+ *
+ * This releases an active reference that was previously acquired via
+ * bus1_active_acquire().
+ *
+ * This is a no-op if NULL is passed.
+ *
+ * This behaves like an up_read().
+ *
+ * Return: NULL is returned.
+ */
+static inline struct bus1_active *
+bus1_active_release(struct bus1_active *active, wait_queue_head_t *waitq)
+{
+ if (active) {
+ bus1_active_lockdep_released(active);
+ if (atomic_dec_return(&active->count) == BUS1_ACTIVE_BIAS)
+ if (waitq)
+ wake_up(waitq);
+ }
+ return NULL;
+}
+
+#endif /* __BUS1_ACTIVE_H */
--
2.10.1
[toc] | [prev] | [next] | [standalone]
| From | David Herrmann <dh.herrmann@gmail.com> |
|---|---|
| Date | 2016-10-26 21:30 +0200 |
| Subject | [RFC v1 05/14] bus1: util - pool utility library |
| Message-ID | <swC3D-87o-13@gated-at.bofh.it> |
| In reply to | #1509715 |
From: Tom Gundersen <teg@jklm.no>
A bus1-pool is a shmem-backed memory pool shared between userspace and
the kernel. The pool is used to transfer memory from the kernel to
userspace without requiring userspace to pre-allocate space.
The pool is managed in slices, which are published to userspace when
they are ready to be read and must be released by userspace when
userspace is done with them.
Userspace has read-only access to its pools and the kernel has
read-write access, but published slices are not altered.
This pool implementation will be used by bus1 message transactions to
support single-copy data transfers, directly from the sender's address
space into the pool of the destination peer. The allocation algorithm
is based on the Android Binder code and has served their needs well for
many years now.
Signed-off-by: Tom Gundersen <teg@jklm.no>
Signed-off-by: David Herrmann <dh.herrmann@gmail.com>
---
ipc/bus1/Makefile | 3 +-
ipc/bus1/util/pool.c | 572 +++++++++++++++++++++++++++++++++++++++++++++++++++
ipc/bus1/util/pool.h | 164 +++++++++++++++
3 files changed, 738 insertions(+), 1 deletion(-)
create mode 100644 ipc/bus1/util/pool.c
create mode 100644 ipc/bus1/util/pool.h
diff --git a/ipc/bus1/Makefile b/ipc/bus1/Makefile
index 6db6d13..ca8e19d 100644
--- a/ipc/bus1/Makefile
+++ b/ipc/bus1/Makefile
@@ -1,7 +1,8 @@
bus1-y := \
main.o \
util/active.o \
- util/flist.o
+ util/flist.o \
+ util/pool.o
obj-$(CONFIG_BUS1) += bus1.o
diff --git a/ipc/bus1/util/pool.c b/ipc/bus1/util/pool.c
new file mode 100644
index 0000000..2ddbffb
--- /dev/null
+++ b/ipc/bus1/util/pool.c
@@ -0,0 +1,572 @@
+/*
+ * Copyright (C) 2013-2016 Red Hat, Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by the
+ * Free Software Foundation; either version 2.1 of the License, or (at
+ * your option) any later version.
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+#include <linux/aio.h>
+#include <linux/err.h>
+#include <linux/file.h>
+#include <linux/fs.h>
+#include <linux/highmem.h>
+#include <linux/kernel.h>
+#include <linux/mm.h>
+#include <linux/pagemap.h>
+#include <linux/rbtree.h>
+#include <linux/sched.h>
+#include <linux/shmem_fs.h>
+#include <linux/sizes.h>
+#include <linux/slab.h>
+#include <linux/uaccess.h>
+#include <linux/uio.h>
+#include "pool.h"
+
+static struct bus1_pool_slice *bus1_pool_slice_new(size_t offset, size_t size)
+{
+ struct bus1_pool_slice *slice;
+
+ if (offset > U32_MAX || size == 0 || size > BUS1_POOL_SLICE_SIZE_MAX)
+ return ERR_PTR(-EMSGSIZE);
+
+ slice = kmalloc(sizeof(*slice), GFP_KERNEL);
+ if (!slice)
+ return ERR_PTR(-ENOMEM);
+
+ slice->offset = offset;
+ slice->size = size;
+
+ return slice;
+}
+
+static struct bus1_pool_slice *
+bus1_pool_slice_free(struct bus1_pool_slice *slice)
+{
+ if (!slice)
+ return NULL;
+
+ kfree(slice);
+
+ return NULL;
+}
+
+/* insert slice into the free tree */
+static void bus1_pool_slice_link_free(struct bus1_pool_slice *slice,
+ struct bus1_pool *pool)
+{
+ struct rb_node **n, *prev = NULL;
+ struct bus1_pool_slice *ps;
+
+ n = &pool->slices_free.rb_node;
+ while (*n) {
+ prev = *n;
+ ps = container_of(prev, struct bus1_pool_slice, rb);
+ if (slice->size < ps->size)
+ n = &prev->rb_left;
+ else
+ n = &prev->rb_right;
+ }
+
+ rb_link_node(&slice->rb, prev, n);
+ rb_insert_color(&slice->rb, &pool->slices_free);
+}
+
+/* insert slice into the busy tree */
+static void bus1_pool_slice_link_busy(struct bus1_pool_slice *slice,
+ struct bus1_pool *pool)
+{
+ struct rb_node **n, *prev = NULL;
+ struct bus1_pool_slice *ps;
+
+ n = &pool->slices_busy.rb_node;
+ while (*n) {
+ prev = *n;
+ ps = container_of(prev, struct bus1_pool_slice, rb);
+ if (WARN_ON(slice->offset == ps->offset))
+ n = &prev->rb_right; /* add anyway */
+ else if (slice->offset < ps->offset)
+ n = &prev->rb_left;
+ else /* if (slice->offset > ps->offset) */
+ n = &prev->rb_right;
+ }
+
+ rb_link_node(&slice->rb, prev, n);
+ rb_insert_color(&slice->rb, &pool->slices_busy);
+
+ pool->allocated_size += slice->size;
+}
+
+/* find free slice big enough to hold @size bytes */
+static struct bus1_pool_slice *
+bus1_pool_slice_find_by_size(struct bus1_pool *pool, size_t size)
+{
+ struct bus1_pool_slice *ps, *closest = NULL;
+ struct rb_node *n;
+
+ n = pool->slices_free.rb_node;
+ while (n) {
+ ps = container_of(n, struct bus1_pool_slice, rb);
+ if (size < ps->size) {
+ closest = ps;
+ n = n->rb_left;
+ } else if (size > ps->size) {
+ n = n->rb_right;
+ } else /* if (size == ps->size) */ {
+ return ps;
+ }
+ }
+
+ return closest;
+}
+
+/* find used slice with given offset */
+static struct bus1_pool_slice *
+bus1_pool_slice_find_by_offset(struct bus1_pool *pool, size_t offset)
+{
+ struct bus1_pool_slice *ps;
+ struct rb_node *n;
+
+ n = pool->slices_busy.rb_node;
+ while (n) {
+ ps = container_of(n, struct bus1_pool_slice, rb);
+ if (offset < ps->offset)
+ n = n->rb_left;
+ else if (offset > ps->offset)
+ n = n->rb_right;
+ else /* if (offset == ps->offset) */
+ return ps;
+ }
+
+ return NULL;
+}
+
+/**
+ * bus1_pool_init() - create memory pool
+ * @pool: pool to operate on
+ * @filename: name to use for the shmem-file (only visible via /proc)
+ *
+ * Initialize a new pool object.
+ *
+ * Return: 0 on success, negative error code on failure.
+ */
+int bus1_pool_init(struct bus1_pool *pool, const char *filename)
+{
+ struct bus1_pool_slice *slice;
+ struct page *p;
+ struct file *f;
+ int r;
+
+ /* cannot calculate width of bitfields, so hardcode '4' as flag-size */
+ BUILD_BUG_ON(BUS1_POOL_SLICE_SIZE_BITS + 3 > 32);
+ BUILD_BUG_ON(BUS1_POOL_SLICE_SIZE_MAX > U32_MAX);
+
+ f = shmem_file_setup(filename, ALIGN(BUS1_POOL_SLICE_SIZE_MAX, 8),
+ VM_NORESERVE);
+ if (IS_ERR(f))
+ return PTR_ERR(f);
+
+ r = get_write_access(file_inode(f));
+ if (r < 0) {
+ fput(f);
+ return r;
+ }
+
+ pool->f = f;
+ pool->allocated_size = 0;
+ INIT_LIST_HEAD(&pool->slices);
+ pool->slices_free = RB_ROOT;
+ pool->slices_busy = RB_ROOT;
+
+ slice = bus1_pool_slice_new(0, BUS1_POOL_SLICE_SIZE_MAX);
+ if (IS_ERR(slice)) {
+ bus1_pool_deinit(pool);
+ return PTR_ERR(slice);
+ }
+
+ slice->free = true;
+ slice->ref_kernel = false;
+ slice->ref_user = false;
+
+ list_add(&slice->entry, &pool->slices);
+ bus1_pool_slice_link_free(slice, pool);
+
+ /*
+ * Touch first page of client pool so the initial allocation overhead
+ * is done during peer setup rather than a message transaction. This is
+ * really just an optimization to avoid some random peaks in common
+ * paths. It is not meant as ultimate protection.
+ */
+ p = shmem_read_mapping_page(file_inode(f)->i_mapping, 0);
+ if (!IS_ERR(p))
+ put_page(p);
+
+ return 0;
+}
+
+/**
+ * bus1_pool_deinit() - destroy pool
+ * @pool: pool to destroy, or NULL
+ *
+ * This destroys a pool that was previously create via bus1_pool_init(). If
+ * NULL is passed, or if @pool->f is NULL (i.e., the pool was initialized to 0
+ * but not created via bus1_pool_init(), yet), then this is a no-op.
+ *
+ * The caller must make sure that no kernel reference to any slice exists. Any
+ * pending user-space reference to any slice is dropped by this function.
+ */
+void bus1_pool_deinit(struct bus1_pool *pool)
+{
+ struct bus1_pool_slice *slice;
+
+ if (!pool || !pool->f)
+ return;
+
+ while ((slice = list_first_entry_or_null(&pool->slices,
+ struct bus1_pool_slice,
+ entry))) {
+ WARN_ON(slice->ref_kernel);
+ list_del(&slice->entry);
+ bus1_pool_slice_free(slice);
+ }
+
+ put_write_access(file_inode(pool->f));
+ fput(pool->f);
+ pool->f = NULL;
+}
+
+/**
+ * bus1_pool_alloc() - allocate memory
+ * @pool: pool to allocate memory from
+ * @size: number of bytes to allocate
+ *
+ * This allocates a new slice of @size bytes from the memory pool at @pool. The
+ * slice must be released via bus1_pool_release_kernel() by the caller. All
+ * slices are aligned to 8 bytes (both offset and size).
+ *
+ * If no suitable slice can be allocated, an error is returned.
+ *
+ * Each pool slice can have two different references, a kernel reference and a
+ * user-space reference. Initially, it only has a kernel-reference, which must
+ * be dropped via bus1_pool_release_kernel(). However, if you previously
+ * publish the slice via bus1_pool_publish(), it will also have a user-space
+ * reference, which user-space must (indirectly) release via a call to
+ * bus1_pool_release_user().
+ * A slice is only actually freed if neither reference exists, anymore. Hence,
+ * pool-slice can be held by both, the kernel and user-space, and both can rely
+ * on it staying around as long as they wish.
+ *
+ * Return: Pointer to new slice, or ERR_PTR on failure.
+ */
+struct bus1_pool_slice *bus1_pool_alloc(struct bus1_pool *pool, size_t size)
+{
+ struct bus1_pool_slice *slice, *ps;
+ size_t slice_size;
+
+ slice_size = ALIGN(size, 8);
+ if (slice_size == 0 || slice_size > BUS1_POOL_SLICE_SIZE_MAX)
+ return ERR_PTR(-EMSGSIZE);
+
+ /* find smallest suitable, free slice */
+ slice = bus1_pool_slice_find_by_size(pool, slice_size);
+ if (!slice)
+ return ERR_PTR(-EXFULL);
+
+ /* split slice if it doesn't match exactly */
+ if (slice_size < slice->size) {
+ ps = bus1_pool_slice_new(slice->offset + slice_size,
+ slice->size - slice_size);
+ if (IS_ERR(ps))
+ return ERR_CAST(ps);
+
+ ps->free = true;
+ ps->ref_kernel = false;
+ ps->ref_user = false;
+
+ list_add(&ps->entry, &slice->entry); /* add after @slice */
+ bus1_pool_slice_link_free(ps, pool);
+
+ slice->size = slice_size;
+ }
+
+ /* move from free-tree to busy-tree */
+ rb_erase(&slice->rb, &pool->slices_free);
+ bus1_pool_slice_link_busy(slice, pool);
+
+ slice->ref_kernel = true;
+ slice->ref_user = false;
+ slice->free = false;
+
+ return slice;
+}
+
+static void bus1_pool_free(struct bus1_pool *pool,
+ struct bus1_pool_slice *slice)
+{
+ struct bus1_pool_slice *ps;
+
+ /* don't free the slice if either has a reference */
+ if (slice->ref_kernel || slice->ref_user || WARN_ON(slice->free))
+ return;
+
+ /*
+ * To release a pool-slice, we first drop it from the busy-tree, then
+ * merge it with possible previous/following free slices and re-add it
+ * to the free-tree.
+ */
+
+ rb_erase(&slice->rb, &pool->slices_busy);
+
+ if (!WARN_ON(slice->size > pool->allocated_size))
+ pool->allocated_size -= slice->size;
+
+ if (pool->slices.next != &slice->entry) {
+ ps = container_of(slice->entry.prev, struct bus1_pool_slice,
+ entry);
+ if (ps->free) {
+ rb_erase(&ps->rb, &pool->slices_free);
+ list_del(&slice->entry);
+ ps->size += slice->size;
+ bus1_pool_slice_free(slice);
+ slice = ps; /* switch to previous slice */
+ }
+ }
+
+ if (pool->slices.prev != &slice->entry) {
+ ps = container_of(slice->entry.next, struct bus1_pool_slice,
+ entry);
+ if (ps->free) {
+ rb_erase(&ps->rb, &pool->slices_free);
+ list_del(&ps->entry);
+ slice->size += ps->size;
+ bus1_pool_slice_free(ps);
+ }
+ }
+
+ slice->free = true;
+ bus1_pool_slice_link_free(slice, pool);
+}
+
+/**
+ * bus1_pool_release_kernel() - release kernel-owned slice reference
+ * @pool: pool to free memory on
+ * @slice: slice to release
+ *
+ * This releases the kernel-reference to a slice that was previously allocated
+ * via bus1_pool_alloc(). This only releases the kernel reference to the slice.
+ * If the slice was already published to user-space, then their reference is
+ * left untouched. Once both references are gone, the memory is actually freed.
+ *
+ * Return: NULL is returned.
+ */
+struct bus1_pool_slice *
+bus1_pool_release_kernel(struct bus1_pool *pool, struct bus1_pool_slice *slice)
+{
+ if (!slice || WARN_ON(!slice->ref_kernel))
+ return NULL;
+
+ /* kernel must own a ref to @slice */
+ slice->ref_kernel = false;
+
+ bus1_pool_free(pool, slice);
+
+ return NULL;
+}
+
+/**
+ * bus1_pool_publish() - publish a slice
+ * @pool: pool to operate on
+ * @slice: slice to publish
+ *
+ * Publish a pool slice to user-space, so user-space can get access to it via
+ * the mapped pool memory. If the slice was already published, this is a no-op.
+ * Otherwise, the slice is marked as public and will only get freed once both
+ * the user-space reference *and* kernel-space reference are released.
+ */
+void bus1_pool_publish(struct bus1_pool *pool, struct bus1_pool_slice *slice)
+{
+ /* kernel must own a ref to @slice to publish it */
+ WARN_ON(!slice->ref_kernel);
+ slice->ref_user = true;
+}
+
+/**
+ * bus1_pool_release_user() - release a public slice
+ * @pool: pool to operate on
+ * @offset: offset of slice to release
+ * @n_slicesp: output variable to store number of released slices, or NULL
+ *
+ * Release the user-space reference to a pool-slice, specified via the offset
+ * of the slice. If both, the user-space reference *and* the kernel-space
+ * reference to the slice are gone, the slice will be actually freed.
+ *
+ * If no slice exists with the given offset, or if there is no user-space
+ * reference to the specified slice, an error is returned.
+ *
+ * Return: 0 on success, negative error code on failure.
+ */
+int bus1_pool_release_user(struct bus1_pool *pool,
+ size_t offset,
+ size_t *n_slicesp)
+{
+ struct bus1_pool_slice *slice;
+
+ slice = bus1_pool_slice_find_by_offset(pool, offset);
+ if (!slice || !slice->ref_user)
+ return -ENXIO;
+
+ if (n_slicesp)
+ *n_slicesp = !slice->ref_kernel;
+
+ slice->ref_user = false;
+ bus1_pool_free(pool, slice);
+
+ return 0;
+}
+
+/**
+ * bus1_pool_flush() - flush all user references
+ * @pool: pool to flush
+ * @n_slicesp: output variable to store number of released slices, or NULL
+ *
+ * This flushes all user-references to any slice in @pool. Kernel references
+ * are left untouched.
+ */
+void bus1_pool_flush(struct bus1_pool *pool, size_t *n_slicesp)
+{
+ struct bus1_pool_slice *slice;
+ struct rb_node *node, *t;
+ size_t n_slices = 0;
+
+ for (node = rb_first(&pool->slices_busy);
+ node && ((t = rb_next(node)), true);
+ node = t) {
+ slice = container_of(node, struct bus1_pool_slice, rb);
+ if (!slice->ref_user)
+ continue;
+
+ if (!slice->ref_kernel)
+ ++n_slices;
+
+ /*
+ * @slice (or the logically previous/next slice) might be freed
+ * by bus1_pool_free(). However, this only ever affects 'free'
+ * slices, never busy slices. Hence, @t is protected from
+ * removal.
+ */
+ slice->ref_user = false;
+ bus1_pool_free(pool, slice);
+ }
+
+ if (n_slicesp)
+ *n_slicesp = n_slices;
+}
+
+/**
+ * bus1_pool_mmap() - mmap the pool
+ * @pool: pool to operate on
+ * @vma: VMA to map to
+ *
+ * This maps the pools shmem file to the provided VMA. Only read-only mappings
+ * are allowed.
+ *
+ * Return: 0 on success, negative error code on failure.
+ */
+int bus1_pool_mmap(struct bus1_pool *pool, struct vm_area_struct *vma)
+{
+ if (unlikely(vma->vm_flags & VM_WRITE))
+ return -EPERM; /* deny write-access to the pool */
+
+ /* replace the connection file with our shmem file */
+ if (vma->vm_file)
+ fput(vma->vm_file);
+ vma->vm_file = get_file(pool->f);
+ vma->vm_flags &= ~VM_MAYWRITE;
+
+ /* calls into shmem_mmap(), which simply sets vm_ops */
+ return pool->f->f_op->mmap(pool->f, vma);
+}
+
+/**
+ * bus1_pool_write_iovec() - copy user memory to a slice
+ * @pool: pool to operate on
+ * @slice: slice to write to
+ * @offset: relative offset into slice memory
+ * @iov: iovec array, pointing to data to copy
+ * @n_iov: number of elements in @iov
+ * @total_len: total number of bytes to copy
+ *
+ * This copies the memory pointed to by @iov into the memory slice @slice at
+ * relative offset @offset (relative to begin of slice).
+ *
+ * Return: Numbers of bytes copied, negative error code on failure.
+ */
+ssize_t bus1_pool_write_iovec(struct bus1_pool *pool,
+ struct bus1_pool_slice *slice,
+ loff_t offset,
+ struct iovec *iov,
+ size_t n_iov,
+ size_t total_len)
+{
+ struct iov_iter iter;
+ ssize_t len;
+
+ if (WARN_ON(offset + total_len < offset) ||
+ WARN_ON(offset + total_len > slice->size) ||
+ WARN_ON(slice->ref_user))
+ return -EFAULT;
+ if (total_len < 1)
+ return 0;
+
+ offset += slice->offset;
+ iov_iter_init(&iter, WRITE, iov, n_iov, total_len);
+
+ len = vfs_iter_write(pool->f, &iter, &offset);
+
+ return (len >= 0 && len != total_len) ? -EFAULT : len;
+}
+
+/**
+ * bus1_pool_write_kvec() - copy kernel memory to a slice
+ * @pool: pool to operate on
+ * @slice: slice to write to
+ * @offset: relative offset into slice memory
+ * @iov: kvec array, pointing to data to copy
+ * @n_iov: number of elements in @iov
+ * @total_len: total number of bytes to copy
+ *
+ * This copies the memory pointed to by @iov into the memory slice @slice at
+ * relative offset @offset (relative to begin of slice).
+ *
+ * Return: Numbers of bytes copied, negative error code on failure.
+ */
+ssize_t bus1_pool_write_kvec(struct bus1_pool *pool,
+ struct bus1_pool_slice *slice,
+ loff_t offset,
+ struct kvec *iov,
+ size_t n_iov,
+ size_t total_len)
+{
+ struct iov_iter iter;
+ mm_segment_t old_fs;
+ ssize_t len;
+
+ if (WARN_ON(offset + total_len < offset) ||
+ WARN_ON(offset + total_len > slice->size) ||
+ WARN_ON(slice->ref_user))
+ return -EFAULT;
+ if (total_len < 1)
+ return 0;
+
+ offset += slice->offset;
+ iov_iter_kvec(&iter, WRITE | ITER_KVEC, iov, n_iov, total_len);
+
+ old_fs = get_fs();
+ set_fs(get_ds());
+ len = vfs_iter_write(pool->f, &iter, &offset);
+ set_fs(old_fs);
+
+ return (len >= 0 && len != total_len) ? -EFAULT : len;
+}
diff --git a/ipc/bus1/util/pool.h b/ipc/bus1/util/pool.h
new file mode 100644
index 0000000..f0e369b
--- /dev/null
+++ b/ipc/bus1/util/pool.h
@@ -0,0 +1,164 @@
+#ifndef __BUS1_POOL_H
+#define __BUS1_POOL_H
+
+/*
+ * Copyright (C) 2013-2016 Red Hat, Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by the
+ * Free Software Foundation; either version 2.1 of the License, or (at
+ * your option) any later version.
+ */
+
+/**
+ * DOC: Pools
+ *
+ * A pool is a shmem-backed memory pool shared between userspace and the kernel.
+ * The pool is used to transfer memory from the kernel to userspace without
+ * requiring userspace to allocate the memory.
+ *
+ * The pool is managed in slices, which are published to userspace when they are
+ * ready to be read and must be released by userspace when userspace is done
+ * with them.
+ *
+ * Userspace has read-only access to its pools and the kernel has read-write
+ * access, but published slices are not altered.
+ */
+
+#include <linux/kernel.h>
+#include <linux/rbtree.h>
+#include <linux/types.h>
+
+struct file;
+struct iovec;
+struct kvec;
+
+/* internal: number of bits available to slice size */
+#define BUS1_POOL_SLICE_SIZE_BITS (29)
+#define BUS1_POOL_SLICE_SIZE_MAX ((1 << BUS1_POOL_SLICE_SIZE_BITS) - 1)
+
+/**
+ * struct bus1_pool_slice - pool slice
+ * @offset: relative offset in parent pool
+ * @size: slice size
+ * @free: whether this slice is in-use or not
+ * @ref_kernel: whether a kernel reference exists
+ * @ref_user: whether a user reference exists
+ * @entry: link into linear list of slices
+ * @rb: link to busy/free rb-tree
+ *
+ * Each chunk of memory in the pool is managed as a slice. A slice can be
+ * accessible by both the kernel and user-space, and their access rights are
+ * managed independently. As long as the kernel has a reference to a slice, its
+ * offset and size can be accessed freely and will not change. Once the kernel
+ * drops its reference, it must not access the slice, anymore.
+ *
+ * To allow user-space access, the slice must be published. This marks the slice
+ * as referenced by user-space. Note that all slices are always readable by
+ * user-space, since the entire pool can be mapped. Publishing a slice only
+ * marks the slice as referenced by user-space, so it will not be modified or
+ * removed. Once user-space releases its reference, it should no longer access
+ * the slice as it might be modified and/or overwritten by other data.
+ *
+ * Only if neither kernel nor user-space have a reference to a slice, the slice
+ * is released. The kernel reference can only be acquired/released once, but
+ * user-space references can be published/released several times. In particular,
+ * if the kernel retains a reference when a slice is published and later
+ * released by userspace, the same slice can be published again in the future.
+ *
+ * Note that both kernel-space and user-space must be aware that slice
+ * references are not ref-counted. They are simple booleans. For the kernel-side
+ * this is obvious, as no ref/unref functions are provided. But user-space must
+ * be aware that the same slice being published several times does not increase
+ * the reference count.
+ */
+struct bus1_pool_slice {
+ u32 offset;
+
+ /* merge @size with flags to save 8 bytes per existing slice */
+ u32 size : BUS1_POOL_SLICE_SIZE_BITS;
+ u32 free : 1;
+ u32 ref_kernel : 1;
+ u32 ref_user : 1;
+
+ struct list_head entry;
+ struct rb_node rb;
+};
+
+/**
+ * struct bus1_pool - client pool
+ * @f: backing shmem file
+ * @allocated_size: currently allocated memory in bytes
+ * @slices: all slices sorted by address
+ * @slices_busy: tree of allocated slices
+ * @slices_free: tree of free slices
+ *
+ * A pool is used to allocate memory slices that can be shared between
+ * kernel-space and user-space. A pool is always backed by a shmem-file and puts
+ * a simple slice-allocator on top. User-space gets read-only access to the
+ * entire pool, kernel-space gets read/write access via accessor-functions.
+ *
+ * Pools are used to transfer large sets of data to user-space, without
+ * requiring a round-trip to ask user-space for a suitable memory chunk.
+ * Instead, the kernel simply allocates slices in the pool and tells user-space
+ * where it put the data.
+ *
+ * All pool operations must be serialized by the caller. No internal lock is
+ * provided. Slices can be queried/modified unlocked. But any pool operation
+ * (allocation, release, flush, ...) must be serialized.
+ */
+struct bus1_pool {
+ struct file *f;
+ size_t allocated_size;
+ struct list_head slices;
+ struct rb_root slices_busy;
+ struct rb_root slices_free;
+};
+
+#define BUS1_POOL_NULL ((struct bus1_pool){})
+
+int bus1_pool_init(struct bus1_pool *pool, const char *filename);
+void bus1_pool_deinit(struct bus1_pool *pool);
+
+struct bus1_pool_slice *bus1_pool_alloc(struct bus1_pool *pool, size_t size);
+struct bus1_pool_slice *bus1_pool_release_kernel(struct bus1_pool *pool,
+ struct bus1_pool_slice *slice);
+void bus1_pool_publish(struct bus1_pool *pool, struct bus1_pool_slice *slice);
+int bus1_pool_release_user(struct bus1_pool *pool,
+ size_t offset,
+ size_t *n_slicesp);
+void bus1_pool_flush(struct bus1_pool *pool, size_t *n_slicesp);
+int bus1_pool_mmap(struct bus1_pool *pool, struct vm_area_struct *vma);
+
+ssize_t bus1_pool_write_iovec(struct bus1_pool *pool,
+ struct bus1_pool_slice *slice,
+ loff_t offset,
+ struct iovec *iov,
+ size_t n_iov,
+ size_t total_len);
+ssize_t bus1_pool_write_kvec(struct bus1_pool *pool,
+ struct bus1_pool_slice *slice,
+ loff_t offset,
+ struct kvec *iov,
+ size_t n_iov,
+ size_t total_len);
+
+/**
+ * bus1_pool_slice_is_public() - check whether a slice is public
+ * @slice: slice to check
+ *
+ * This checks whether @slice is public. That is, bus1_pool_publish() has been
+ * called and the user has not released their reference, yet.
+ *
+ * Note that if you need reliable results, you better make sure this cannot
+ * race calls to bus1_pool_publish() or bus1_pool_release_user().
+ *
+ * Return: True if public, false if not.
+ */
+static inline bool bus1_pool_slice_is_public(struct bus1_pool_slice *slice)
+{
+ WARN_ON(!slice->ref_kernel);
+ return slice->ref_user;
+}
+
+#endif /* __BUS1_POOL_H */
--
2.10.1
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2016-10-27 16:00 +0200 |
| Subject | Re: [RFC v1 05/14] bus1: util - pool utility library |
| Message-ID | <swTnQ-2Bn-75@gated-at.bofh.it> |
| In reply to | #1509720 |
On Wed, Oct 26, 2016 at 09:18:01PM +0200, David Herrmann wrote:
> +/* insert slice into the free tree */
> +static void bus1_pool_slice_link_free(struct bus1_pool_slice *slice,
> + struct bus1_pool *pool)
> +{
> + struct rb_node **n, *prev = NULL;
> + struct bus1_pool_slice *ps;
> +
> + n = &pool->slices_free.rb_node;
> + while (*n) {
> + prev = *n;
> + ps = container_of(prev, struct bus1_pool_slice, rb);
> + if (slice->size < ps->size)
> + n = &prev->rb_left;
> + else
> + n = &prev->rb_right;
> + }
> +
> + rb_link_node(&slice->rb, prev, n);
> + rb_insert_color(&slice->rb, &pool->slices_free);
> +}
If you only sort free slices by size, how do you merge contiguous free
slices?
> +/* find free slice big enough to hold @size bytes */
> +static struct bus1_pool_slice *
> +bus1_pool_slice_find_by_size(struct bus1_pool *pool, size_t size)
> +{
> + struct bus1_pool_slice *ps, *closest = NULL;
> + struct rb_node *n;
> +
> + n = pool->slices_free.rb_node;
> + while (n) {
> + ps = container_of(n, struct bus1_pool_slice, rb);
> + if (size < ps->size) {
> + closest = ps;
> + n = n->rb_left;
> + } else if (size > ps->size) {
> + n = n->rb_right;
> + } else /* if (size == ps->size) */ {
> + return ps;
> + }
> + }
> +
> + return closest;
> +}
> +
> +/* find used slice with given offset */
> +static struct bus1_pool_slice *
> +bus1_pool_slice_find_by_offset(struct bus1_pool *pool, size_t offset)
> +{
> + struct bus1_pool_slice *ps;
> + struct rb_node *n;
> +
> + n = pool->slices_busy.rb_node;
> + while (n) {
> + ps = container_of(n, struct bus1_pool_slice, rb);
> + if (offset < ps->offset)
> + n = n->rb_left;
> + else if (offset > ps->offset)
> + n = n->rb_right;
> + else /* if (offset == ps->offset) */
> + return ps;
> + }
> +
> + return NULL;
> +}
I find these two function names misleading. They don't find_by_size or
find_by_offset. They find_free_by_size and find_busy_by_offset. You
could reduce that to find_free and find_busy and have the 'size' and
'offset' in the argument name.
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2016-10-27 17:10 +0200 |
| Subject | Re: [RFC v1 05/14] bus1: util - pool utility library |
| Message-ID | <swUtA-3yF-15@gated-at.bofh.it> |
| In reply to | #1510166 |
On Thu, Oct 27, 2016 at 02:59:07PM +0200, Peter Zijlstra wrote:
> On Wed, Oct 26, 2016 at 09:18:01PM +0200, David Herrmann wrote:
> > +/* insert slice into the free tree */
> > +static void bus1_pool_slice_link_free(struct bus1_pool_slice *slice,
> > + struct bus1_pool *pool)
> > +{
> > + struct rb_node **n, *prev = NULL;
> > + struct bus1_pool_slice *ps;
> > +
> > + n = &pool->slices_free.rb_node;
> > + while (*n) {
> > + prev = *n;
> > + ps = container_of(prev, struct bus1_pool_slice, rb);
> > + if (slice->size < ps->size)
> > + n = &prev->rb_left;
> > + else
> > + n = &prev->rb_right;
> > + }
> > +
> > + rb_link_node(&slice->rb, prev, n);
> > + rb_insert_color(&slice->rb, &pool->slices_free);
> > +}
>
> If you only sort free slices by size, how do you merge contiguous free
> slices?
Ah, I see, you also keep an ordered list of slices and use that one
function up from here.
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2016-10-27 16:00 +0200 |
| Subject | Re: [RFC v1 05/14] bus1: util - pool utility library |
| Message-ID | <swTnS-2Bn-131@gated-at.bofh.it> |
| In reply to | #1509720 |
On Wed, Oct 26, 2016 at 09:18:01PM +0200, David Herrmann wrote:
> +static struct bus1_pool_slice *
> +bus1_pool_slice_free(struct bus1_pool_slice *slice)
> +{
> + if (!slice)
> + return NULL;
> +
> + kfree(slice);
> +
> + return NULL;
> +}
The return value is never used. Which reduces the entire thing to:
kfree(slice);
since kfree() already accepts a NULL.
> + bus1_pool_slice_free(slice);
> + bus1_pool_slice_free(slice);
> + bus1_pool_slice_free(ps);
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2016-10-27 17:20 +0200 |
| Subject | Re: [RFC v1 05/14] bus1: util - pool utility library |
| Message-ID | <swUDf-3BS-1@gated-at.bofh.it> |
| In reply to | #1509720 |
On Wed, Oct 26, 2016 at 09:18:01PM +0200, David Herrmann wrote:
All small nits..
> +void bus1_pool_deinit(struct bus1_pool *pool)
> +{
> + struct bus1_pool_slice *slice;
> +
> + if (!pool || !pool->f)
> + return;
> +
> + while ((slice = list_first_entry_or_null(&pool->slices,
> + struct bus1_pool_slice,
> + entry))) {
> + WARN_ON(slice->ref_kernel);
> + list_del(&slice->entry);
> + bus1_pool_slice_free(slice);
> + }
I prefer to write that loop like:
while (!list_empty(&pool->slices)) {
slice = list_first_entry(&pool->slices, struct bus1_pool_slice, entry);
list_del(&slice->entry);
// ...
}
> +static void bus1_pool_free(struct bus1_pool *pool,
> + struct bus1_pool_slice *slice)
> +{
> + struct bus1_pool_slice *ps;
> +
> + /* don't free the slice if either has a reference */
> + if (slice->ref_kernel || slice->ref_user || WARN_ON(slice->free))
> + return;
> +
> + /*
> + * To release a pool-slice, we first drop it from the busy-tree, then
> + * merge it with possible previous/following free slices and re-add it
> + * to the free-tree.
> + */
> +
> + rb_erase(&slice->rb, &pool->slices_busy);
> +
> + if (!WARN_ON(slice->size > pool->allocated_size))
> + pool->allocated_size -= slice->size;
> +
> + if (pool->slices.next != &slice->entry) {
> + ps = container_of(slice->entry.prev, struct bus1_pool_slice,
> + entry);
ps = list_prev_entry(slice, entry);
> + if (ps->free) {
> + rb_erase(&ps->rb, &pool->slices_free);
> + list_del(&slice->entry);
> + ps->size += slice->size;
> + bus1_pool_slice_free(slice);
> + slice = ps; /* switch to previous slice */
> + }
> + }
> +
> + if (pool->slices.prev != &slice->entry) {
> + ps = container_of(slice->entry.next, struct bus1_pool_slice,
> + entry);
ps = list_next_entry(slice, entry);
> + if (ps->free) {
> + rb_erase(&ps->rb, &pool->slices_free);
> + list_del(&ps->entry);
> + slice->size += ps->size;
> + bus1_pool_slice_free(ps);
> + }
> + }
> +
> + slice->free = true;
> + bus1_pool_slice_link_free(slice, pool);
> +}
[toc] | [prev] | [next] | [standalone]
| From | David Herrmann <dh.herrmann@gmail.com> |
|---|---|
| Date | 2016-10-26 21:30 +0200 |
| Subject | [RFC v1 04/14] bus1: util - fixed list utility library |
| Message-ID | <swC3D-87o-27@gated-at.bofh.it> |
| In reply to | #1509715 |
From: Tom Gundersen <teg@jklm.no>
This implements a fixed-size list called bus1_flist. The size of
the list must be constant over the lifetime of the list. The list
can hold one arbitrary pointer per node.
Fixed lists are a combination of a linked list and a static array.
That is, fixed lists behave like linked lists (no random access, but
arbitrary size), but compare in speed with arrays (consequetive
accesses are fast). Unlike fixed arrays, fixed lists can hold huge
number of elements without requiring vmalloc, but solely relying on
small-size kmalloc allocations.
Internally, fixed lists are a singly-linked list of static arrays.
This guarantees that iterations behave almost like on an array,
except when crossing a batch-border.
Fixed lists can replace fixed-size arrays whenever you need to support
large number of elements, but don't need random access. Fixed lists
have ALMOST the same memory requirements as fixed-size arrays, except
one pointer of state per 'BUS1_FLIST_BATCH' elements. If only a small
size (i.e., it only requires one batch) is stored in a fixed list,
then its memory requirements and iteration time are equivalent to
fixed-size arrays.
Fixed lists will be required by the upcoming bus1 message-transactions.
They must support large auxiliary data transfers, in case users want to
send their entire handle state via the bus.
Signed-off-by: Tom Gundersen <teg@jklm.no>
Signed-off-by: David Herrmann <dh.herrmann@gmail.com>
---
ipc/bus1/Makefile | 3 +-
ipc/bus1/util/flist.c | 116 +++++++++++++++++++++++++++++
ipc/bus1/util/flist.h | 202 ++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 320 insertions(+), 1 deletion(-)
create mode 100644 ipc/bus1/util/flist.c
create mode 100644 ipc/bus1/util/flist.h
diff --git a/ipc/bus1/Makefile b/ipc/bus1/Makefile
index 9e491691..6db6d13 100644
--- a/ipc/bus1/Makefile
+++ b/ipc/bus1/Makefile
@@ -1,6 +1,7 @@
bus1-y := \
main.o \
- util/active.o
+ util/active.o \
+ util/flist.o
obj-$(CONFIG_BUS1) += bus1.o
diff --git a/ipc/bus1/util/flist.c b/ipc/bus1/util/flist.c
new file mode 100644
index 0000000..b8b0d4e
--- /dev/null
+++ b/ipc/bus1/util/flist.c
@@ -0,0 +1,116 @@
+/*
+ * Copyright (C) 2013-2016 Red Hat, Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by the
+ * Free Software Foundation; either version 2.1 of the License, or (at
+ * your option) any later version.
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+#include <linux/err.h>
+#include <linux/kernel.h>
+#include <linux/slab.h>
+#include "flist.h"
+
+/**
+ * bus1_flist_populate() - populate an flist
+ * @list: flist to operate on
+ * @n: number of elements
+ * @gfp: GFP to use for allocations
+ *
+ * Populate an flist. This pre-allocates the backing memory for an flist that
+ * was statically initialized via bus1_flist_init(). This is NOT needed if the
+ * list was allocated via bus1_flist_new().
+ *
+ * Return: 0 on success, negative error code on failure.
+ */
+int bus1_flist_populate(struct bus1_flist *list, size_t n, gfp_t gfp)
+{
+ if (gfp & __GFP_ZERO)
+ memset(list, 0, bus1_flist_inline_size(n));
+
+ if (unlikely(n > BUS1_FLIST_BATCH)) {
+ /* Never populate twice! */
+ WARN_ON(list[BUS1_FLIST_BATCH].next);
+
+ n -= BUS1_FLIST_BATCH;
+ list[BUS1_FLIST_BATCH].next = bus1_flist_new(n, gfp);
+ if (!list[BUS1_FLIST_BATCH].next)
+ return -ENOMEM;
+ }
+
+ return 0;
+}
+
+/**
+ * bus1_flist_new() - allocate new flist
+ * @n: number of elements
+ * @gfp: GFP to use for allocations
+ *
+ * This allocates a new flist ready to store @n elements.
+ *
+ * Return: Pointer to flist, NULL if out-of-memory.
+ */
+struct bus1_flist *bus1_flist_new(size_t n, gfp_t gfp)
+{
+ struct bus1_flist list, *e, *slot;
+ size_t remaining;
+
+ list.next = NULL;
+ slot = &list;
+ remaining = n;
+
+ while (remaining >= BUS1_FLIST_BATCH) {
+ e = kmalloc_array(sizeof(*e), BUS1_FLIST_BATCH + 1, gfp);
+ if (!e)
+ return bus1_flist_free(list.next, n);
+
+ slot->next = e;
+ slot = &e[BUS1_FLIST_BATCH];
+ slot->next = NULL;
+
+ remaining -= BUS1_FLIST_BATCH;
+ }
+
+ if (remaining > 0) {
+ slot->next = kmalloc_array(remaining, sizeof(*e), gfp);
+ if (!slot->next)
+ return bus1_flist_free(list.next, n);
+ }
+
+ return list.next;
+}
+
+/**
+ * bus1_flist_free() - free flist
+ * @list: flist to operate on, or NULL
+ * @n: number of elements
+ *
+ * This deallocates an flist previously created via bus1_flist_new().
+ *
+ * If NULL is passed, this is a no-op.
+ *
+ * Return: NULL is returned.
+ */
+struct bus1_flist *bus1_flist_free(struct bus1_flist *list, size_t n)
+{
+ struct bus1_flist *e;
+
+ if (list) {
+ /*
+ * If @list was only partially allocated, then "next" pointers
+ * might be NULL. So check @list on each iteration.
+ */
+ while (list && n >= BUS1_FLIST_BATCH) {
+ e = list;
+ list = list[BUS1_FLIST_BATCH].next;
+ kfree(e);
+ n -= BUS1_FLIST_BATCH;
+ }
+
+ kfree(list);
+ }
+
+ return NULL;
+}
diff --git a/ipc/bus1/util/flist.h b/ipc/bus1/util/flist.h
new file mode 100644
index 0000000..e265d5c
--- /dev/null
+++ b/ipc/bus1/util/flist.h
@@ -0,0 +1,202 @@
+#ifndef __BUS1_FLIST_H
+#define __BUS1_FLIST_H
+
+/*
+ * Copyright (C) 2013-2016 Red Hat, Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by the
+ * Free Software Foundation; either version 2.1 of the License, or (at
+ * your option) any later version.
+ */
+
+/**
+ * DOC: Fixed Lists
+ *
+ * This implements a fixed-size list called bus1_flist. The size of the list
+ * must be constant over the lifetime of the list. The list can hold one
+ * arbitrary pointer per node.
+ *
+ * Fixed lists are a combination of a linked list and a static array. That is,
+ * fixed lists behave like linked lists (no random access, but arbitrary size),
+ * but compare in speed with arrays (consequetive accesses are fast). Unlike
+ * fixed arrays, fixed lists can hold huge number of elements without requiring
+ * vmalloc(), but solely relying on small-size kmalloc() allocations.
+ *
+ * Internally, fixed lists are a singly-linked list of static arrays. This
+ * guarantees that iterations behave almost like on an array, except when
+ * crossing a batch-border.
+ *
+ * Fixed lists can replace fixed-size arrays whenever you need to support large
+ * number of elements, but don't need random access. Fixed lists have ALMOST
+ * the same memory requirements as fixed-size arrays, except one pointer of
+ * state per 'BUS1_FLIST_BATCH' elements. If only a small size (i.e., it only
+ * requires one batch) is stored in a fixed list, then its memory requirements
+ * and iteration time are equivalent to fixed-size arrays.
+ */
+
+#include <linux/kernel.h>
+
+#define BUS1_FLIST_BATCH (1024)
+
+/**
+ * struct bus1_flist - fixed list
+ * @next: pointer to next batch
+ * @ptr: stored entry
+ */
+struct bus1_flist {
+ union {
+ struct bus1_flist *next;
+ void *ptr;
+ };
+};
+
+int bus1_flist_populate(struct bus1_flist *flist, size_t n, gfp_t gfp);
+struct bus1_flist *bus1_flist_new(size_t n, gfp_t gfp);
+struct bus1_flist *bus1_flist_free(struct bus1_flist *list, size_t n);
+
+/**
+ * bus1_flist_inline_size() - calculate required inline size
+ * @n: number of entries
+ *
+ * When allocating storage for an flist, this calculates the size of the
+ * initial array in bytes. Use bus1_flist_new() directly if you want to
+ * allocate an flist on the heap. This helper is only needed if you embed an
+ * flist into another struct like this:
+ *
+ * struct foo {
+ * ...
+ * struct bus1_flist list[];
+ * };
+ *
+ * In that case the flist must be the last element, and the size in bytes
+ * required by it is returned by this function.
+ *
+ * The inline-size of an flist is always bound to a fixed maximum. That is,
+ * regardless of @n, this will always return a reasonable number that can be
+ * allocated via kmalloc().
+ *
+ * Return: Size in bytes required for the initial batch of an flist.
+ */
+static inline size_t bus1_flist_inline_size(size_t n)
+{
+ return sizeof(struct bus1_flist) *
+ ((likely(n < BUS1_FLIST_BATCH)) ? n : (BUS1_FLIST_BATCH + 1));
+}
+
+/**
+ * bus1_flist_init() - initialize an flist
+ * @list: flist to initialize
+ * @n: number of entries
+ *
+ * This initializes an flist of size @n. It does NOT preallocate the memory,
+ * but only initializes @list in a way that bus1_flist_deinit() can be called
+ * on it. Use bus1_flist_populate() to populate the flist.
+ *
+ * This is only needed if your backing memory of @list is shared with another
+ * object. If possible, use bus1_flist_new() to allocate an flist on the heap
+ * and avoid this dance.
+ */
+static inline void bus1_flist_init(struct bus1_flist *list, size_t n)
+{
+ BUILD_BUG_ON(sizeof(struct bus1_flist) != sizeof(void *));
+
+ if (unlikely(n >= BUS1_FLIST_BATCH))
+ list[BUS1_FLIST_BATCH].next = NULL;
+}
+
+/**
+ * bus1_flist_deinit() - deinitialize an flist
+ * @list: flist to deinitialize
+ * @n: number of entries
+ *
+ * This deallocates an flist and releases all resources. If already
+ * deinitialized, this is a no-op. This is only needed if you called
+ * bus1_flist_populate().
+ */
+static inline void bus1_flist_deinit(struct bus1_flist *list, size_t n)
+{
+ if (unlikely(n >= BUS1_FLIST_BATCH)) {
+ bus1_flist_free(list[BUS1_FLIST_BATCH].next,
+ n - BUS1_FLIST_BATCH);
+ list[BUS1_FLIST_BATCH].next = NULL;
+ }
+}
+
+/**
+ * bus1_flist_next() - flist iterator
+ * @iter: iterator
+ * @pos: current position
+ *
+ * This advances an flist iterator by one position. @iter must point to the
+ * current position, and the new position is returned by this function. @pos
+ * must point to a variable that contains the current index position. That is,
+ * @pos must be initialized to 0 and @iter to the flist head.
+ *
+ * Neither @pos nor @iter must be modified by anyone but this helper. In the
+ * loop body you can use @iter->ptr to access the current element.
+ *
+ * This iterator is normally used like this:
+ *
+ * size_t pos, n = 128;
+ * struct bus1_flist *e, *list = bus1_flist_new(n);
+ *
+ * ...
+ *
+ * for (pos = 0, e = list; pos < n; e = bus1_flist_next(e, &pos)) {
+ * ... access e->ptr ...
+ * }
+ *
+ * Return: Next iterator position.
+ */
+static inline struct bus1_flist *bus1_flist_next(struct bus1_flist *iter,
+ size_t *pos)
+{
+ return (++*pos % BUS1_FLIST_BATCH) ? (iter + 1) : (iter + 1)->next;
+}
+
+/**
+ * bus1_flist_walk() - walk flist in batches
+ * @list: list to walk
+ * @n: number of entries
+ * @iter: iterator
+ * @pos: current position
+ *
+ * This walks an flist in batches of size up to BUS1_FLIST_BATCH. It is
+ * normally used like this:
+ *
+ * size_t pos, z, n = 65536;
+ * struct bus1_flist *e, *list = bus1_flist_new(n);
+ *
+ * ...
+ *
+ * pos = 0;
+ * while ((z = bus1_flist_walk(list, n, &e, &pos)) > 0) {
+ * ... access e[0...z]->ptr
+ * ... invariant: z <= BUS1_FLIST_BATCH
+ * ... invariant: e[i]->ptr == (&e->ptr)[i]
+ * }
+ *
+ * Return: Size of batch at @iter.
+ */
+static inline size_t bus1_flist_walk(struct bus1_flist *list,
+ size_t n,
+ struct bus1_flist **iter,
+ size_t *pos)
+{
+ if (*pos < n) {
+ n = n - *pos;
+ if (unlikely(n > BUS1_FLIST_BATCH))
+ n = BUS1_FLIST_BATCH;
+ if (likely(*pos == 0))
+ *iter = list;
+ else
+ *iter = (*iter)[BUS1_FLIST_BATCH].next;
+ *pos += n;
+ } else {
+ n = 0;
+ }
+ return n;
+}
+
+#endif /* __BUS1_FLIST_H */
--
2.10.1
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2016-10-27 16:30 +0200 |
| Subject | Re: [RFC v1 04/14] bus1: util - fixed list utility library |
| Message-ID | <swTnP-2Bn-13@gated-at.bofh.it> |
| In reply to | #1509721 |
On Wed, Oct 26, 2016 at 09:18:00PM +0200, David Herrmann wrote:
> + e = kmalloc_array(sizeof(*e), BUS1_FLIST_BATCH + 1, gfp);
> +#define BUS1_FLIST_BATCH (1024)
> +struct bus1_flist {
> + union {
> + struct bus1_flist *next;
> + void *ptr;
> + };
> +};
So that's an allocation of 8*(1024+1), or slightly more than 2 pages.
kmalloc will round up to the next power of two, so you'll end up with an
allocation of 16*1024, wasting a whopping 8184 bytes per such allocation
in slack space.
Please consider using 1023 or something for your batch size, 511 would
get you to exactly 1 page which would be even better.
[toc] | [prev] | [next] | [standalone]
Page 1 of 3 [1] 2 3 Next page →
Back to top | Article view | linux.kernel
csiph-web