Skip to contentSkip to conversation

Task local data bug fixes and improvement

PATCH Superseded Amery Hung 3 participants 12 messages Mar 26 – Mar 27

Subsystems (3)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Amery Hung

author
#0 lore raw

cover Task local data bug fixes and improvement

Hi,

This patchset fixed two task local data bugs and improved the memory allocation code. Please find the detail in each patch's commit msg.

Amery Hung (3):
selftests/bpf: Fix task_local_data data allocation size selftests/bpf: Simplify task_local_data memory allocation selftests/bpf: Make sure TLD_DEFINE_KEY runs first

 .../bpf/prog_tests/task_local_data.h          | 66 ++++++++-----------
 1 file changed, 26 insertions(+), 40 deletions(-)
Signature · 1 line
2.52.0
author
#1 lore raw

PATCH 1/3 selftests/bpf: Fix task_local_data data allocation size

Currently, when allocating memory for data, size of tld_data_u->start is not taken into account. This may cause OOB access. Fixed it by adding the non-flexible array part of tld_datg_u.

Besides, explicitly align tld_data_u->data to 8 bytes in case some fields are added before data in the future. It could break the assumption that every data field is 8 byte aligned and sizeof(tld_data_u) will no longer be equal to offsetof(struct tld_data_u, data), which we use interchangeably.

---
 .../selftests/bpf/prog_tests/task_local_data.h       | 12 +++++++-----
 1 file changed, 7 insertions(+), 5 deletions(-)
