diff --git a/src/openvpn/mbuf.c b/src/openvpn/mbuf.c index 7b790ed..5bb397f 100644 --- a/src/openvpn/mbuf.c +++ b/src/openvpn/mbuf.c @@ -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); } } diff --git a/tests/unit_tests/openvpn/test_mbuf.c b/tests/unit_tests/openvpn/test_mbuf.c index cba4da7..61d438b 100644 --- a/tests/unit_tests/openvpn/test_mbuf.c +++ b/tests/unit_tests/openvpn/test_mbuf.c @@ -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);