Add the CEQ mbox: Coalescing Event Queues (XCC)
[akaros.git] / kern / include / ros / ceq.h
1 /* Copyright (c) 2015 Google Inc.
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details.
4  *
5  * Coalescing Event Queue: encapuslates the essence of epoll/kqueue in shared
6  * memory: a dense array of sticky status bits.
7  *
8  * Like all event mailboxes, CEQs are multi-producer, multi-consumer, with the
9  * producer not trusting the consumer.
10  *
11  * The producer sends ceq_events with a certain ID (the ev_type).  Events of a
12  * particular ID are coalesced in one spot, such that N events can occur and the
13  * consumer only receives them as one event.  These are the "sticky status
14  * bits".  For example, setting flags in an int coalesce (you can set the same
15  * flag repeatedly, and it's still set), and an atomic counter coalesces small
16  * increments into a larger value.  The nature of the operation (atomic_or,
17  * atomic_add) depends on a field in the CEQ.  There is also a data blob field,
18  * last-write-wins.  There aren't a lot of guarantees associated with it, but
19  * it's still useful for some apps.
20  *
21  * Internally, a CEQ maintains an array of ceq_event structs for every possible
22  * ID, so the maximum ID should be known at ceq creation time.  These structs
23  * coalesce the events.  To keep the consumer from needing to scan the array for
24  * activity, there is a separate ring buffer that contains the indices of
25  * ceq_events with activity.  This is the "dense array."
26  *
27  * The ring buffer is actually an optimization.  If anything goes wrong, we can
28  * tell the consumer to scan the entire array.  Likewise, spurious entries in
29  * the ring are safe; the consumer just does an extra check.
30  *
31  * In general, every time we have an event, we make sure there's a pointer in
32  * the ring.  That's the purposed of 'idx_posted' - whether or not we think our
33  * index is posted in the ring. */
34
35 #ifndef ROS_INC_CEQ_H
36 #define ROS_INC_CEQ_H
37
38 #include <ros/atomic.h>
39 #include <ros/ring_buffer.h>
40
41 #define CEQ_OR                                  1
42 #define CEQ_ADD                                 2
43
44 struct ceq_event {
45         atomic_t                                        coalesce;               /* ev_arg2 */
46         uint64_t                                        blob_data;              /* ev_arg3 */
47         bool                                            idx_posted;             /* for syncing with consumer */
48         uint64_t                                        user_data;              /* for apps, ignored by CEQ */
49 };
50
51 /* The events array and the ring buffer are provided by the consumer.
52  *
53  * Ring values are -1 for "unconsumed" and an index into *events otherwise.
54  *
55  * Similar to BCQs, the ring buffer must be a power of two and is managed with
56  * three index variables:
57  *
58  * prod_idx:     the next slot to be produced
59  * cons_pvt_idx: the next slot a consumer can claim
60  * cons_pub_idx: the last slot (farthest left / oldest) that hasn't been
61  *               consumed/made ready to be produced by the producer (it is
62  *               what the consumer produces).
63  *
64  * The ring is has no new entries that need consumed when prod == pvt.   The
65  * number of entries filled is prod - pub.  The number of available entries
66  * (nr_empty) is the size - (prod - pub). */
67
68 struct ceq {
69         struct ceq_event                        *events;                /* consumer pointer */
70         size_t                                          nr_events;
71         int32_t                                         *ring;                  /* consumer pointer */
72         uint32_t                                        ring_sz;                /* size (power of 2) */
73         uint8_t                                         operation;              /* e.g. CEQ_OR */
74         bool                                            ring_overflowed;
75         atomic_t                                        prod_idx;               /* next prod slot to fill */
76         atomic_t                                        cons_pub_idx;   /* how far has been consumed */
77         atomic_t                                        cons_pvt_idx;   /* next cons slot to get */
78         uint32_t                                        u_lock[2];              /* user space lock */
79 };
80
81 #endif /* ROS_INC_CEQ_H */