Copilot commented on code in PR #13170:
URL: https://github.com/apache/trafficserver/pull/13170#discussion_r3276943044
##########
src/tscore/ink_queue.cc:
##########
@@ -200,15 +223,21 @@ ink_freelist_create(const char *name, uint32_t type_size,
uint32_t chunk_size, u
return f;
}
-#define ADDRESS_OF_NEXT(x, offset) ((void **)((char *)x + offset))
+static void **
+to_voidp_p(void *x, std::uint64_t offset)
+{
+ unsigned char *addr{reinterpret_cast<unsigned char *>(x) + offset};
+ ink_assert(is_addr_aligned(x, alignof(void **)));
Review Comment:
to_voidp_p computes addr = x + offset but asserts alignment of x rather than
addr, so it can return an unaligned void** when offset is not suitably aligned.
The assertion should validate the computed addr meets the alignment required
for void* (and typically should use alignof(void*) rather than alignof(void**)).
##########
src/tscore/ink_queue.cc:
##########
@@ -517,76 +577,96 @@ ink_freelists_dump(FILE *f)
void
ink_atomiclist_init(InkAtomicList *l, const char *name, uint32_t
offset_to_next)
{
+ // The pointers we push onto the atomiclist will also need to be aligned. If
+ // the offset is not aligned, then it is not possible for the caller to
+ // determine a consistent, safe alignment for the object the head_p objects
+ // are subobjects of.
+ ink_release_assert(offset_to_next % alignof(head_p) == 0);
+
l->name = name;
l->offset = offset_to_next;
- SET_FREELIST_POINTER_VERSION(l->head, FROM_PTR(0), 0);
+ head_p empty_head;
+ SET_FREELIST_POINTER_VERSION(empty_head, FROM_PTR(nullptr), 0);
+ l->head.store(empty_head);
}
void *
ink_atomiclist_pop(InkAtomicList *l)
{
head_p item;
head_p next;
- int result = 0;
+ bool result = 0;
+
+ std::lock_guard guard{l->m};
+
+ item = l->head.load();
do {
- INK_QUEUE_LD(item, l->head);
if (TO_PTR(FREELIST_POINTER(item)) == nullptr) {
return nullptr;
}
- SET_FREELIST_POINTER_VERSION(next,
*ADDRESS_OF_NEXT(TO_PTR(FREELIST_POINTER(item)), l->offset),
FREELIST_VERSION(item) + 1);
- result = ink_atomic_cas(&l->head.data, item.data, next.data);
- } while (result == 0);
- {
- void *ret = TO_PTR(FREELIST_POINTER(item));
- *ADDRESS_OF_NEXT(ret, l->offset) = nullptr;
- return ret;
- }
+ void **next_ptr = reinterpret_cast<void **>(reinterpret_cast<unsigned char
*>(TO_PTR(FREELIST_POINTER(item))) + l->offset);
+ SET_FREELIST_POINTER_VERSION(next, *next_ptr, FREELIST_VERSION(item) + 1);
+ result = l->head.compare_exchange_weak(item, next);
+ } while (result == false);
+
+ void *ret = TO_PTR(FREELIST_POINTER(item));
+ void **ret_ = reinterpret_cast<void **>(reinterpret_cast<unsigned char
*>(ret) + l->offset);
+ *ret_ = nullptr;
+ return ret;
}
void *
ink_atomiclist_popall(InkAtomicList *l)
{
head_p item;
head_p next;
- int result = 0;
+ bool result = false;
+
+ item = l->head.load();
do {
- INK_QUEUE_LD(item, l->head);
if (TO_PTR(FREELIST_POINTER(item)) == nullptr) {
return nullptr;
}
SET_FREELIST_POINTER_VERSION(next, FROM_PTR(nullptr),
FREELIST_VERSION(item) + 1);
- result = ink_atomic_cas(&l->head.data, item.data, next.data);
- } while (result == 0);
- {
- void *ret = TO_PTR(FREELIST_POINTER(item));
- void *e = ret;
- /* fixup forward pointers */
- while (e) {
- void *n = TO_PTR(*ADDRESS_OF_NEXT(e, l->offset));
- *ADDRESS_OF_NEXT(e, l->offset) = n;
- e = n;
- }
- return ret;
+ result = l->head.compare_exchange_weak(item, next);
+ } while (result == false);
+
+ void *ret = TO_PTR(FREELIST_POINTER(item));
+ void *e = ret;
+ /* fixup forward pointers */
+ while (e) {
+ void **e_ = to_voidp_p(e, l->offset);
+ void *n = TO_PTR(*e_);
+ *e_ = n;
+ e = n;
}
+
+ ink_assert(is_addr_aligned(ret, alignof(head_p)));
Review Comment:
ink_atomiclist_popall asserts ret is aligned to alignof(head_p). The
returned pointer is an item allocated by the caller, and only needs to satisfy
the caller's object alignment (and the next-pointer field alignment). If head_p
becomes 16-byte aligned (TS_HAS_128BIT_CAS), this assertion can fire even when
ret is correctly void*-aligned. The alignment check should be against the
actual requirement (typically alignof(void*) and/or the list's expected node
alignment), not alignof(head_p).
##########
src/tscore/ink_queue.cc:
##########
@@ -517,76 +577,96 @@ ink_freelists_dump(FILE *f)
void
ink_atomiclist_init(InkAtomicList *l, const char *name, uint32_t
offset_to_next)
{
+ // The pointers we push onto the atomiclist will also need to be aligned. If
+ // the offset is not aligned, then it is not possible for the caller to
+ // determine a consistent, safe alignment for the object the head_p objects
+ // are subobjects of.
+ ink_release_assert(offset_to_next % alignof(head_p) == 0);
+
l->name = name;
l->offset = offset_to_next;
- SET_FREELIST_POINTER_VERSION(l->head, FROM_PTR(0), 0);
+ head_p empty_head;
+ SET_FREELIST_POINTER_VERSION(empty_head, FROM_PTR(nullptr), 0);
+ l->head.store(empty_head);
}
void *
ink_atomiclist_pop(InkAtomicList *l)
{
head_p item;
head_p next;
- int result = 0;
+ bool result = 0;
+
+ std::lock_guard guard{l->m};
+
+ item = l->head.load();
do {
- INK_QUEUE_LD(item, l->head);
if (TO_PTR(FREELIST_POINTER(item)) == nullptr) {
return nullptr;
}
- SET_FREELIST_POINTER_VERSION(next,
*ADDRESS_OF_NEXT(TO_PTR(FREELIST_POINTER(item)), l->offset),
FREELIST_VERSION(item) + 1);
- result = ink_atomic_cas(&l->head.data, item.data, next.data);
- } while (result == 0);
- {
- void *ret = TO_PTR(FREELIST_POINTER(item));
- *ADDRESS_OF_NEXT(ret, l->offset) = nullptr;
- return ret;
- }
+ void **next_ptr = reinterpret_cast<void **>(reinterpret_cast<unsigned char
*>(TO_PTR(FREELIST_POINTER(item))) + l->offset);
+ SET_FREELIST_POINTER_VERSION(next, *next_ptr, FREELIST_VERSION(item) + 1);
+ result = l->head.compare_exchange_weak(item, next);
+ } while (result == false);
+
+ void *ret = TO_PTR(FREELIST_POINTER(item));
+ void **ret_ = reinterpret_cast<void **>(reinterpret_cast<unsigned char
*>(ret) + l->offset);
+ *ret_ = nullptr;
+ return ret;
}
void *
ink_atomiclist_popall(InkAtomicList *l)
{
head_p item;
head_p next;
- int result = 0;
+ bool result = false;
+
+ item = l->head.load();
do {
- INK_QUEUE_LD(item, l->head);
if (TO_PTR(FREELIST_POINTER(item)) == nullptr) {
return nullptr;
}
SET_FREELIST_POINTER_VERSION(next, FROM_PTR(nullptr),
FREELIST_VERSION(item) + 1);
- result = ink_atomic_cas(&l->head.data, item.data, next.data);
- } while (result == 0);
- {
- void *ret = TO_PTR(FREELIST_POINTER(item));
- void *e = ret;
- /* fixup forward pointers */
- while (e) {
- void *n = TO_PTR(*ADDRESS_OF_NEXT(e, l->offset));
- *ADDRESS_OF_NEXT(e, l->offset) = n;
- e = n;
- }
- return ret;
+ result = l->head.compare_exchange_weak(item, next);
+ } while (result == false);
Review Comment:
ink_atomiclist_popall is not protected by the new InkAtomicList mutex,
unlike ink_atomiclist_pop. If the intent is to provide mutual exclusion among
pop operations to avoid UB (per PR description), popall should also take the
mutex; otherwise concurrent pop/popall can still race on the head node's next
pointer reads.
##########
src/tscore/unit_tests/test_ink_queue.cc:
##########
@@ -0,0 +1,220 @@
+/** @file
+
+ Freelist and Atomiclist tests
+
+ @section license License
+
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+*/
+
+#define CATCH_CONFIG_ENABLE_BENCHMARKING
+#include <catch2/catch_all.hpp>
+
+#include <tscore/ink_queue.h>
+
+#include <atomic>
+#include <cstddef>
+#include <cstdint>
+#include <thread>
+#include <vector>
+
+TEST_CASE("Freelist", "[freelist]")
+{
+ // There is no error reporting for this routine. The allocation
+ // is assumed to never fail.
+ InkFreeList *f{ink_freelist_create("test#1", sizeof(std::int32_t), 1,
alignof(std::int32_t))};
+
+ SECTION("Freelist allocates aligned pointers")
+ {
+ void *addr{ink_freelist_new(f)};
+
+ CHECK(!(reinterpret_cast<std::uintptr_t>(addr) & (alignof(std::int32_t) -
1)));
+
+ ink_freelist_free(f, addr);
+ }
+
+ SECTION("Two new freelist allocations")
+ {
+ std::int32_t *a{new (ink_freelist_new(f)) std::int32_t{1}};
+ std::int32_t *b{new (ink_freelist_new(f)) std::int32_t{2}};
+
+ CHECK(((*a == 1) && (*b == 2)));
+
+ ink_freelist_free(f, a);
+ ink_freelist_free(f, b);
+ }
+
+ SECTION("Freelist stack behavior")
+ {
+ void *a{ink_freelist_new(f)};
+ void *b{ink_freelist_new(f)};
+
+ ink_freelist_free(f, a);
+ ink_freelist_free(f, b);
+
+ void *x{ink_freelist_new(f)};
+ void *y{ink_freelist_new(f)};
+
+ CHECK((a == y && b == x));
+
+ ink_freelist_free(f, a);
+ ink_freelist_free(f, b);
+ }
+}
+
+TEST_CASE("Empty atomic list", "[atomiclist]")
+{
+ InkAtomicList l;
+ ink_atomiclist_init(&l, "test#1", 0);
+
+ CHECK(nullptr == ink_atomiclist_pop(&l));
+}
+
+TEST_CASE("Popall from empty atomic list", "[atomiclist]")
+{
+ InkAtomicList l;
+ ink_atomiclist_init(&l, "test#1", 0);
+
+ CHECK(nullptr == ink_atomiclist_popall(&l));
+}
+
+TEST_CASE("Atomic list", "[atomiclist]")
+{
+ struct test_type {
+ std::int32_t i;
+ void *next;
+ };
+
+ InkAtomicList l;
+ ink_atomiclist_init(&l, "test#1", offsetof(test_type, next));
+
+ // We allocate memory this way to ensure proper alignment for atomiclist.
+ InkFreeList *f{ink_freelist_create("test#1", sizeof(test_type), 1,
alignof(test_type))};
+
+ SECTION("Atomic list becomes empty after push and pop")
+ {
+ ink_atomiclist_push(&l, ink_freelist_new(f));
+ void *a{ink_atomiclist_pop(&l)};
+
+ CHECK(nullptr == ink_atomiclist_pop(&l));
+
+ ink_freelist_free(f, a);
+ }
+
+ SECTION("Atomic list stack behavior")
+ {
+ void *a{ink_freelist_new(f)};
+ void *b{ink_freelist_new(f)};
+
+ ink_atomiclist_push(&l, a);
+ ink_atomiclist_push(&l, b);
+
+ void *x{ink_atomiclist_pop(&l)};
+ void *y{ink_atomiclist_pop(&l)};
+
+ CHECK((a == y && b == x));
+
+ ink_freelist_free(f, a);
+ ink_freelist_free(f, b);
+ }
+
+ SECTION("Atomic list remove head")
+ {
+ void *a{ink_freelist_new(f)};
+ void *b{ink_freelist_new(f)};
+
+ ink_atomiclist_push(&l, a);
+ ink_atomiclist_push(&l, b);
+
+ CHECK(b == ink_atomiclist_remove(&l, b));
+
+ ink_freelist_free(f, a);
+ ink_freelist_free(f, b);
+ }
+
+ SECTION("Atomic list remove tail")
+ {
+ void *a{ink_freelist_new(f)};
+ void *b{ink_freelist_new(f)};
+
+ ink_atomiclist_push(&l, a);
+ ink_atomiclist_push(&l, b);
+
+ CHECK(a == ink_atomiclist_remove(&l, a));
+
+ ink_freelist_free(f, a);
+ ink_freelist_free(f, b);
+ }
+
+ SECTION("Atomic list becomes empty after popall")
+ {
+ void *a{ink_freelist_new(f)};
+ void *b{ink_freelist_new(f)};
+
+ ink_atomiclist_push(&l, a);
+ ink_atomiclist_push(&l, b);
+
+ ink_atomiclist_popall(&l);
+ CHECK(nullptr == ink_atomiclist_popall(&l));
+
+ ink_freelist_free(f, a);
+ ink_freelist_free(f, b);
+ }
+
+ SECTION("Atomic list popall behavior")
+ {
+ void *a{ink_freelist_new(f)};
+ void *b{ink_freelist_new(f)};
+
+ ink_atomiclist_push(&l, a);
+ ink_atomiclist_push(&l, b);
+
+ void *head{ink_atomiclist_popall(&l)};
+ void **head_{reinterpret_cast<void **>(reinterpret_cast<unsigned char
*>(head) + l.offset)};
+ void *tail{FREELIST_POINTER(*head_)};
+
+ CHECK(((head == b) && (tail == a)));
+
+ ink_freelist_free(f, a);
+ ink_freelist_free(f, b);
+ }
+}
+
+TEST_CASE("Freelist benchmarks", "[freelist][bench]")
+{
+ BENCHMARK_ADVANCED("Single threaded alloc")(Catch::Benchmark::Chronometer
meter)
+ {
+ InkFreeList *f{ink_freelist_create("test#1", sizeof(std::int32_t), 4,
alignof(std::int32_t))};
+
+ ink_freelist_new(f);
+
+ meter.measure([&]() { return ink_freelist_new(f); });
+ };
+
+ BENCHMARK_ADVANCED("Single threaded free")(Catch::Benchmark::Chronometer
meter)
+ {
+ InkFreeList *f{ink_freelist_create("test#1", sizeof(std::int32_t), 4,
alignof(std::int32_t))};
+
+ std::vector<void *> ptrs;
+ ptrs.resize(meter.runs());
+ for (auto &x : ptrs) {
+ x = ink_freelist_new(f);
+ }
+
+ meter.measure([&](int i) { return ink_freelist_free(f, ptrs[i]); });
+ };
+}
Review Comment:
The new `TEST_CASE("Freelist benchmarks", ...)` uses Catch2
BENCHMARK_ADVANCED. Catch2 runs benchmarks by default unless the test runner is
invoked with `--skip-benchmarks`; `test_tscore` is currently registered without
that flag, so this will add significant runtime to the regular unit-test suite.
Consider gating these benchmarks behind an opt-in build flag, moving them to a
dedicated microbench target, or updating the test invocation to skip benchmarks
in CI/unit-test runs.
##########
include/tscore/ink_queue.h:
##########
@@ -213,9 +236,10 @@ void ink_freelists_snap_baseline();
struct InkAtomicList {
InkAtomicList() {}
- head_p head{};
- const char *name = nullptr;
- uint32_t offset = 0;
+ std::mutex m;
+ std::atomic<head_p> head{};
+ const char *name = nullptr;
+ uint32_t offset = 0;
};
Review Comment:
InkAtomicList::head is now std::atomic<head_p>, but there are existing
non-macro call sites that access `al.head` as if it were a plain head_p (e.g.,
AtomicSLL::head() in include/tscore/List.h currently does
`FREELIST_POINTER(al.head)`). This type change requires updating those call
sites to use `.head.load(...)` (or providing a helper accessor) or the build
will fail due to passing std::atomic to FREELIST_POINTER/TO_PTR.
##########
src/tscore/ink_queue.cc:
##########
@@ -517,76 +577,96 @@ ink_freelists_dump(FILE *f)
void
ink_atomiclist_init(InkAtomicList *l, const char *name, uint32_t
offset_to_next)
{
+ // The pointers we push onto the atomiclist will also need to be aligned. If
+ // the offset is not aligned, then it is not possible for the caller to
+ // determine a consistent, safe alignment for the object the head_p objects
+ // are subobjects of.
+ ink_release_assert(offset_to_next % alignof(head_p) == 0);
+
l->name = name;
l->offset = offset_to_next;
- SET_FREELIST_POINTER_VERSION(l->head, FROM_PTR(0), 0);
+ head_p empty_head;
+ SET_FREELIST_POINTER_VERSION(empty_head, FROM_PTR(nullptr), 0);
+ l->head.store(empty_head);
Review Comment:
ink_atomiclist_init now asserts offset_to_next % alignof(head_p) == 0, but
the offset is used to access a void* next field, not a head_p. On platforms
where head_p has stricter alignment (e.g., 16-byte when TS_HAS_128BIT_CAS),
this will spuriously abort for common structures where the next pointer is only
void*-aligned (e.g., ProtectedQueue/Event and AtomicSLL). Consider validating
against alignof(void*) (and/or validate the alignment of item+offset at push
time) instead.
##########
ci/asan_leak_suppression/unit_tests.txt:
##########
@@ -2,3 +2,8 @@
# not destroyed because it holds a reference to a stack-allocated
# TestRefCountObj whose free() override calls exit(1).
leak:test_http_hdr_print_and_copy_aux
+
+# on 64-bit architectures, freelist pointers are stored in a special bitwise
+# format, so LSan cannot find link pointers. It will erroneously determine
+# that the list tail is not reachable.
+leak:freelist_new
Review Comment:
LSan suppression `leak:freelist_new` is very broad: any real leak
originating from freelist allocations in unit tests will also be suppressed. If
possible, narrow the suppression (e.g., suppress the specific test binary/stack
frame that is a known false positive, or suppress the specific
allocator/backing allocation function) so leak detection remains useful for
other freelist-backed allocations.
##########
src/tscore/ink_queue.cc:
##########
@@ -517,76 +577,96 @@ ink_freelists_dump(FILE *f)
void
ink_atomiclist_init(InkAtomicList *l, const char *name, uint32_t
offset_to_next)
{
+ // The pointers we push onto the atomiclist will also need to be aligned. If
+ // the offset is not aligned, then it is not possible for the caller to
+ // determine a consistent, safe alignment for the object the head_p objects
+ // are subobjects of.
+ ink_release_assert(offset_to_next % alignof(head_p) == 0);
+
l->name = name;
l->offset = offset_to_next;
- SET_FREELIST_POINTER_VERSION(l->head, FROM_PTR(0), 0);
+ head_p empty_head;
+ SET_FREELIST_POINTER_VERSION(empty_head, FROM_PTR(nullptr), 0);
+ l->head.store(empty_head);
}
void *
ink_atomiclist_pop(InkAtomicList *l)
{
head_p item;
head_p next;
- int result = 0;
+ bool result = 0;
+
+ std::lock_guard guard{l->m};
+
+ item = l->head.load();
do {
- INK_QUEUE_LD(item, l->head);
if (TO_PTR(FREELIST_POINTER(item)) == nullptr) {
return nullptr;
}
- SET_FREELIST_POINTER_VERSION(next,
*ADDRESS_OF_NEXT(TO_PTR(FREELIST_POINTER(item)), l->offset),
FREELIST_VERSION(item) + 1);
- result = ink_atomic_cas(&l->head.data, item.data, next.data);
- } while (result == 0);
- {
- void *ret = TO_PTR(FREELIST_POINTER(item));
- *ADDRESS_OF_NEXT(ret, l->offset) = nullptr;
- return ret;
- }
+ void **next_ptr = reinterpret_cast<void **>(reinterpret_cast<unsigned char
*>(TO_PTR(FREELIST_POINTER(item))) + l->offset);
+ SET_FREELIST_POINTER_VERSION(next, *next_ptr, FREELIST_VERSION(item) + 1);
+ result = l->head.compare_exchange_weak(item, next);
+ } while (result == false);
+
+ void *ret = TO_PTR(FREELIST_POINTER(item));
+ void **ret_ = reinterpret_cast<void **>(reinterpret_cast<unsigned char
*>(ret) + l->offset);
+ *ret_ = nullptr;
+ return ret;
}
void *
ink_atomiclist_popall(InkAtomicList *l)
{
head_p item;
head_p next;
- int result = 0;
+ bool result = false;
+
+ item = l->head.load();
do {
- INK_QUEUE_LD(item, l->head);
if (TO_PTR(FREELIST_POINTER(item)) == nullptr) {
return nullptr;
}
SET_FREELIST_POINTER_VERSION(next, FROM_PTR(nullptr),
FREELIST_VERSION(item) + 1);
- result = ink_atomic_cas(&l->head.data, item.data, next.data);
- } while (result == 0);
- {
- void *ret = TO_PTR(FREELIST_POINTER(item));
- void *e = ret;
- /* fixup forward pointers */
- while (e) {
- void *n = TO_PTR(*ADDRESS_OF_NEXT(e, l->offset));
- *ADDRESS_OF_NEXT(e, l->offset) = n;
- e = n;
- }
- return ret;
+ result = l->head.compare_exchange_weak(item, next);
+ } while (result == false);
+
+ void *ret = TO_PTR(FREELIST_POINTER(item));
+ void *e = ret;
+ /* fixup forward pointers */
+ while (e) {
+ void **e_ = to_voidp_p(e, l->offset);
+ void *n = TO_PTR(*e_);
+ *e_ = n;
+ e = n;
}
+
+ ink_assert(is_addr_aligned(ret, alignof(head_p)));
+
+ return ret;
}
void *
ink_atomiclist_push(InkAtomicList *l, void *item)
{
- void **adr_of_next = ADDRESS_OF_NEXT(item, l->offset);
+ ink_release_assert(is_addr_aligned(item, alignof(void *)));
+
head_p head;
head_p item_pair;
- int result = 0;
+ void **recovered_item;
+ bool result = false;
void *h = nullptr;
+
+ head = l->head.load();
do {
- INK_QUEUE_LD(head, l->head);
- h = FREELIST_POINTER(head);
- *adr_of_next = h;
+ h = FREELIST_POINTER(head);
ink_assert(item != TO_PTR(h));
+
+ recovered_item = new (reinterpret_cast<unsigned char *>(item) +
l->offset) void *{};
+ *recovered_item = FREELIST_POINTER(head);
SET_FREELIST_POINTER_VERSION(item_pair, FROM_PTR(item),
FREELIST_VERSION(head));
- INK_MEMORY_BARRIER;
- result = ink_atomic_cas(&l->head.data, head.data, item_pair.data);
- } while (result == 0);
+ result = l->head.compare_exchange_weak(head, item_pair);
+ } while (result == false);
Review Comment:
ink_atomiclist_push does not take the new InkAtomicList mutex, but the PR
description states atomiclist_push was locked to provide mutual exclusion.
Either add the lock (if required for the UB fix) or update the
description/approach; as-is the locking strategy is inconsistent (pop is
locked, popall/push are not).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
