@@ -85,6 +85,21 @@
}
}
+/*
+ * Dereferenced items cannot be removed from the middle of the ring, so
+ * reclaim them once they reach the head: a ring left without any live
+ * item must not keep looking full.
+ */
+static void
+mbuf_reclaim_head(struct mbuf_set *ms)
+{
+ while (ms->len && !ms->array[ms->head].instance)
+ {
+ ms->head = MBUF_INDEX(ms->head, 1, ms->capacity);
+ --ms->len;
+ }
+}
+
void
mbuf_add_item(struct mbuf_set *ms, const struct mbuf_item *item)
{
@@ -125,6 +140,7 @@
break;
}
}
+ mbuf_reclaim_head(ms);
}
return ret;
}
@@ -164,5 +180,6 @@
msg(D_MBUF, "MBUF: dereferenced queued packet");
}
}
+ mbuf_reclaim_head(ms);
}
}
@@ -136,9 +136,9 @@
mbuf_dereference_instance(ms, &mi2);
assert_int_equal(mbuf_buf->refcount, 2);
assert_int_equal(mbuf_buf2->refcount, 1);
- assert_int_equal(mbuf_len(ms), 3);
+ assert_int_equal(mbuf_len(ms), 1);
assert_int_equal(mbuf_maximum_queued(ms), 4);
- assert_int_equal(ms->head, 3);
+ assert_int_equal(ms->head, 1);
assert_ptr_equal(mbuf_peek(ms), &mi);
mbuf_free(ms);
@@ -148,12 +148,151 @@
mbuf_free_buf(mbuf_buf2);
}
+/* a queue holding nothing but dereferenced items is an empty queue */
+static void
+test_mbuf_dereference_reclaims_queue(void **state)
+{
+ struct mbuf_set *ms = mbuf_init(4);
+ struct multi_instance mi = { 0 };
+ struct buffer buf = alloc_buf(16);
+ struct mbuf_buffer *mbuf_buf = mbuf_alloc_buf(&buf);
+ struct mbuf_item item = { .buffer = mbuf_buf, .instance = &mi };
+ free_buf(&buf);
+
+ for (int i = 0; i < 4; ++i)
+ {
+ mbuf_add_item(ms, &item);
+ }
+ assert_int_equal(mbuf_len(ms), 4);
+ assert_int_equal(mbuf_buf->refcount, 5);
+
+ mbuf_dereference_instance(ms, &mi);
+
+ assert_int_equal(mbuf_len(ms), 0);
+ assert_false(mbuf_defined(ms));
+ assert_null(mbuf_peek(ms));
+ assert_int_equal(mbuf_buf->refcount, 1);
+
+ /* the queue is empty, so this must be queued and not dropped */
+ mbuf_add_item(ms, &item);
+ assert_int_equal(mbuf_len(ms), 1);
+ assert_ptr_equal(mbuf_peek(ms), &mi);
+
+ mbuf_free(ms);
+ mbuf_free_buf(mbuf_buf);
+}
+
+/* extracting the last live item must not leave a trailing hole behind */
+static void
+test_mbuf_extract_reclaims_tail(void **state)
+{
+ struct mbuf_set *ms = mbuf_init(4);
+ struct multi_instance mi = { 0 };
+ struct multi_instance mi2 = { 0 };
+ struct buffer buf = alloc_buf(16);
+ struct mbuf_buffer *mbuf_buf = mbuf_alloc_buf(&buf);
+ struct mbuf_item item = { .buffer = mbuf_buf, .instance = &mi };
+ struct mbuf_item item2 = { .buffer = mbuf_buf, .instance = &mi2 };
+ free_buf(&buf);
+
+ mbuf_add_item(ms, &item);
+ mbuf_add_item(ms, &item2);
+ mbuf_dereference_instance(ms, &mi2);
+ assert_int_equal(mbuf_len(ms), 2); /* head is still live, nothing to reclaim */
+
+ struct mbuf_item out;
+ assert_true(mbuf_extract_item(ms, &out));
+ assert_ptr_equal(out.instance, &mi);
+ mbuf_free_buf(out.buffer);
+
+ assert_int_equal(mbuf_len(ms), 0);
+ assert_false(mbuf_defined(ms));
+ assert_null(mbuf_peek(ms));
+
+ mbuf_free(ms);
+ mbuf_free_buf(mbuf_buf);
+}
+
+/* reclaiming stops at the first live item, it does not walk the whole ring */
+static void
+test_mbuf_extract_reclaims_up_to_live(void **state)
+{
+ struct mbuf_set *ms = mbuf_init(4);
+ struct multi_instance mi = { 0 };
+ struct multi_instance mi2 = { 0 };
+ struct buffer buf = alloc_buf(16);
+ struct mbuf_buffer *mbuf_buf = mbuf_alloc_buf(&buf);
+ struct mbuf_item item = { .buffer = mbuf_buf, .instance = &mi };
+ struct mbuf_item item2 = { .buffer = mbuf_buf, .instance = &mi2 };
+ free_buf(&buf);
+
+ /* [mi][mi2][mi] -> dereferencing mi2 leaves [mi][hole][mi] */
+ mbuf_add_item(ms, &item);
+ mbuf_add_item(ms, &item2);
+ mbuf_add_item(ms, &item);
+ mbuf_dereference_instance(ms, &mi2);
+ assert_int_equal(mbuf_len(ms), 3); /* head is live, nothing to reclaim yet */
+
+ /* extracting the head leaves the hole in front: it must be reclaimed, and
+ * the walk must stop at the live item behind it */
+ struct mbuf_item out;
+ assert_true(mbuf_extract_item(ms, &out));
+ assert_ptr_equal(out.instance, &mi);
+ mbuf_free_buf(out.buffer);
+
+ assert_int_equal(mbuf_len(ms), 1);
+ assert_true(mbuf_defined(ms));
+ assert_ptr_equal(mbuf_peek(ms), &mi);
+
+ mbuf_free(ms);
+ mbuf_free_buf(mbuf_buf);
+}
+
+/* Holes behind a live item are not reclaimed, so a full ring can still hold
+ * them. mbuf_add_item() must cope: it evicts the live head, which drags the
+ * holes with it, rather than finding nothing to drop. */
+static void
+test_mbuf_add_on_full_queue_with_holes(void **state)
+{
+ struct mbuf_set *ms = mbuf_init(4);
+ struct multi_instance mi = { 0 };
+ struct multi_instance mi2 = { 0 };
+ struct multi_instance mi3 = { 0 };
+ struct buffer buf = alloc_buf(16);
+ struct mbuf_buffer *mbuf_buf = mbuf_alloc_buf(&buf);
+ struct mbuf_item item = { .buffer = mbuf_buf, .instance = &mi };
+ struct mbuf_item item2 = { .buffer = mbuf_buf, .instance = &mi2 };
+ struct mbuf_item item3 = { .buffer = mbuf_buf, .instance = &mi3 };
+ free_buf(&buf);
+
+ /* [mi][mi2][mi2][mi2] -> dereferencing mi2 leaves [mi][hole][hole][hole],
+ * which mbuf_reclaim_head() cannot touch: the head is still live */
+ mbuf_add_item(ms, &item);
+ mbuf_add_item(ms, &item2);
+ mbuf_add_item(ms, &item2);
+ mbuf_add_item(ms, &item2);
+ mbuf_dereference_instance(ms, &mi2);
+ assert_int_equal(mbuf_len(ms), 4);
+ assert_int_equal(mbuf_len(ms), ms->capacity); /* still counts as full */
+
+ mbuf_add_item(ms, &item3);
+ assert_int_equal(mbuf_len(ms), 1);
+ assert_ptr_equal(mbuf_peek(ms), &mi3);
+
+ mbuf_free(ms);
+ mbuf_free_buf(mbuf_buf);
+}
+
int
main(void)
{
const struct CMUnitTest tests[] = {
cmocka_unit_test(test_mbuf_init),
cmocka_unit_test(test_mbuf_add_remove),
+ cmocka_unit_test(test_mbuf_dereference_reclaims_queue),
+ cmocka_unit_test(test_mbuf_extract_reclaims_tail),
+ cmocka_unit_test(test_mbuf_extract_reclaims_up_to_live),
+ cmocka_unit_test(test_mbuf_add_on_full_queue_with_holes),
};
return cmocka_run_group_tests_name("mbuf", tests, NULL, NULL);