<p>Hoernchen has uploaded this change for <strong>review</strong>.</p><p><a href="https://gerrit.osmocom.org/c/osmo-mgw/+/25431">View Change</a></p><pre style="font-family: monospace,monospace; white-space: pre-wrap;">add a lock-free bounded spsc interthread queue<br><br>Not entirely wait-free: allows waiting on a fd, and in general fd<br>notifications for poll-loop integration between threads.<br><br>Change-Id: I4f17042baf76d086ce6b20eb99402dc64c22c657<br>---<br>A include/osmocom/mgcp/mgcp_threads_queue.h<br>A src/libosmo-mgcp/mgcp_threads_queue.c<br>2 files changed, 224 insertions(+), 0 deletions(-)<br><br></pre><pre style="font-family: monospace,monospace; white-space: pre-wrap;">git pull ssh://gerrit.osmocom.org:29418/osmo-mgw refs/changes/31/25431/1</pre><pre style="font-family: monospace,monospace; white-space: pre-wrap;"><span>diff --git a/include/osmocom/mgcp/mgcp_threads_queue.h b/include/osmocom/mgcp/mgcp_threads_queue.h</span><br><span>new file mode 100644</span><br><span>index 0000000..41f02e8</span><br><span>--- /dev/null</span><br><span>+++ b/include/osmocom/mgcp/mgcp_threads_queue.h</span><br><span>@@ -0,0 +1,52 @@</span><br><span style="color: hsl(120, 100%, 40%);">+/*</span><br><span style="color: hsl(120, 100%, 40%);">+ * (C) 2021 by sysmocom s.f.m.c. GmbH <info@sysmocom.de></span><br><span style="color: hsl(120, 100%, 40%);">+ * All Rights Reserved</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * Author: Eric Wild</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * This program is free software; you can redistribute it and/or modify</span><br><span style="color: hsl(120, 100%, 40%);">+ * it under the terms of the GNU Affero General Public License as published by</span><br><span style="color: hsl(120, 100%, 40%);">+ * the Free Software Foundation; either version 3 of the License, or</span><br><span style="color: hsl(120, 100%, 40%);">+ * (at your option) any later version.</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * This program is distributed in the hope that it will be useful,</span><br><span style="color: hsl(120, 100%, 40%);">+ * but WITHOUT ANY WARRANTY; without even the implied warranty of</span><br><span style="color: hsl(120, 100%, 40%);">+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the</span><br><span style="color: hsl(120, 100%, 40%);">+ * GNU Affero General Public License for more details.</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * You should have received a copy of the GNU Affero General Public License</span><br><span style="color: hsl(120, 100%, 40%);">+ * along with this program. If not, see <http://www.gnu.org/licenses/>.</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#include <stdatomic.h></span><br><span style="color: hsl(120, 100%, 40%);">+#include <stdbool.h></span><br><span style="color: hsl(120, 100%, 40%);">+#include <stdlib.h></span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+struct spsc {</span><br><span style="color: hsl(120, 100%, 40%);">+ atomic_uint readptr;</span><br><span style="color: hsl(120, 100%, 40%);">+ atomic_uint writeptr;</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ int efd_r, efd_w;</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ int count;</span><br><span style="color: hsl(120, 100%, 40%);">+ int size_per_buf;</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ void *buf;</span><br><span style="color: hsl(120, 100%, 40%);">+ uintptr_t data[0];</span><br><span style="color: hsl(120, 100%, 40%);">+};</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+struct qchan {</span><br><span style="color: hsl(120, 100%, 40%);">+ struct spsc *a;</span><br><span style="color: hsl(120, 100%, 40%);">+ struct spsc *b;</span><br><span style="color: hsl(120, 100%, 40%);">+};</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+bool spsc_push(struct spsc *q, void *elem);</span><br><span style="color: hsl(120, 100%, 40%);">+bool spsc_pop(struct spsc *q, void *elem);</span><br><span style="color: hsl(120, 100%, 40%);">+ssize_t prep_pop(struct spsc *q);</span><br><span style="color: hsl(120, 100%, 40%);">+int get_a_rdfd(struct qchan *q);</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+struct qchan chan_init(unsigned int count, unsigned size_per_buf);</span><br><span style="color: hsl(120, 100%, 40%);">+struct qchan chan_init_ex(unsigned int count, unsigned size_per_buf, bool blockr_a, bool blockw_a, bool blockr_b,</span><br><span style="color: hsl(120, 100%, 40%);">+ bool blockw_b);</span><br><span style="color: hsl(120, 100%, 40%);">+void chan_close(struct qchan *q);</span><br><span>diff --git a/src/libosmo-mgcp/mgcp_threads_queue.c b/src/libosmo-mgcp/mgcp_threads_queue.c</span><br><span>new file mode 100644</span><br><span>index 0000000..c67bcb3</span><br><span>--- /dev/null</span><br><span>+++ b/src/libosmo-mgcp/mgcp_threads_queue.c</span><br><span>@@ -0,0 +1,172 @@</span><br><span style="color: hsl(120, 100%, 40%);">+/*</span><br><span style="color: hsl(120, 100%, 40%);">+ * (C) 2021 by sysmocom s.f.m.c. GmbH <info@sysmocom.de></span><br><span style="color: hsl(120, 100%, 40%);">+ * All Rights Reserved</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * Author: Eric Wild</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * This program is free software; you can redistribute it and/or modify</span><br><span style="color: hsl(120, 100%, 40%);">+ * it under the terms of the GNU Affero General Public License as published by</span><br><span style="color: hsl(120, 100%, 40%);">+ * the Free Software Foundation; either version 3 of the License, or</span><br><span style="color: hsl(120, 100%, 40%);">+ * (at your option) any later version.</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * This program is distributed in the hope that it will be useful,</span><br><span style="color: hsl(120, 100%, 40%);">+ * but WITHOUT ANY WARRANTY; without even the implied warranty of</span><br><span style="color: hsl(120, 100%, 40%);">+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the</span><br><span style="color: hsl(120, 100%, 40%);">+ * GNU Affero General Public License for more details.</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * You should have received a copy of the GNU Affero General Public License</span><br><span style="color: hsl(120, 100%, 40%);">+ * along with this program. If not, see <http://www.gnu.org/licenses/>.</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#include <inttypes.h></span><br><span style="color: hsl(120, 100%, 40%);">+#include <stdatomic.h></span><br><span style="color: hsl(120, 100%, 40%);">+#include <stdbool.h></span><br><span style="color: hsl(120, 100%, 40%);">+#include <stdint.h></span><br><span style="color: hsl(120, 100%, 40%);">+#include <stdlib.h></span><br><span style="color: hsl(120, 100%, 40%);">+#include <string.h></span><br><span style="color: hsl(120, 100%, 40%);">+#include <sys/eventfd.h></span><br><span style="color: hsl(120, 100%, 40%);">+#include <sys/types.h></span><br><span style="color: hsl(120, 100%, 40%);">+#include <unistd.h></span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#include <osmocom/mgcp/mgcp_threads_queue.h></span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*</span><br><span style="color: hsl(120, 100%, 40%);">+classic lamport circular lockfree spsc queue:</span><br><span style="color: hsl(120, 100%, 40%);">+every "side" only writes its own ptr, but may read the other sides ptr</span><br><span style="color: hsl(120, 100%, 40%);">+-> own ptr relaxed, other one not so much...</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+notify reader using eventfd as soon as element is added, reader then reads until</span><br><span style="color: hsl(120, 100%, 40%);">+read fails</span><br><span style="color: hsl(120, 100%, 40%);">+-> reader pops in a loop until FALSE and might get spurious events because it</span><br><span style="color: hsl(120, 100%, 40%);">+read before it was notified, which is fine</span><br><span style="color: hsl(120, 100%, 40%);">+-> writing pushes *the same data* in a loop until TRUE, blocks</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+shutting this down requires</span><br><span style="color: hsl(120, 100%, 40%);">+1) to stop reading and pushing</span><br><span style="color: hsl(120, 100%, 40%);">+2) ONE side to take care of the eventfds</span><br><span style="color: hsl(120, 100%, 40%);">+*/</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+static struct spsc *spsc_init(unsigned int count, unsigned int size_per_buf, bool blockr, bool blockw)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ struct spsc *q = calloc(1, sizeof(struct spsc) + sizeof(uintptr_t) * count);</span><br><span style="color: hsl(120, 100%, 40%);">+ atomic_init(&q->readptr, 0);</span><br><span style="color: hsl(120, 100%, 40%);">+ atomic_init(&q->writeptr, 0);</span><br><span style="color: hsl(120, 100%, 40%);">+ q->efd_r = eventfd(0, blockr ? 0 : EFD_NONBLOCK);</span><br><span style="color: hsl(120, 100%, 40%);">+ q->efd_w = eventfd(1, blockw ? 0 : EFD_NONBLOCK);</span><br><span style="color: hsl(120, 100%, 40%);">+ q->count = count;</span><br><span style="color: hsl(120, 100%, 40%);">+ q->size_per_buf = size_per_buf;</span><br><span style="color: hsl(120, 100%, 40%);">+ q->buf = calloc(count, size_per_buf);</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ for (int i = 0; i < count; i++)</span><br><span style="color: hsl(120, 100%, 40%);">+ q->data[i] = (uintptr_t)q->buf + i * size_per_buf;</span><br><span style="color: hsl(120, 100%, 40%);">+ return q;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+static void spsc_deinit(struct spsc *q)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ free(q->buf);</span><br><span style="color: hsl(120, 100%, 40%);">+ close(q->efd_r);</span><br><span style="color: hsl(120, 100%, 40%);">+ close(q->efd_w);</span><br><span style="color: hsl(120, 100%, 40%);">+ free(q);</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+static ssize_t spsc_check_r(struct spsc *q)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ uint64_t efdr;</span><br><span style="color: hsl(120, 100%, 40%);">+ return read(q->efd_r, &efdr, sizeof(uint64_t));</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+static ssize_t spsc_check_w(struct spsc *q)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ uint64_t efdr;</span><br><span style="color: hsl(120, 100%, 40%);">+ return read(q->efd_w, &efdr, sizeof(uint64_t));</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+static void spsc_notify_r(struct spsc *q)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ uint64_t efdu = 1;</span><br><span style="color: hsl(120, 100%, 40%);">+ write(q->efd_r, &efdu, sizeof(uint64_t));</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+static void spsc_notify_w(struct spsc *q)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ uint64_t efdu = 1;</span><br><span style="color: hsl(120, 100%, 40%);">+ write(q->efd_w, &efdu, sizeof(uint64_t));</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+bool spsc_push(struct spsc *q, void *elem)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ size_t cur_wp, cur_rp;</span><br><span style="color: hsl(120, 100%, 40%);">+ cur_wp = atomic_load_explicit(&q->writeptr, memory_order_relaxed);</span><br><span style="color: hsl(120, 100%, 40%);">+ cur_rp = atomic_load_explicit(&q->readptr, memory_order_acquire);</span><br><span style="color: hsl(120, 100%, 40%);">+ if ((cur_wp + 1) % q->count == cur_rp) {</span><br><span style="color: hsl(120, 100%, 40%);">+ spsc_check_w(q); // blocks, ensures next (!) call succeeds</span><br><span style="color: hsl(120, 100%, 40%);">+ return false;</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+ memcpy((void *)q->data[cur_wp], elem, q->size_per_buf);</span><br><span style="color: hsl(120, 100%, 40%);">+ atomic_store_explicit(&q->writeptr, (cur_wp + 1) % q->count, memory_order_release);</span><br><span style="color: hsl(120, 100%, 40%);">+ spsc_notify_r(q); // fine after release</span><br><span style="color: hsl(120, 100%, 40%);">+ return true;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/* just clear it - pop is called in a loop until empty, and next notification</span><br><span style="color: hsl(120, 100%, 40%);">+ * can't happen until it's not empty */</span><br><span style="color: hsl(120, 100%, 40%);">+ssize_t prep_pop(struct spsc *q)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ return spsc_check_r(q);</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+bool spsc_pop(struct spsc *q, void *elem)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ size_t cur_wp, cur_rp;</span><br><span style="color: hsl(120, 100%, 40%);">+ cur_wp = atomic_load_explicit(&q->writeptr, memory_order_acquire);</span><br><span style="color: hsl(120, 100%, 40%);">+ cur_rp = atomic_load_explicit(&q->readptr, memory_order_relaxed);</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ if (cur_wp == cur_rp) /* blocks via prep_pop */</span><br><span style="color: hsl(120, 100%, 40%);">+ return false;</span><br><span style="color: hsl(120, 100%, 40%);">+ memcpy(elem, (void *)q->data[cur_rp], q->size_per_buf);</span><br><span style="color: hsl(120, 100%, 40%);">+ atomic_store_explicit(&q->readptr, (cur_rp + 1) % q->count, memory_order_release);</span><br><span style="color: hsl(120, 100%, 40%);">+ spsc_notify_w(q);</span><br><span style="color: hsl(120, 100%, 40%);">+ return true;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*</span><br><span style="color: hsl(120, 100%, 40%);">+master: writes a, waits for rdfd of b</span><br><span style="color: hsl(120, 100%, 40%);">+slave: waits for rdfd of a, writes b</span><br><span style="color: hsl(120, 100%, 40%);">+wrfd used interally to block writers</span><br><span style="color: hsl(120, 100%, 40%);">+*/</span><br><span style="color: hsl(120, 100%, 40%);">+struct qchan chan_init_ex(unsigned int count, unsigned size_per_buf, bool blockr_a, bool blockw_a, bool blockr_b,</span><br><span style="color: hsl(120, 100%, 40%);">+ bool blockw_b)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ struct qchan q; // = calloc(1, sizeof(struct qchan));</span><br><span style="color: hsl(120, 100%, 40%);">+ q.a = spsc_init(count, size_per_buf, blockr_a, blockw_a);</span><br><span style="color: hsl(120, 100%, 40%);">+ q.b = spsc_init(count, size_per_buf, blockr_b, blockw_b);</span><br><span style="color: hsl(120, 100%, 40%);">+ return q;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+struct qchan chan_init(unsigned int count, unsigned size_per_buf)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ return chan_init_ex(count, size_per_buf, false, true, false, true);</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+void chan_close(struct qchan *q)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ spsc_deinit(q->a);</span><br><span style="color: hsl(120, 100%, 40%);">+ spsc_deinit(q->b);</span><br><span style="color: hsl(120, 100%, 40%);">+ free(q);</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+int get_a_rdfd(struct qchan *q)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ return q->a->efd_r;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+int get_b_rdfd(struct qchan *q)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ return q->b->efd_r;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+int get_a_wrfd(struct qchan *q)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ return q->a->efd_w;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+int get_b_wrfd(struct qchan *q)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ return q->b->efd_w;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span></span><br></pre><p>To view, visit <a href="https://gerrit.osmocom.org/c/osmo-mgw/+/25431">change 25431</a>. To unsubscribe, or for help writing mail filters, visit <a href="https://gerrit.osmocom.org/settings">settings</a>.</p><div itemscope itemtype="http://schema.org/EmailMessage"><div itemscope itemprop="action" itemtype="http://schema.org/ViewAction"><link itemprop="url" href="https://gerrit.osmocom.org/c/osmo-mgw/+/25431"/><meta itemprop="name" content="View Change"/></div></div>
<div style="display:none"> Gerrit-Project: osmo-mgw </div>
<div style="display:none"> Gerrit-Branch: master </div>
<div style="display:none"> Gerrit-Change-Id: I4f17042baf76d086ce6b20eb99402dc64c22c657 </div>
<div style="display:none"> Gerrit-Change-Number: 25431 </div>
<div style="display:none"> Gerrit-PatchSet: 1 </div>
<div style="display:none"> Gerrit-Owner: Hoernchen <ewild@sysmocom.de> </div>
<div style="display:none"> Gerrit-MessageType: newchange </div>