940b37ee80aa3168a5fcb57b6427f48623d6b7d1
[akaros.git] / kern / include / ros / ucq.h
1 /* Copyright (c) 2011 The Regents of the University of California
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details.
4  *
5  * Unbounded concurrent queues.  Linked buffers/arrays of elements, in page
6  * size chunks.  The pages/buffers are linked together by an info struct at the
7  * beginning of the page.  Producers and consumers sync on the idxes when
8  * operating in a page, and page swaps are synced via the proc* for the kernel
9  * and via the ucq's u_lock for the user. 
10  *
11  * There's a bunch of details and issues discussed in the Documentation.
12  *
13  * This header contains the stuff that the kernel and userspace need to agree
14  * on.  Each side of the implementation will have their own .c and .h files.
15  * The kernel's implementation is in kern/src/ucq.c, and the user's is in
16  * user/parlib/ucq.c. */
17
18 #ifndef ROS_INC_UCQ_H
19 #define ROS_INC_UCQ_H
20
21 #include <ros/common.h>
22 #include <ros/atomic.h>
23 #include <ros/arch/mmu.h>
24
25 #ifdef ROS_KERNEL
26 #include <arch/arch.h>
27 #else
28 #include <parlib/arch/arch.h>
29 #endif
30
31 /* #include <ros/event.h> included below */
32
33 /* The main UCQ structure, contains indexes and start points (for the indexes),
34  * etc. */
35 struct ucq {
36         atomic_t                                        prod_idx;               /* both pg and slot nr */
37         bool                                            prod_overflow;  /* flag to prevent wraparound */
38         atomic_t                                        spare_pg;               /* mmaped, unused page */
39         atomic_t                                        nr_extra_pgs;   /* nr pages mmaped */
40         atomic_t                                        cons_idx;               /* cons pg and slot nr */
41         bool                                            ucq_ready;              /* ucq is ready to be used */
42         /* Userspace lock for modifying the UCQ */
43         uint64_t                                        u_lock[2 * ARCH_CL_SIZE / 8];
44 };
45
46 /* Struct at the beginning of every page/buffer, tracking consumers and
47  * pointing to the next one, so that the consumer can follow. */
48 struct ucq_page_header {
49         uintptr_t                                       cons_next_pg;   /* next page to consume */
50         atomic_t                                        nr_cons;                /* like an inverted refcnt */
51 };
52
53 /* Including here since event.h needs to know about struct ucq */
54 #include <ros/event.h>
55
56 struct msg_container {
57         struct event_msg                        ev_msg;
58         bool                                            ready;                  /* kernel has written */
59 };
60
61 struct ucq_page {
62         struct ucq_page_header          header;
63         struct msg_container            msgs[];
64 };
65
66 #define UCQ_WARN_THRESH                 1000                    /* nr pages befor warning */
67
68 #define NR_MSG_PER_PAGE ((PGSIZE - ROUNDUP(sizeof(struct ucq_page_header),     \
69                                            __alignof__(struct msg_container))) \
70                          / sizeof(struct msg_container))
71
72 /* A slot encodes both the page addr and the count within the page */
73 static bool slot_is_good(uintptr_t slot)
74 {
75         uintptr_t counter = PGOFF(slot);
76         uintptr_t pg_addr = PTE_ADDR(slot);
77         return ((counter < NR_MSG_PER_PAGE) && pg_addr) ? TRUE : FALSE;
78 }
79
80 /* Helper: converts a slot/index into a msg container.  The ucq_page is the
81  * PPN/PTE_ADDR of 'slot', and the specific slot *number* is the PGOFF.  Assumes
82  * the slot is good.  If it isn't, you're going to get random memory.
83  *
84  * Note that this doesn't actually read the memory, just computes an address. */
85 static inline struct msg_container *slot2msg(uintptr_t slot)
86 {
87         return &((struct ucq_page*)PTE_ADDR(slot))->msgs[PGOFF(slot)];
88 }
89
90 #endif /* ROS_INC_UCQ_H */