feat: merge dummy entry of transfer list
When transfer_list_set_data_size() is called in sequence—first to
shrink an entry, then to expand it—the dummy entry created during
the shrink is not reused in the expansion.
This leaves unused dummy entries that increase the total size of
the transfer list unnecessarily.
This patch addresses that by:
1. Reusing a following dummy entry when expanding
the size of a transfer list entry.
2. Merging adjacent dummy entries when removing an entry,
reducing fragmentation and improving reuse.
Change-Id: Ieb61b345117bdfe93348995af022a17a00f8728d
Signed-off-by: Yeoreum Yun <yeoreum.yun@arm.com>
diff --git a/src/transfer_list.c b/src/transfer_list.c
index 8b7d0d0..369c331 100644
--- a/src/transfer_list.c
+++ b/src/transfer_list.c
@@ -227,6 +227,28 @@
}
/*******************************************************************************
+ * Enumerate the prev transfer entry
+ * Return pointer to the prev transfer entry or NULL on error
+ ******************************************************************************/
+struct transfer_list_entry *transfer_list_prev(struct transfer_list_header *tl,
+ struct transfer_list_entry *last)
+{
+ struct transfer_list_entry *prev;
+ struct transfer_list_entry *te = NULL;
+
+ if (!last || !tl || (tl + tl->hdr_size == (void *)last)) {
+ return NULL;
+ }
+
+ do {
+ prev = te;
+ te = transfer_list_next(tl, te);
+ } while (te && te != last);
+
+ return (te != NULL) ? prev : NULL;
+}
+
+/*******************************************************************************
* Calculate the byte sum of a transfer list
* Return byte sum of the transfer list
******************************************************************************/
@@ -287,7 +309,7 @@
struct transfer_list_entry *te,
uint32_t new_data_size)
{
- uintptr_t tl_old_ev, new_ev = 0, old_ev = 0, ru_new_ev;
+ uintptr_t tl_old_ev, new_ev = 0, old_ev = 0, merge_ev, ru_new_ev;
struct transfer_list_entry *dummy_te = NULL;
size_t gap = 0;
size_t mov_dis = 0;
@@ -315,6 +337,27 @@
if (new_ev > old_ev) {
/*
+ * When next transfer list is dummy,
+ * - if te can be extended in boundary of dummy entry,
+ * extend it to dummy entry and set new dummy entry.
+ *
+ * - otherwise, merge dummy entry with existing te and
+ * extend transfer list as much as it requires.
+ */
+ dummy_te = transfer_list_next(tl, te);
+ if (dummy_te && (dummy_te->tag_id == TL_TAG_EMPTY)) {
+ merge_ev = align_up(old_ev + dummy_te->hdr_size +
+ dummy_te->data_size,
+ TRANSFER_LIST_GRANULE);
+ if (merge_ev >= new_ev) {
+ gap = merge_ev - new_ev;
+ goto set_dummy;
+ } else {
+ old_ev = merge_ev;
+ }
+ }
+
+ /*
* move distance should be roundup
* to meet the requirement of TE data max alignment
* ensure that the increased size doesn't exceed
@@ -333,6 +376,7 @@
gap = old_ev - new_ev;
}
+set_dummy:
if (gap >= sizeof(*dummy_te)) {
/* create a dummy TE to fill up the gap */
dummy_te = (struct transfer_list_entry *)new_ev;
@@ -354,9 +398,27 @@
bool transfer_list_rem(struct transfer_list_header *tl,
struct transfer_list_entry *te)
{
+ struct transfer_list_entry *prev;
+ struct transfer_list_entry *next;
+
if (!tl || !te || (uintptr_t)te > (uintptr_t)tl + tl->size) {
return false;
}
+
+ prev = transfer_list_prev(tl, te);
+ next = transfer_list_next(tl, te);
+
+ if (prev && prev->tag_id == TL_TAG_EMPTY) {
+ prev->data_size += align_up(te->hdr_size + te->data_size,
+ TRANSFER_LIST_GRANULE);
+ te = prev;
+ }
+
+ if (next && next->tag_id == TL_TAG_EMPTY) {
+ te->data_size += align_up(next->hdr_size + next->data_size,
+ TRANSFER_LIST_GRANULE);
+ }
+
te->tag_id = TL_TAG_EMPTY;
transfer_list_update_checksum(tl);
return true;
diff --git a/test/entry_manipulation.c b/test/entry_manipulation.c
index 72088bb..bf01014 100644
--- a/test/entry_manipulation.c
+++ b/test/entry_manipulation.c
@@ -6,16 +6,18 @@
#include <stdio.h>
#include <stdlib.h>
+#include <string.h>
#include "test.h"
#include "transfer_list.h"
#include "unity.h"
void *buffer = NULL;
+char *test_page_data = NULL;
uint8_t byte_sum(const char *ptr, size_t len)
{
- uint8_t sum;
+ uint8_t sum = 0;
for (size_t i = 0; i < len; i++) {
sum += ptr[i];
@@ -24,6 +26,25 @@
return sum;
}
+static void setup_test_entries(struct transfer_list_header *tl,
+ unsigned int tag_base, unsigned int num_entries,
+ struct transfer_list_entry **entries)
+{
+ unsigned int i;
+ unsigned int te_data_size;
+ struct transfer_list_entry *te;
+
+ te_data_size = tl->max_size / (num_entries * 2);
+
+ for (i = 0; i < num_entries; i++) {
+ TEST_ASSERT(transfer_list_add(tl, tag_base + i, te_data_size,
+ test_page_data));
+ TEST_ASSERT(te = transfer_list_find(tl, tag_base + i));
+ TEST_ASSERT(byte_sum((void *)tl, tl->size) == 0);
+ entries[i] = te;
+ }
+}
+
void test_add()
{
struct transfer_list_header *tl;
@@ -93,29 +114,83 @@
void test_rem()
{
struct transfer_list_header *tl = transfer_list_init(buffer, TL_SIZE);
- struct transfer_list_entry *te;
+ struct transfer_list_entry *te[3];
+ unsigned int tag_base = test_tag;
TEST_ASSERT_EQUAL(tl->size, tl->hdr_size);
- /* Add a test TE, check the TL has been updated with its contents. */
- TEST_ASSERT(
- transfer_list_add(tl, test_tag, tl->max_size / 8, &test_data));
- TEST_ASSERT(te = transfer_list_find(tl, test_tag));
- TEST_ASSERT(byte_sum((void *)tl, tl->size) == 0);
+ setup_test_entries(tl, tag_base, 3, te);
- /* Remove the TE and make sure it isn't present in the TL. */
- TEST_ASSERT_TRUE(transfer_list_rem(tl, te));
+ /* Remove the TE and make sure it does not present in the TL. */
+ TEST_ASSERT_TRUE(transfer_list_rem(tl, te[0]));
TEST_ASSERT(byte_sum((void *)tl, tl->size) == 0);
- TEST_ASSERT_NULL(transfer_list_find(tl, test_tag));
+ TEST_ASSERT_NULL(transfer_list_find(tl, tag_base));
+
+ /* Remove the TE3 and make sure it does not present in the TL. */
+ TEST_ASSERT_TRUE(transfer_list_rem(tl, te[2]));
+ TEST_ASSERT(byte_sum((void *)tl, tl->size) == 0);
+ TEST_ASSERT_NULL(transfer_list_find(tl, tag_base + 2));
+
+ /* Remove the TE2 and make sure it does not present in the TL. */
+ TEST_ASSERT_TRUE(transfer_list_rem(tl, te[1]));
+ TEST_ASSERT(byte_sum((void *)tl, tl->size) == 0);
+ TEST_ASSERT_NULL(transfer_list_find(tl, tag_base + 1));
+
+ /*
+ * Should have only one TL_TAG_EMPTY entry.
+ */
+ TEST_ASSERT(te[0] = transfer_list_find(tl, TL_TAG_EMPTY));
+ TEST_ASSERT(transfer_list_next(tl, te[0]) == NULL);
+}
+
+void test_set_data_size()
+{
+ struct transfer_list_header *tl = transfer_list_init(buffer, TL_SIZE);
+ struct transfer_list_entry *te[3];
+ unsigned int tag_base = test_tag;
+ unsigned int tl_size;
+
+ TEST_ASSERT_EQUAL(tl->size, tl->hdr_size);
+
+ setup_test_entries(tl, tag_base, 3, te);
+
+ /* Remove the TE2 and make sure it does not present in the TL. */
+ TEST_ASSERT_TRUE(transfer_list_rem(tl, te[1]));
+ TEST_ASSERT(byte_sum((void *)tl, tl->size) == 0);
+ TEST_ASSERT_NULL(transfer_list_find(tl, tag_base + 1));
+
+ /*
+ * Increase te size to tl->max_size / 4, this shouldn't increase the
+ * current transfer list's size since it will be increased with
+ * adjacent TL_TAG_EMPTY entry.
+ */
+ tl_size = tl->size;
+ TEST_ASSERT(transfer_list_set_data_size(tl, te[0], tl->max_size / 4));
+ TEST_ASSERT(byte_sum((void *)tl, tl->size) == 0);
+ TEST_ASSERT(te[0]->data_size == tl->max_size / 4);
+ TEST_ASSERT(tl_size == tl->size);
+
+ /*
+ * Increase te size to tl->max_size / 2, this increases
+ * the transfer list size.
+ */
+ tl_size = tl->size;
+ TEST_ASSERT(transfer_list_set_data_size(tl, te[0], tl->max_size / 2));
+ TEST_ASSERT(byte_sum((void *)tl, tl->size) == 0);
+ TEST_ASSERT(te[0]->data_size == tl->max_size / 2);
+ TEST_ASSERT(tl_size < tl->size);
}
void setUp(void)
{
buffer = malloc(TL_MAX_SIZE);
+ test_page_data = malloc(TL_SIZE);
+ memset(test_page_data, 0xff, TL_SIZE);
}
void tearDown(void)
{
+ free(test_page_data);
free(buffer);
buffer = NULL;
}
@@ -125,5 +200,7 @@
UNITY_BEGIN();
RUN_TEST(test_add);
RUN_TEST(test_add_with_align);
+ RUN_TEST(test_rem);
+ RUN_TEST(test_set_data_size);
return UNITY_END();
}