tools/testing/selftests/bpf/prog_tests/task_local_data.h +7 -5
index 7819f318b2fb..a52d8b549425 100644
@@ -90,7 +90,7 @@ typedef struct {
 
 struct tld_metadata {
 	char name[TLD_NAME_LEN];
-	_Atomic __u16 size;
+	_Atomic __u16 size; /* size of tld_data_u->data */
 };
 
 struct tld_meta_u {
@@ -101,7 +101,7 @@ struct tld_meta_u {
 
 struct tld_data_u {
 	__u64 start; /* offset of tld_data_u->data in a page */
-	char data[];
+	char data[] __attribute__((aligned(8)));
 };
 
 struct tld_map_value {
@@ -158,6 +158,7 @@ static int __tld_init_data_p(int map_fd)
 	struct tld_data_u *data;
 	void *data_alloc = NULL;
 	int err, tid_fd = -1;
+	size_t size;
 
 	tid_fd = syscall(SYS_pidfd_open, sys_gettid(), O_EXCL);
 	if (tid_fd < 0) {
@@ -173,9 +174,10 @@ static int __tld_init_data_p(int map_fd)
 	 * tld_meta_p->size = TLD_DYN_DATA_SIZE +
 	 *          total size of TLDs defined via TLD_DEFINE_KEY()
 	 */
-	data_alloc = (use_aligned_alloc || tld_meta_p->size * 2 >= TLD_PAGE_SIZE) ?
-		aligned_alloc(TLD_PAGE_SIZE, tld_meta_p->size) :
-		malloc(tld_meta_p->size * 2);
+	size = tld_meta_p->size + sizeof(struct tld_data_u);
+	data_alloc = (use_aligned_alloc || size * 2 >= TLD_PAGE_SIZE) ?
+		aligned_alloc(TLD_PAGE_SIZE, size) :
+		malloc(size * 2);
 	if (!data_alloc) {
 		err = -ENOMEM;
 		goto out;
Signature · 1 line
2.52.0
#2 lore raw

Re: [PATCH bpf-next v1 1/3] selftests/bpf: Fix task_local_data data allocation size

Quoted 4 lines · Amery Hung

Currently, when allocating memory for data, size of tld_data_u->start is not taken into account. This may cause OOB access. Fixed it by adding the non-flexible array part of tld_datg_u.

nit: seems to be a typo of tld_data_u?

Quoted 43 lines

Besides, explicitly align tld_data_u->data to 8 bytes in case some fields are added before data in the future. It could break the assumption that every data field is 8 byte aligned and sizeof(tld_data_u) will no longer be equal to offsetof(struct tld_data_u, data), which we use interchangeably.

---
 .../selftests/bpf/prog_tests/task_local_data.h       | 12 +++++++-----
 1 file changed, 7 insertions(+), 5 deletions(-)
tools/testing/selftests/bpf/prog_tests/task_local_data.h +3 -2
index 7819f318b2fb..a52d8b549425 100644
@@ -90,7 +90,7 @@ typedef struct {
 
 struct tld_metadata {
        char name[TLD_NAME_LEN];
-       _Atomic __u16 size;
+       _Atomic __u16 size; /* size of tld_data_u->data */
 };
 
 struct tld_meta_u {
@@ -101,7 +101,7 @@ struct tld_meta_u {
 
 struct tld_data_u {
        __u64 start; /* offset of tld_data_u->data in a page */
-       char data[];
+       char data[] __attribute__((aligned(8)));
 };
 
 struct tld_map_value {
@@ -158,6 +158,7 @@ static int __tld_init_data_p(int map_fd)
        struct tld_data_u *data;
        void *data_alloc = NULL;
        int err, tid_fd = -1;
+       size_t size;
 
        tid_fd = syscall(SYS_pidfd_open, sys_gettid(), O_EXCL);
        if (tid_fd < 0) {

tools/testing/selftests/bpf/prog_tests/task_local_data.h static int __tld_init_data_p(int map_fd) · line 179

Quoted 9 lines
tools/testing/selftests/bpf/prog_tests/task_local_data.h +3 -3
@@ -173,9 +174,10 @@ static int __tld_init_data_p(int map_fd)
         * tld_meta_p->size = TLD_DYN_DATA_SIZE +
         *          total size of TLDs defined via TLD_DEFINE_KEY()
         */
-       data_alloc = (use_aligned_alloc || tld_meta_p->size * 2 >= TLD_PAGE_SIZE) ?
-               aligned_alloc(TLD_PAGE_SIZE, tld_meta_p->size) :
-               malloc(tld_meta_p->size * 2);
+       size = tld_meta_p->size + sizeof(struct tld_data_u);
+       data_alloc = (use_aligned_alloc || size * 2 >= TLD_PAGE_SIZE) ?
+               aligned_alloc(TLD_PAGE_SIZE, size) :

with start now included, size seems even less likely to be a multiple of TLD_PAGE_SIZE. Could aligned_alloc() fail here?

Quoted 8 lines
tools/testing/selftests/bpf/prog_tests/task_local_data.h +1 -1
+               malloc(size * 2);
        if (!data_alloc) {
                err = -ENOMEM;
                goto out;
--

2.52.0

author
#3 lore raw

Re: [PATCH bpf-next v1 1/3] selftests/bpf: Fix task_local_data data allocation size

Quoted 7 lines · sun jian
Quoted 4 lines · Amery Hung

Currently, when allocating memory for data, size of tld_data_u->start is not taken into account. This may cause OOB access. Fixed it by adding the non-flexible array part of tld_datg_u.

nit: seems to be a typo of tld_data_u?

Ah yes

Quoted 40 lines
Quoted 40 lines

Besides, explicitly align tld_data_u->data to 8 bytes in case some fields are added before data in the future. It could break the assumption that every data field is 8 byte aligned and sizeof(tld_data_u) will no longer be equal to offsetof(struct tld_data_u, data), which we use interchangeably.

---
 .../selftests/bpf/prog_tests/task_local_data.h       | 12 +++++++-----
 1 file changed, 7 insertions(+), 5 deletions(-)
tools/testing/selftests/bpf/prog_tests/task_local_data.h +3 -2
index 7819f318b2fb..a52d8b549425 100644
@@ -90,7 +90,7 @@ typedef struct {
 
 struct tld_metadata {
        char name[TLD_NAME_LEN];
-       _Atomic __u16 size;
+       _Atomic __u16 size; /* size of tld_data_u->data */
 };
 
 struct tld_meta_u {
@@ -101,7 +101,7 @@ struct tld_meta_u {
 
 struct tld_data_u {
        __u64 start; /* offset of tld_data_u->data in a page */
-       char data[];
+       char data[] __attribute__((aligned(8)));
 };
 
 struct tld_map_value {
@@ -158,6 +158,7 @@ static int __tld_init_data_p(int map_fd)
        struct tld_data_u *data;
        void *data_alloc = NULL;
        int err, tid_fd = -1;
+       size_t size;
 
Quoted 14 lines

tools/testing/selftests/bpf/prog_tests/task_local_data.h static int __tld_init_data_p(int map_fd) · line 179

Quoted 12 lines
tools/testing/selftests/bpf/prog_tests/task_local_data.h +3 -3
        tid_fd = syscall(SYS_pidfd_open, sys_gettid(), O_EXCL);
        if (tid_fd < 0) {
@@ -173,9 +174,10 @@ static int __tld_init_data_p(int map_fd)
         * tld_meta_p->size = TLD_DYN_DATA_SIZE +
         *          total size of TLDs defined via TLD_DEFINE_KEY()
         */
-       data_alloc = (use_aligned_alloc || tld_meta_p->size * 2 >= TLD_PAGE_SIZE) ?
-               aligned_alloc(TLD_PAGE_SIZE, tld_meta_p->size) :
-               malloc(tld_meta_p->size * 2);
+       size = tld_meta_p->size + sizeof(struct tld_data_u);
+       data_alloc = (use_aligned_alloc || size * 2 >= TLD_PAGE_SIZE) ?
+               aligned_alloc(TLD_PAGE_SIZE, size) :

with start now included, size seems even less likely to be a multiple of TLD_PAGE_SIZE. Could aligned_alloc() fail here?

Hi, Thanks for taking a look.

This indeed could be a problem. Passing size not being an integral multiple of alignment can be undefined behavior for some memory allocators. This is okay for TLD_DATA_USE_ALIGNED_ALLOC as it should only be enabled when users know the memory allocator supports it. However, aligned_alloc() is always used when size * 2 > TLD_PAGE_SIZE, which may lead to UB.

This issue is addressed in patch 2 when the allocation path is cleaned up.

Quoted 8 lines
Quoted 8 lines
tools/testing/selftests/bpf/prog_tests/task_local_data.h +1 -1
+               malloc(size * 2);
        if (!data_alloc) {
                err = -ENOMEM;
                goto out;
--

2.52.0

#4 lore raw

Re: [PATCH bpf-next v1 1/3] selftests/bpf: Fix task_local_data data allocation size

In reply to Amery Hung
Quoted 46 lines · Amery Hung

Currently, when allocating memory for data, size of tld_data_u->start is not taken into account. This may cause OOB access. Fixed it by adding the non-flexible array part of tld_datg_u.

Besides, explicitly align tld_data_u->data to 8 bytes in case some fields are added before data in the future. It could break the assumption that every data field is 8 byte aligned and sizeof(tld_data_u) will no longer be equal to offsetof(struct tld_data_u, data), which we use interchangeably.

---
 .../selftests/bpf/prog_tests/task_local_data.h       | 12 +++++++-----
 1 file changed, 7 insertions(+), 5 deletions(-)
tools/testing/selftests/bpf/prog_tests/task_local_data.h +3 -2
index 7819f318b2fb..a52d8b549425 100644
@@ -90,7 +90,7 @@ typedef struct {
 
 struct tld_metadata {
 	char name[TLD_NAME_LEN];
-	_Atomic __u16 size;
+	_Atomic __u16 size; /* size of tld_data_u->data */
 };
 
 struct tld_meta_u {
@@ -101,7 +101,7 @@ struct tld_meta_u {
 
 struct tld_data_u {
 	__u64 start; /* offset of tld_data_u->data in a page */
-	char data[];
+	char data[] __attribute__((aligned(8)));
 };
 
 struct tld_map_value {
@@ -158,6 +158,7 @@ static int __tld_init_data_p(int map_fd)
 	struct tld_data_u *data;
 	void *data_alloc = NULL;
 	int err, tid_fd = -1;
+	size_t size;
 
 	tid_fd = syscall(SYS_pidfd_open, sys_gettid(), O_EXCL);
 	if (tid_fd < 0) {

tools/testing/selftests/bpf/prog_tests/task_local_data.h static int __tld_init_data_p(int map_fd) · line 180

Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/task_local_data.h +4 -3
@@ -173,9 +174,10 @@ static int __tld_init_data_p(int map_fd)
 	 * tld_meta_p->size = TLD_DYN_DATA_SIZE +
 	 *          total size of TLDs defined via TLD_DEFINE_KEY()
 	 */
-	data_alloc = (use_aligned_alloc || tld_meta_p->size * 2 >= TLD_PAGE_SIZE) ?
-		aligned_alloc(TLD_PAGE_SIZE, tld_meta_p->size) :
-		malloc(tld_meta_p->size * 2);
+	size = tld_meta_p->size + sizeof(struct tld_data_u);
+	data_alloc = (use_aligned_alloc || size * 2 >= TLD_PAGE_SIZE) ?
+		aligned_alloc(TLD_PAGE_SIZE, size) :
+		malloc(size * 2);

It looks like there is no point having Patch 1 separately, most of it is overwritten in the Patch 2, I understand you want to have fix and simplification separately, but is it really worth it for this selftest.

Quoted 5 lines
tools/testing/selftests/bpf/prog_tests/task_local_data.h +0 -0
 	if (!data_alloc) {
 		err = -ENOMEM;
 		goto out;
Signature · 1 line
2.52.0
author
#5 lore raw

Re: [PATCH bpf-next v1 1/3] selftests/bpf: Fix task_local_data data allocation size

Quoted 46 lines · Mykyta Yatsenko
Quoted 43 lines · Amery Hung

Currently, when allocating memory for data, size of tld_data_u->start is not taken into account. This may cause OOB access. Fixed it by adding the non-flexible array part of tld_datg_u.

Besides, explicitly align tld_data_u->data to 8 bytes in case some fields are added before data in the future. It could break the assumption that every data field is 8 byte aligned and sizeof(tld_data_u) will no longer be equal to offsetof(struct tld_data_u, data), which we use interchangeably.

---
 .../selftests/bpf/prog_tests/task_local_data.h       | 12 +++++++-----
 1 file changed, 7 insertions(+), 5 deletions(-)
tools/testing/selftests/bpf/prog_tests/task_local_data.h +3 -2
index 7819f318b2fb..a52d8b549425 100644
@@ -90,7 +90,7 @@ typedef struct {
 
 struct tld_metadata {
      char name[TLD_NAME_LEN];
-     _Atomic __u16 size;
+     _Atomic __u16 size; /* size of tld_data_u->data */
 };
 
 struct tld_meta_u {
@@ -101,7 +101,7 @@ struct tld_meta_u {
 
 struct tld_data_u {
      __u64 start; /* offset of tld_data_u->data in a page */
-     char data[];
+     char data[] __attribute__((aligned(8)));
 };
 
 struct tld_map_value {
@@ -158,6 +158,7 @@ static int __tld_init_data_p(int map_fd)
      struct tld_data_u *data;
      void *data_alloc = NULL;
      int err, tid_fd = -1;
+     size_t size;
 
Quoted 16 lines

tools/testing/selftests/bpf/prog_tests/task_local_data.h static int __tld_init_data_p(int map_fd) · line 180

Quoted 13 lines
tools/testing/selftests/bpf/prog_tests/task_local_data.h +4 -3
      tid_fd = syscall(SYS_pidfd_open, sys_gettid(), O_EXCL);
      if (tid_fd < 0) {
@@ -173,9 +174,10 @@ static int __tld_init_data_p(int map_fd)
       * tld_meta_p->size = TLD_DYN_DATA_SIZE +
       *          total size of TLDs defined via TLD_DEFINE_KEY()
       */
-     data_alloc = (use_aligned_alloc || tld_meta_p->size * 2 >= TLD_PAGE_SIZE) ?
-             aligned_alloc(TLD_PAGE_SIZE, tld_meta_p->size) :
-             malloc(tld_meta_p->size * 2);
+     size = tld_meta_p->size + sizeof(struct tld_data_u);
+     data_alloc = (use_aligned_alloc || size * 2 >= TLD_PAGE_SIZE) ?
+             aligned_alloc(TLD_PAGE_SIZE, size) :
+             malloc(size * 2);

It looks like there is no point having Patch 1 separately, most of it is overwritten in the Patch 2, I understand you want to have fix and simplification separately, but is it really worth it for this selftest.

The allocation path is already a bit puzzling, so I have this fix as a separate patch to make patch 2 easier to follow.

That said, I can squash it if it is simpler and needs a respin.

Quoted 5 lines
Quoted 5 lines
tools/testing/selftests/bpf/prog_tests/task_local_data.h +0 -1
      if (!data_alloc) {
              err = -ENOMEM;
              goto out;
--

2.52.0

author
#6 lore raw

PATCH 2/3 selftests/bpf: Simplify task_local_data memory allocation

In reply to Amery Hung

Simplify data allocation by always using aligned_alloc() and passing size_pot, size rounded up to the closest power of two to alignment.

Currently, aligned_alloc(page_size, size) is only intended to be used with memory allocators that can fulfill the request without rounding size up to page_size to conserve memory. This is enabled by defining TLD_DATA_USE_ALIGNED_ALLOC. The reason to align to page_size is due to the limitation of UPTR where only a page can be pinned to the kernel. Otherwise, malloc(size * 2) is used to allocate memory for data.

However, we don't need to call aligned_alloc(page_size, size) to get a contiguous memory of size bytes within a page. aligned_alloc(size_pot, ...) will also do the trick. Therefore, just use aligned_alloc(size_pot, ...) universally.

As for the size argument, create a new option, TLD_DONT_ROUND_UP_DATA_SIZE, to specify not rounding up the size. This preserves the current TLD_DATA_USE_ALIGNED_ALLOC behavior, allowing memory allocators with low overhead aligned_alloc() to not waste memory. To enable this, users need to make sure it is not an undefined behavior for the memory allocator to have size not being an integral multiple of alignment.

Compared to the current implementation, !TLD_DATA_USE_ALIGNED_ALLOC used to always waste size-byte of memory due to malloc(size * 2). Now the worst case becomes size - 1 and the best case is 0 when the size is already a power of two.

---
 .../bpf/prog_tests/task_local_data.h          | 60 +++++++------------
 1 file changed, 22 insertions(+), 38 deletions(-)
tools/testing/selftests/bpf/prog_tests/task_local_data.h +22 -38
index a52d8b549425..366a6739c086 100644
@@ -50,16 +50,13 @@
  *   TLD_MAX_DATA_CNT.
  *
  *
- *   TLD_DATA_USE_ALIGNED_ALLOC - Always use aligned_alloc() instead of malloc()
+ *   TLD_DONT_ROUND_UP_DATA_SIZE - Don't round up memory size allocated for data if
+ *   the memory allocator has low overhead aligned_alloc() implementation.
  *
- *   When allocating the memory for storing TLDs, we need to make sure there is a memory
- *   region of the X bytes within a page. This is due to the limit posed by UPTR: memory
- *   pinned to the kernel cannot exceed a page nor can it cross the page boundary. The
- *   library normally calls malloc(2*X) given X bytes of total TLDs, and only uses
- *   aligned_alloc(PAGE_SIZE, X) when X >= PAGE_SIZE / 2. This is to reduce memory wastage
- *   as not all memory allocator can use the exact amount of memory requested to fulfill
- *   aligned_alloc(). For example, some may round the size up to the alignment. Enable the
- *   option to always use aligned_alloc() if the implementation has low memory overhead.
+ *   For some memory allocators, when calling aligned_alloc(alignment, size), size
+ *   does not need to be an integral multiple of alignment and it can be fulfilled
+ *   without using round_up(size, alignment) bytes of memory. Enable this option to
+ *   reduce memory usage.
  */
 
 #define TLD_PAGE_SIZE getpagesize()
@@ -68,6 +65,8 @@
 #define TLD_ROUND_MASK(x, y) ((__typeof__(x))((y) - 1))
 #define TLD_ROUND_UP(x, y) ((((x) - 1) | TLD_ROUND_MASK(x, y)) + 1)
 
+#define TLD_ROUND_UP_POWER_OF_TWO(x) (1UL << (sizeof(x) * 8 - __builtin_clzl(x - 1)))
+
 #define TLD_READ_ONCE(x) (*(volatile typeof(x) *)&(x))
 
 #ifndef TLD_DYN_DATA_SIZE
@@ -111,7 +110,6 @@ struct tld_map_value {
 
 struct tld_meta_u * _Atomic tld_meta_p __attribute__((weak));
 __thread struct tld_data_u *tld_data_p __attribute__((weak));
-__thread void *tld_data_alloc_p __attribute__((weak));
 
 #ifdef TLD_FREE_DATA_ON_THREAD_EXIT
 pthread_key_t tld_pthread_key __attribute__((weak));
@@ -153,12 +151,10 @@ static int __tld_init_meta_p(void)
 
 static int __tld_init_data_p(int map_fd)
 {
-	bool use_aligned_alloc = false;
 	struct tld_map_value map_val;
 	struct tld_data_u *data;
-	void *data_alloc = NULL;
 	int err, tid_fd = -1;
-	size_t size;
+	size_t size, size_pot;
 
 	tid_fd = syscall(SYS_pidfd_open, sys_gettid(), O_EXCL);
 	if (tid_fd < 0) {
@@ -166,48 +162,37 @@ static int __tld_init_data_p(int map_fd)
 		goto out;
 	}
 
-#ifdef TLD_DATA_USE_ALIGNED_ALLOC
-	use_aligned_alloc = true;
-#endif
-
 	/*
 	 * tld_meta_p->size = TLD_DYN_DATA_SIZE +
 	 *          total size of TLDs defined via TLD_DEFINE_KEY()
 	 */
 	size = tld_meta_p->size + sizeof(struct tld_data_u);
-	data_alloc = (use_aligned_alloc || size * 2 >= TLD_PAGE_SIZE) ?
-		aligned_alloc(TLD_PAGE_SIZE, size) :
-		malloc(size * 2);
-	if (!data_alloc) {
+	size_pot = TLD_ROUND_UP_POWER_OF_TWO(size);
+#ifdef TLD_DONT_ROUND_UP_DATA_SIZE
+	data = (struct tld_data_u *)aligned_alloc(size_pot, size);
+#else
+	data = (struct tld_data_u *)aligned_alloc(size_pot, size_pot);
+#endif
+	if (!data) {
 		err = -ENOMEM;
 		goto out;
 	}
 
 	/*
 	 * Always pass a page-aligned address to UPTR since the size of tld_map_value::data
-	 * is a page in BTF. If data_alloc spans across two pages, use the page that contains large
-	 * enough memory.
+	 * is a page in BTF.
 	 */
-	if (TLD_PAGE_SIZE - (~TLD_PAGE_MASK & (intptr_t)data_alloc) >= tld_meta_p->size) {
-		map_val.data = (void *)(TLD_PAGE_MASK & (intptr_t)data_alloc);
-		data = data_alloc;
-		data->start = (~TLD_PAGE_MASK & (intptr_t)data_alloc) +
-			      offsetof(struct tld_data_u, data);
-	} else {
-		map_val.data = (void *)(TLD_ROUND_UP((intptr_t)data_alloc, TLD_PAGE_SIZE));
-		data = (void *)(TLD_ROUND_UP((intptr_t)data_alloc, TLD_PAGE_SIZE));
-		data->start = offsetof(struct tld_data_u, data);
-	}
+	map_val.data = (void *)(TLD_PAGE_MASK & (intptr_t)data);
+	data->start = (~TLD_PAGE_MASK & (intptr_t)data) + sizeof(struct tld_data_u);
 	map_val.meta = TLD_READ_ONCE(tld_meta_p);
 
 	err = bpf_map_update_elem(map_fd, &tid_fd, &map_val, 0);
 	if (err) {
-		free(data_alloc);
+		free(data);
 		goto out;
 	}
 
 	tld_data_p = data;
-	tld_data_alloc_p = data_alloc;
 #ifdef TLD_FREE_DATA_ON_THREAD_EXIT
 	pthread_setspecific(tld_pthread_key, (void *)1);
 #endif
@@ -375,9 +360,8 @@ static void *tld_get_data(int map_fd, tld_key_t key)
 __attribute__((unused))
 static void tld_free(void)
 {
-	if (tld_data_alloc_p) {
-		free(tld_data_alloc_p);
-		tld_data_alloc_p = NULL;
+	if (tld_data_p) {
+		free(tld_data_p);
 		tld_data_p = NULL;
 	}
 }
Signature · 1 line
2.52.0
#7 lore raw

Re: [PATCH bpf-next v1 2/3] selftests/bpf: Simplify task_local_data memory allocation

Quoted 15 lines · Amery Hung

Simplify data allocation by always using aligned_alloc() and passing size_pot, size rounded up to the closest power of two to alignment.

Currently, aligned_alloc(page_size, size) is only intended to be used with memory allocators that can fulfill the request without rounding size up to page_size to conserve memory. This is enabled by defining TLD_DATA_USE_ALIGNED_ALLOC. The reason to align to page_size is due to the limitation of UPTR where only a page can be pinned to the kernel. Otherwise, malloc(size * 2) is used to allocate memory for data.

However, we don't need to call aligned_alloc(page_size, size) to get a contiguous memory of size bytes within a page. aligned_alloc(size_pot, ...) will also do the trick. Therefore, just use aligned_alloc(size_pot, ...) universally.

Quoted 7 lines

As for the size argument, create a new option, TLD_DONT_ROUND_UP_DATA_SIZE, to specify not rounding up the size. This preserves the current TLD_DATA_USE_ALIGNED_ALLOC behavior, allowing memory allocators with low overhead aligned_alloc() to not waste memory. To enable this, users need to make sure it is not an undefined behavior for the memory allocator to have size not being an integral multiple of alignment.

Why not simplify this further and just mmap() a page?

data = mmap(NULL, PAGE_SIZE, PROT_READ | PROT_WRITE,

              MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

That gives you a page-aligned, page-sized buffer with no ambiguity about alignment, page boundary crossings, or aligned_alloc() POSIX compliance. munmap() on cleanup instead of free().

The whole power-of-two rounding and TLD_DONT_ROUND_UP_DATA_SIZE option adds complexity that's hard to justify for selftest infrastructure. How does a user decide when to define/undefine TLD_DONT_ROUND_UP? This is a selftest library -- the common case should just work with the simplest possible approach

Quoted 143 lines

Compared to the current implementation, !TLD_DATA_USE_ALIGNED_ALLOC used to always waste size-byte of memory due to malloc(size * 2). Now the worst case becomes size - 1 and the best case is 0 when the size is already a power of two.

---
 .../bpf/prog_tests/task_local_data.h          | 60 +++++++------------
 1 file changed, 22 insertions(+), 38 deletions(-)
tools/testing/selftests/bpf/prog_tests/task_local_data.h +22 -38
index a52d8b549425..366a6739c086 100644
@@ -50,16 +50,13 @@
  *   TLD_MAX_DATA_CNT.
  *
  *
- *   TLD_DATA_USE_ALIGNED_ALLOC - Always use aligned_alloc() instead of malloc()
+ *   TLD_DONT_ROUND_UP_DATA_SIZE - Don't round up memory size allocated for data if
+ *   the memory allocator has low overhead aligned_alloc() implementation.
  *
- *   When allocating the memory for storing TLDs, we need to make sure there is a memory
- *   region of the X bytes within a page. This is due to the limit posed by UPTR: memory
- *   pinned to the kernel cannot exceed a page nor can it cross the page boundary. The
- *   library normally calls malloc(2*X) given X bytes of total TLDs, and only uses
- *   aligned_alloc(PAGE_SIZE, X) when X >= PAGE_SIZE / 2. This is to reduce memory wastage
- *   as not all memory allocator can use the exact amount of memory requested to fulfill
- *   aligned_alloc(). For example, some may round the size up to the alignment. Enable the
- *   option to always use aligned_alloc() if the implementation has low memory overhead.
+ *   For some memory allocators, when calling aligned_alloc(alignment, size), size
+ *   does not need to be an integral multiple of alignment and it can be fulfilled
+ *   without using round_up(size, alignment) bytes of memory. Enable this option to
+ *   reduce memory usage.
  */
 
 #define TLD_PAGE_SIZE getpagesize()
@@ -68,6 +65,8 @@
 #define TLD_ROUND_MASK(x, y) ((__typeof__(x))((y) - 1))
 #define TLD_ROUND_UP(x, y) ((((x) - 1) | TLD_ROUND_MASK(x, y)) + 1)
 
+#define TLD_ROUND_UP_POWER_OF_TWO(x) (1UL << (sizeof(x) * 8 - __builtin_clzl(x - 1)))
+
 #define TLD_READ_ONCE(x) (*(volatile typeof(x) *)&(x))
 
 #ifndef TLD_DYN_DATA_SIZE
@@ -111,7 +110,6 @@ struct tld_map_value {
 
 struct tld_meta_u * _Atomic tld_meta_p __attribute__((weak));
 __thread struct tld_data_u *tld_data_p __attribute__((weak));
-__thread void *tld_data_alloc_p __attribute__((weak));
 
 #ifdef TLD_FREE_DATA_ON_THREAD_EXIT
 pthread_key_t tld_pthread_key __attribute__((weak));
@@ -153,12 +151,10 @@ static int __tld_init_meta_p(void)
 
 static int __tld_init_data_p(int map_fd)
 {
-	bool use_aligned_alloc = false;
 	struct tld_map_value map_val;
 	struct tld_data_u *data;
-	void *data_alloc = NULL;
 	int err, tid_fd = -1;
-	size_t size;
+	size_t size, size_pot;
 
 	tid_fd = syscall(SYS_pidfd_open, sys_gettid(), O_EXCL);
 	if (tid_fd < 0) {
@@ -166,48 +162,37 @@ static int __tld_init_data_p(int map_fd)
 		goto out;
 	}
 
-#ifdef TLD_DATA_USE_ALIGNED_ALLOC
-	use_aligned_alloc = true;
-#endif
-
 	/*
 	 * tld_meta_p->size = TLD_DYN_DATA_SIZE +
 	 *          total size of TLDs defined via TLD_DEFINE_KEY()
 	 */
 	size = tld_meta_p->size + sizeof(struct tld_data_u);
-	data_alloc = (use_aligned_alloc || size * 2 >= TLD_PAGE_SIZE) ?
-		aligned_alloc(TLD_PAGE_SIZE, size) :
-		malloc(size * 2);
-	if (!data_alloc) {
+	size_pot = TLD_ROUND_UP_POWER_OF_TWO(size);
+#ifdef TLD_DONT_ROUND_UP_DATA_SIZE
+	data = (struct tld_data_u *)aligned_alloc(size_pot, size);
+#else
+	data = (struct tld_data_u *)aligned_alloc(size_pot, size_pot);
+#endif
+	if (!data) {
 		err = -ENOMEM;
 		goto out;
 	}
 
 	/*
 	 * Always pass a page-aligned address to UPTR since the size of tld_map_value::data
-	 * is a page in BTF. If data_alloc spans across two pages, use the page that contains large
-	 * enough memory.
+	 * is a page in BTF.
 	 */
-	if (TLD_PAGE_SIZE - (~TLD_PAGE_MASK & (intptr_t)data_alloc) >= tld_meta_p->size) {
-		map_val.data = (void *)(TLD_PAGE_MASK & (intptr_t)data_alloc);
-		data = data_alloc;
-		data->start = (~TLD_PAGE_MASK & (intptr_t)data_alloc) +
-			      offsetof(struct tld_data_u, data);
-	} else {
-		map_val.data = (void *)(TLD_ROUND_UP((intptr_t)data_alloc, TLD_PAGE_SIZE));
-		data = (void *)(TLD_ROUND_UP((intptr_t)data_alloc, TLD_PAGE_SIZE));
-		data->start = offsetof(struct tld_data_u, data);
-	}
+	map_val.data = (void *)(TLD_PAGE_MASK & (intptr_t)data);
+	data->start = (~TLD_PAGE_MASK & (intptr_t)data) + sizeof(struct tld_data_u);
 	map_val.meta = TLD_READ_ONCE(tld_meta_p);
 
 	err = bpf_map_update_elem(map_fd, &tid_fd, &map_val, 0);
 	if (err) {
-		free(data_alloc);
+		free(data);
 		goto out;
 	}
 
 	tld_data_p = data;
-	tld_data_alloc_p = data_alloc;
 #ifdef TLD_FREE_DATA_ON_THREAD_EXIT
 	pthread_setspecific(tld_pthread_key, (void *)1);
 #endif
@@ -375,9 +360,8 @@ static void *tld_get_data(int map_fd, tld_key_t key)
 __attribute__((unused))
 static void tld_free(void)
 {
-	if (tld_data_alloc_p) {
-		free(tld_data_alloc_p);
-		tld_data_alloc_p = NULL;
+	if (tld_data_p) {
+		free(tld_data_p);
 		tld_data_p = NULL;
 	}
 }
Signature · 1 line
2.52.0
author
#8 lore raw

Re: [PATCH bpf-next v1 2/3] selftests/bpf: Simplify task_local_data memory allocation

Quoted 34 lines · Mykyta Yatsenko
Quoted 15 lines · Amery Hung

Simplify data allocation by always using aligned_alloc() and passing size_pot, size rounded up to the closest power of two to alignment.

Currently, aligned_alloc(page_size, size) is only intended to be used with memory allocators that can fulfill the request without rounding size up to page_size to conserve memory. This is enabled by defining TLD_DATA_USE_ALIGNED_ALLOC. The reason to align to page_size is due to the limitation of UPTR where only a page can be pinned to the kernel. Otherwise, malloc(size * 2) is used to allocate memory for data.

However, we don't need to call aligned_alloc(page_size, size) to get a contiguous memory of size bytes within a page. aligned_alloc(size_pot, ...) will also do the trick. Therefore, just use aligned_alloc(size_pot, ...) universally.

Quoted 7 lines

As for the size argument, create a new option, TLD_DONT_ROUND_UP_DATA_SIZE, to specify not rounding up the size. This preserves the current TLD_DATA_USE_ALIGNED_ALLOC behavior, allowing memory allocators with low overhead aligned_alloc() to not waste memory. To enable this, users need to make sure it is not an undefined behavior for the memory allocator to have size not being an integral multiple of alignment.

Why not simplify this further and just mmap() a page?

data = mmap(NULL, PAGE_SIZE, PROT_READ | PROT_WRITE,

              MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

That gives you a page-aligned, page-sized buffer with no ambiguity about alignment, page boundary crossings, or aligned_alloc() POSIX compliance. munmap() on cleanup instead of free().

Quoted 5 lines

The whole power-of-two rounding and TLD_DONT_ROUND_UP_DATA_SIZE option adds complexity that's hard to justify for selftest infrastructure. How does a user decide when to define/undefine TLD_DONT_ROUND_UP? This is a selftest library -- the common case should just work with the simplest possible approach

This library, while residing in selftest, is designed to be used in production projects. sched_ext is in the process of adopting it. Therefore, simplicity is traded for efficiency.

data here is allocated for every thread that calls tld_get_data(). So if we mmap a page for every thread (which could be in 100k order), it is going to waste a significant amount of memory.

Quoted 6 lines
Quoted 6 lines

Compared to the current implementation, !TLD_DATA_USE_ALIGNED_ALLOC used to always waste size-byte of memory due to malloc(size * 2). Now the worst case becomes size - 1 and the best case is 0 when the size is already a power of two.

#9 lore raw

Re: [PATCH bpf-next v1 2/3] selftests/bpf: Simplify task_local_data memory allocation

Quoted 42 lines · Amery Hung
Quoted 34 lines · Mykyta Yatsenko
Quoted 15 lines · Amery Hung

Simplify data allocation by always using aligned_alloc() and passing size_pot, size rounded up to the closest power of two to alignment.

Currently, aligned_alloc(page_size, size) is only intended to be used with memory allocators that can fulfill the request without rounding size up to page_size to conserve memory. This is enabled by defining TLD_DATA_USE_ALIGNED_ALLOC. The reason to align to page_size is due to the limitation of UPTR where only a page can be pinned to the kernel. Otherwise, malloc(size * 2) is used to allocate memory for data.

However, we don't need to call aligned_alloc(page_size, size) to get a contiguous memory of size bytes within a page. aligned_alloc(size_pot, ...) will also do the trick. Therefore, just use aligned_alloc(size_pot, ...) universally.

Quoted 7 lines

As for the size argument, create a new option, TLD_DONT_ROUND_UP_DATA_SIZE, to specify not rounding up the size. This preserves the current TLD_DATA_USE_ALIGNED_ALLOC behavior, allowing memory allocators with low overhead aligned_alloc() to not waste memory. To enable this, users need to make sure it is not an undefined behavior for the memory allocator to have size not being an integral multiple of alignment.

Why not simplify this further and just mmap() a page?

data = mmap(NULL, PAGE_SIZE, PROT_READ | PROT_WRITE,

              MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

That gives you a page-aligned, page-sized buffer with no ambiguity about alignment, page boundary crossings, or aligned_alloc() POSIX compliance. munmap() on cleanup instead of free().

Quoted 5 lines

The whole power-of-two rounding and TLD_DONT_ROUND_UP_DATA_SIZE option adds complexity that's hard to justify for selftest infrastructure. How does a user decide when to define/undefine TLD_DONT_ROUND_UP? This is a selftest library -- the common case should just work with the simplest possible approach

Quoted 8 lines

This library, while residing in selftest, is designed to be used in production projects. sched_ext is in the process of adopting it. Therefore, simplicity is traded for efficiency.

data here is allocated for every thread that calls tld_get_data(). So if we mmap a page for every thread (which could be in 100k order), it is going to waste a significant amount of memory.

Thanks for providing this context, it makes sense now.

Quoted 6 lines
Quoted 6 lines
Quoted 6 lines

Compared to the current implementation, !TLD_DATA_USE_ALIGNED_ALLOC used to always waste size-byte of memory due to malloc(size * 2). Now the worst case becomes size - 1 and the best case is 0 when the size is already a power of two.

author
#10 lore raw

PATCH 3/3 selftests/bpf: Make sure TLD_DEFINE_KEY runs first

In reply to Amery Hung

Without specifying constructor priority of the hidden constructor function defined by TLD_DEFINE_KEY, __tld_create_key(..., dyn_data = false) may run after tld_get_data() called from other constructors. Threads calling tld_get_data() before __tld_create_key(..., dyn_data = false) will not allocate enough memory for all TLDs and later result in OOB access. Therefore, set it to the lowest value available to users. Note that lower means higher priority and 0-100 is reserved to the compiler.

---
 tools/testing/selftests/bpf/prog_tests/task_local_data.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
tools/testing/selftests/bpf/prog_tests/task_local_data.h +1 -1
index 366a6739c086..e242c455ddae 100644
@@ -278,7 +278,7 @@ static tld_key_t __tld_create_key(const char *name, size_t size, bool dyn_data)
 #define TLD_DEFINE_KEY(key, name, size)			\
 tld_key_t key;						\
 							\
-__attribute__((constructor))				\
+__attribute__((constructor(101)))			\
 void __tld_define_key_##key(void)			\
 {							\
 	key = __tld_create_key(name, size, false);	\
Signature · 1 line
2.52.0
Acked-by on v1 3/3
#11 lore raw

Re: [PATCH bpf-next v1 3/3] selftests/bpf: Make sure TLD_DEFINE_KEY runs first

Quoted 29 lines · Amery Hung

Without specifying constructor priority of the hidden constructor function defined by TLD_DEFINE_KEY, __tld_create_key(..., dyn_data = false) may run after tld_get_data() called from other constructors. Threads calling tld_get_data() before __tld_create_key(..., dyn_data = false) will not allocate enough memory for all TLDs and later result in OOB access. Therefore, set it to the lowest value available to users. Note that lower means higher priority and 0-100 is reserved to the compiler.

---
 tools/testing/selftests/bpf/prog_tests/task_local_data.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
tools/testing/selftests/bpf/prog_tests/task_local_data.h +1 -1
index 366a6739c086..e242c455ddae 100644
@@ -278,7 +278,7 @@ static tld_key_t __tld_create_key(const char *name, size_t size, bool dyn_data)
 #define TLD_DEFINE_KEY(key, name, size)			\
 tld_key_t key;						\
 							\
-__attribute__((constructor))				\
+__attribute__((constructor(101)))			\
 void __tld_define_key_##key(void)			\
 {							\
 	key = __tld_create_key(name, size, false);	\
Signature · 1 line
2.52.0