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 #pragma once
  19
  20 #include <ros/bits/event.h>
  21 #include <ros/atomic.h>
  22 #include <ros/arch/mmu.h>
  23
  24 #ifdef ROS_KERNEL
  25 #include <arch/arch.h>
  26 #else
  27 #include <parlib/arch/arch.h>
  28 #endif
  29
  30 /* #include <ros/event.h> included below */
  31
  32 /* The main UCQ structure, contains indexes and start points (for the indexes),
  33  * etc. */
  34 struct ucq {
  35         atomic_t                        prod_idx;     /* both pg and slot nr */
  36         atomic_t                        spare_pg;     /* mmaped, unused page */
  37         atomic_t                        nr_extra_pgs; /* nr pages mmaped */
  38         atomic_t                        cons_idx;     /* cons pg and slot nr */
  39         bool                            prod_overflow;/* prevent wraparound */
  40         bool                            ucq_ready;
  41         /* Userspace lock for modifying the UCQ */
  42         uint32_t                        u_lock[2];
  43 };
  44
  45 /* Struct at the beginning of every page/buffer, tracking consumers and
  46  * pointing to the next one, so that the consumer can follow. */
  47 struct ucq_page_header {
  48         uintptr_t                       cons_next_pg; /* next page to consume */
  49         atomic_t                        nr_cons; /* like an inverted refcnt */
  50 };
  51
  52 struct msg_container {
  53         struct event_msg                ev_msg;
  54         bool                            ready;
  55 };
  56
  57 struct ucq_page {
  58         struct ucq_page_header          header;
  59         struct msg_container            msgs[];
  60 };
  61
  62 #define UCQ_WARN_THRESH         1000            /* nr pages befor warning */
  63
  64 #define NR_MSG_PER_PAGE ((PGSIZE - ROUNDUP(sizeof(struct ucq_page_header),     \
  65                                            __alignof__(struct msg_container))) \
  66                          / sizeof(struct msg_container))
  67
  68 /* A slot encodes both the page addr and the count within the page */
  69 static bool slot_is_good(uintptr_t slot)
  70 {
  71         uintptr_t counter = PGOFF(slot);
  72         uintptr_t pg_addr = PTE_ADDR(slot);
  73
  74         return ((counter < NR_MSG_PER_PAGE) && pg_addr) ? TRUE : FALSE;
  75 }
  76
  77 /* Helper: converts a slot/index into a msg container.  The ucq_page is the
  78  * PPN/PTE_ADDR of 'slot', and the specific slot *number* is the PGOFF.  Assumes
  79  * the slot is good.  If it isn't, you're going to get random memory.
  80  *
  81  * Note that this doesn't actually read the memory, just computes an address. */
  82 static inline struct msg_container *slot2msg(uintptr_t slot)
  83 {
  84         return &((struct ucq_page*)PTE_ADDR(slot))->msgs[PGOFF(slot)];
  85 }