As there have been various discussions[1][2] about improving
the current `list_head` facilities, I would like to
propose a type-safe(r), lightweight wrapper: tlist.
The first commit goes into details as to how it works,
lists some of its advantages and disadvantages.
The second commit showcases it in the existing WMI platform driver.
NOTE: these changes are mostly untested! They are purely for showcasing
a possible implementation and API. And they depend on the switch to gnu11.
I would like to get some feedback as to whether/how acceptable this
approach is before going further: writing documentation, tests, and
adding more wrappers around existing `list_head` facilities
(e.g. reverse iteration is not implemented).
If this idea has already been proposed, I apologize,
I must have missed it when I searched for similar patches.
PS. I have tried to select those who may be interested
in this discussion, I may have missed people or added
people who aren't interested. Sorry.
[1]: https://lore.kernel.org/all/[email protected]/
[2]: https://lore.kernel.org/all/[email protected]/
And see https://lwn.net/Articles/887097/ for a summary.
Barnabás Pőcze (2):
list: add type-safer list_head wrapper
platform/x86: wmi: use tlist for WMI blocks
drivers/platform/x86/wmi.c | 54 ++++++++++---------------
include/linux/tlist.h | 81 ++++++++++++++++++++++++++++++++++++++
2 files changed, 102 insertions(+), 33 deletions(-)
create mode 100644 include/linux/tlist.h
--
2.35.1
tlist is a type-safer wrapper around the existing
`list_head` facilities. Use that to make the code
type-safer and shorter.
Signed-off-by: Barnabás Pőcze <[email protected]>
---
drivers/platform/x86/wmi.c | 53 ++++++++++++++------------------------
1 file changed, 20 insertions(+), 33 deletions(-)
diff --git a/drivers/platform/x86/wmi.c b/drivers/platform/x86/wmi.c
index 58a23a9adbef..4da968bda3dc 100644
--- a/drivers/platform/x86/wmi.c
+++ b/drivers/platform/x86/wmi.c
@@ -22,7 +22,7 @@
#include <linux/device.h>
#include <linux/init.h>
#include <linux/kernel.h>
-#include <linux/list.h>
+#include <linux/tlist.h>
#include <linux/miscdevice.h>
#include <linux/module.h>
#include <linux/platform_device.h>
@@ -39,8 +39,6 @@ MODULE_AUTHOR("Carlos Corbacho");
MODULE_DESCRIPTION("ACPI-WMI Mapping Driver");
MODULE_LICENSE("GPL");
-static LIST_HEAD(wmi_block_list);
-
struct guid_block {
guid_t guid;
union {
@@ -75,6 +73,7 @@ struct wmi_block {
unsigned long flags;
};
+static TLIST_DEFINE(struct wmi_block, list, wmi_block_list);
/*
* If the GUID data block is marked as expensive, we must enable and
@@ -121,7 +120,6 @@ static struct platform_driver acpi_wmi_driver = {
static acpi_status find_guid(const char *guid_string, struct wmi_block **out)
{
guid_t guid_input;
- struct wmi_block *wblock;
if (!guid_string)
return AE_BAD_PARAMETER;
@@ -129,7 +127,7 @@ static acpi_status find_guid(const char *guid_string, struct wmi_block **out)
if (guid_parse(guid_string, &guid_input))
return AE_BAD_PARAMETER;
- list_for_each_entry(wblock, &wmi_block_list, list) {
+ tlist_for_each(&wmi_block_list, wblock) {
if (guid_equal(&wblock->gblock.guid, &guid_input)) {
if (out)
*out = wblock;
@@ -565,7 +563,6 @@ acpi_status wmi_install_notify_handler(const char *guid,
wmi_notify_handler handler,
void *data)
{
- struct wmi_block *block;
acpi_status status = AE_NOT_EXIST;
guid_t guid_input;
@@ -575,7 +572,7 @@ acpi_status wmi_install_notify_handler(const char *guid,
if (guid_parse(guid, &guid_input))
return AE_BAD_PARAMETER;
- list_for_each_entry(block, &wmi_block_list, list) {
+ tlist_for_each(&wmi_block_list, block) {
acpi_status wmi_status;
if (guid_equal(&block->gblock.guid, &guid_input)) {
@@ -605,7 +602,6 @@ EXPORT_SYMBOL_GPL(wmi_install_notify_handler);
*/
acpi_status wmi_remove_notify_handler(const char *guid)
{
- struct wmi_block *block;
acpi_status status = AE_NOT_EXIST;
guid_t guid_input;
@@ -615,7 +611,7 @@ acpi_status wmi_remove_notify_handler(const char *guid)
if (guid_parse(guid, &guid_input))
return AE_BAD_PARAMETER;
- list_for_each_entry(block, &wmi_block_list, list) {
+ tlist_for_each(&wmi_block_list, block) {
acpi_status wmi_status;
if (guid_equal(&block->gblock.guid, &guid_input)) {
@@ -652,9 +648,7 @@ EXPORT_SYMBOL_GPL(wmi_remove_notify_handler);
*/
acpi_status wmi_get_event_data(u32 event, struct acpi_buffer *out)
{
- struct wmi_block *wblock;
-
- list_for_each_entry(wblock, &wmi_block_list, list) {
+ tlist_for_each(&wmi_block_list, wblock) {
struct guid_block *gblock = &wblock->gblock;
if ((gblock->flags & ACPI_WMI_EVENT) && gblock->notify_id == event)
@@ -854,10 +848,8 @@ static int wmi_dev_match(struct device *dev, struct device_driver *driver)
static int wmi_char_open(struct inode *inode, struct file *filp)
{
const char *driver_name = filp->f_path.dentry->d_iname;
- struct wmi_block *wblock;
- struct wmi_block *next;
- list_for_each_entry_safe(wblock, next, &wmi_block_list, list) {
+ tlist_for_each(&wmi_block_list, wblock) {
if (!wblock->dev.dev.driver)
continue;
if (strcmp(driver_name, wblock->dev.dev.driver->name) == 0) {
@@ -1143,12 +1135,10 @@ static int wmi_create_device(struct device *wmi_bus_dev,
static void wmi_free_devices(struct acpi_device *device)
{
- struct wmi_block *wblock, *next;
-
/* Delete devices for all the GUIDs */
- list_for_each_entry_safe(wblock, next, &wmi_block_list, list) {
+ tlist_for_each_safe(&wmi_block_list, wblock) {
if (wblock->acpi_device == device) {
- list_del(&wblock->list);
+ tlist_remove(&wmi_block_list, wblock);
device_unregister(&wblock->dev.dev);
}
}
@@ -1156,9 +1146,7 @@ static void wmi_free_devices(struct acpi_device *device)
static bool guid_already_parsed(struct acpi_device *device, const guid_t *guid)
{
- struct wmi_block *wblock;
-
- list_for_each_entry(wblock, &wmi_block_list, list) {
+ tlist_for_each(&wmi_block_list, wblock) {
if (guid_equal(&wblock->gblock.guid, guid)) {
/*
* Because we historically didn't track the relationship
@@ -1182,7 +1170,7 @@ static int parse_wdg(struct device *wmi_bus_dev, struct acpi_device *device)
{
struct acpi_buffer out = {ACPI_ALLOCATE_BUFFER, NULL};
const struct guid_block *gblock;
- struct wmi_block *wblock, *next;
+ struct wmi_block *wblock;
union acpi_object *obj;
acpi_status status;
int retval = 0;
@@ -1232,7 +1220,7 @@ static int parse_wdg(struct device *wmi_bus_dev, struct acpi_device *device)
continue;
}
- list_add_tail(&wblock->list, &wmi_block_list);
+ tlist_push_back(&wmi_block_list, wblock);
if (debug_event) {
wblock->handler = wmi_notify_debug;
@@ -1244,7 +1232,7 @@ static int parse_wdg(struct device *wmi_bus_dev, struct acpi_device *device)
* Now that all of the devices are created, add them to the
* device tree and probe subdrivers.
*/
- list_for_each_entry_safe(wblock, next, &wmi_block_list, list) {
+ tlist_for_each_safe(&wmi_block_list, wblock) {
if (wblock->acpi_device != device)
continue;
@@ -1254,7 +1242,7 @@ static int parse_wdg(struct device *wmi_bus_dev, struct acpi_device *device)
&wblock->gblock.guid);
if (debug_event)
wmi_method_enable(wblock, false);
- list_del(&wblock->list);
+ tlist_remove(&wmi_block_list, wblock);
put_device(&wblock->dev.dev);
}
}
@@ -1308,21 +1296,20 @@ acpi_wmi_ec_space_handler(u32 function, acpi_physical_address address,
static void acpi_wmi_notify_handler(acpi_handle handle, u32 event,
void *context)
{
- struct wmi_block *wblock;
- bool found_it = false;
+ struct wmi_block *wblock = NULL;
- list_for_each_entry(wblock, &wmi_block_list, list) {
- struct guid_block *block = &wblock->gblock;
+ tlist_for_each(&wmi_block_list, b) {
+ struct guid_block *block = &b->gblock;
- if (wblock->acpi_device->handle == handle &&
+ if (b->acpi_device->handle == handle &&
(block->flags & ACPI_WMI_EVENT) &&
(block->notify_id == event)) {
- found_it = true;
+ wblock = b;
break;
}
}
- if (!found_it)
+ if (!wblock)
return;
/* If a driver is bound, then notify the driver. */
--
2.35.1
The aim of this patch is to add a type-safer, lightweight
wrapper around the currently available `list_head` facilities
existing in the kernel. It is named "tlist", which may or
may not stand for "typed list".
The type-safe(r)ty is achieved by storing compile-time metadata
in the list head:
* the type of the objects ("value type"), and
* the offset of the `list_head` member ("member offset")
These only appear at compile-time, and do not affect the actual
generated executable code. (They might show up in debug info, etc.)
The underlying idea is to define each list head using an anonymous struct:
#define TLIST(T, member)
struct {
struct list_head head;
char _member_offset[0][offsetof(T, member) +
BUILD_BUG_ON_ZERO(!__same_type(struct list_head,
typeof_member(T, member)))];
T _type[0];
}
Arguably, this is an abuse of multiple features of GNU C. However,
it is nothing new. The currently existing `__STRUCT_KFIFO_COMMON()` macro
uses the same underlying idea to store type and size information
in the type, like a C++ template.
Note, that the `member` in `T` must be a `struct list_head` object,
it is not possible to specify a non-list-head member by accident.
Let us assume we have a tlist:
struct wmi_block {
struct wmi_device dev;
struct list_head list;
...
};
TLIST(struct wmi_block, list) wmi_block_list = ...;
Note, that the items in the list still only embed a `list_head`
object. Only the head of the list has a different type.
In this scenario, the value type can be retrieved using:
typeof(*wmi_block_list._type)
and the member offset:
sizeof(*wmi_block_list._member_offset)
Looking at the `__STRUCT_KFIFO_COMMON()` one might ask:
why aren't pointers used? Why zero-length arrays?
The answer is const-correctness - that is, a const tlist
can only be iterated with a `const value_type *` -, which
I believe is nice to have.
With the previous type and offset primitives, it is easy to
implement a type-safe insertion macro:
#define __tlist_ptroff(base, offset, T)
((T *) (((uintptr_t)(base)) + (offset)))
#define tlist_item_to_node(list, item)
(__tlist_ptroff((item), tlist_member_offset(list), struct list_head) +
BUILD_BUG_ON_ZERO(!__same_type(*(item), tlist_value_type(list))))
#define tlist_push_back(list, item)
list_add_tail(tlist_head(list), tlist_item_to_node((list), (item)))
Note, `tlist_head()` is a macro which simply expands to the underlying
`list_head`.
The real type checking is done inside the `tlist_item_to_node()` macro
which does two things:
* get a pointer to the embedded `list_head` object using the
known member offset, and
* check if `item` matches the value type of the tlist
Note, that the existing `list_head` facilities can still be used
since the head of a tlist can be easily retrieved and the list items
only include a `list_head` object.
All in all, for insertion, a tlist completely elliminates the
possibility of inserting an object with the wrong type or
wrong `list_head` member. (Of course, assuming the appropriate
wrappers are used.)
Iteration is also possible in a very convenient manner:
#define tlist_node_to_item(list, node)
__tlist_ptroff((node), -tlist_member_offset(list), tlist_value_type(list))
#define tlist_begin(list)
tlist_node_to_item((list), tlist_head(list)->next)
#define tlist_end(list)
tlist_node_to_item((list), tlist_head(list))
#define tlist_item_next(list, item) \
tlist_node_to_item((list), tlist_item_to_node((list), (item))->next)
#define tlist_for_each(list, iter)
for (tlist_value_type(list) *iter = tlist_begin(list);
iter != tlist_end(list);
iter = tlist_item_next(list, iter))
...
tlist_for_each(&wmi_block_list, wblock) {
if (guid_equal(&wblock->gblock.guid, &guid_input)) {
if (out)
*out = wblock;
return AE_OK;
}
}
Note, the iterator is defined in the scope of the for loop,
reuse after the loop is not possible by accident. Also note,
that neither the type, nor the name of the correct `list_head` member
need to be known (or specified) when iterating over a tlist.
The "safe" iterations are also easily implementable (see this patch)
without even needing to explicitly name/create the secondary iterator.
Reverse iteration is naturally also implementable.
Removal from a tlist is possible using the already existing
`list_del()`, etc. facilities, or there is the newly added
#define tlist_remove(list, item)
list_del(tlist_item_to_node((list), (item)))
This macro also does type-checking and selects the correct
`list_head` member based on the known offset.
There are, however, certain limitations of the tlist wrapper.
The biggest of which is that they cannot easily be
passed from/to functions since every tlist has a distinct
type from every other type because they are anonymous structs.
Furthermore, when declaring a tlist, the value type must be
complete, otherwise e.g. the `offsetof()` would not work.
Thus it is not possible to have a list of nodes which has
no "separate" head.
Signed-off-by: Barnabás Pőcze <[email protected]>
---
include/linux/tlist.h | 75 +++++++++++++++++++++++++++++++++++++++++++
1 file changed, 75 insertions(+)
create mode 100644 include/linux/tlist.h
diff --git a/include/linux/tlist.h b/include/linux/tlist.h
new file mode 100644
index 000000000000..ad68de9d74fa
--- /dev/null
+++ b/include/linux/tlist.h
@@ -0,0 +1,75 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef _LINUX_TLIST_H
+#define _LINUX_TLIST_H
+
+#include <linux/build_bug.h>
+#include <linux/compiler.h>
+#include <linux/container_of.h>
+#include <linux/list.h>
+
+#define TLIST(T, member) \
+struct { \
+ struct list_head head; \
+ char _member_offset[0][offsetof(T, member) + \
+ BUILD_BUG_ON_ZERO(!__same_type(struct list_head, \
+ typeof_member(T, member)))]; \
+ T _type[0]; \
+}
+
+#define TLIST_DEFINE(T, member, name) \
+ TLIST(T, member) name = { LIST_HEAD_INIT((name).head) }
+
+#define tlist_value_type(list) \
+ typeof(*(list)->_type)
+
+#define tlist_member_offset(list) \
+ sizeof(*(list)->_member_offset)
+
+#define tlist_head(list) \
+ (&(list)->head)
+
+#define tlist_init(list) \
+ INIT_LIST_HEAD(tlist_head(list))
+
+#define tlist_is_empty(list) \
+ list_empty(tlist_head(list))
+
+#define __tlist_ptroff(base, offset, T) \
+ ((T *) (((uintptr_t)(base)) + (offset)))
+
+#define tlist_item_to_node(list, item) \
+ (__tlist_ptroff((item), tlist_member_offset(list), struct list_head) + \
+ BUILD_BUG_ON_ZERO(!__same_type(*(item), tlist_value_type(list))))
+
+#define tlist_node_to_item(list, node) \
+ __tlist_ptroff((node), -tlist_member_offset(list), tlist_value_type(list))
+
+#define tlist_begin(list) \
+ tlist_node_to_item((list), tlist_head(list)->next)
+
+#define tlist_end(list) \
+ tlist_node_to_item((list), tlist_head(list))
+
+#define tlist_remove(list, item) \
+ list_del(tlist_item_to_node((list), (item)))
+
+#define tlist_push_back(list, item) \
+ list_add_tail(tlist_head(list), tlist_item_to_node((list), (item)))
+
+#define tlist_item_next(list, item) \
+ tlist_node_to_item((list), tlist_item_to_node((list), (item))->next)
+
+#define tlist_for_each(list, iter) \
+ for (tlist_value_type(list) *iter = tlist_begin(list); \
+ iter != tlist_end(list); \
+ iter = tlist_item_next(list, iter))
+
+#define __tlist_for_each_safe(list, iter, next_iter) \
+ for (tlist_value_type(list) *iter = tlist_begin(list), *next_iter; \
+ iter != tlist_end(list) && (next_iter = tlist_item_next(list, iter), 1); \
+ iter = next_iter)
+
+#define tlist_for_each_safe(list, iter) \
+ __tlist_for_each_safe((list), iter, __UNIQUE_ID(tlist_next_))
+
+#endif /* _LINUX_TLIST_H */
--
2.35.1
On Thu, Mar 10, 2022 at 5:42 PM Linus Torvalds
<[email protected]> wrote:
>
> That one didn't do the automatic offset thing, but see
>
> https://lore.kernel.org/all/CAADWXX-Pr-D3wSr5wsqTEOBSJzB9k7bSH+7hnCAj0AeL0=U4mg@mail.gmail.com/
>
> on the problems that has.
Note: I think the problems are serious enough that it almost certainly
isn't worth doing - it makes the code uglier for very little upside.
So I tried to explain how it _could_ be done, but that doesn't mean
that it _should_ be done.
Having the member name as part of the list traversal macro isn't
actually generally a real problem.
I added it to the list_traversal_head() macro in that original patch
because I think we can easily use the member head name to _verify_
that the declaration and the use match.
Yes, squirrelling off the offset and not needing the member head name
at all at when traversing the list is obviously simpler syntax, but
that part has never been the real problem with list traversal. And
verifying that the member name that is passed in is the same as in the
list_traversal_head() would be trivial.
To verify it, we could simply change that type name from:
type *name##_traversal_type;
to be
type *name##_traversal_type_##member;
instead, and suddenly the member name in 'list_traverse()' has to
match that thing that list_traversal_head() created.
So yes, you'd have that third argument in list_traverse(), but it
would be trivially checked at compile-time.
And you'd avoid all the ugly complexities (described above) with lists
that are embedded inside data structures that refer to each other)
Linus
On Thu, Mar 10, 2022 at 5:33 PM Barnabás Pőcze <[email protected]> wrote:
>
> The underlying idea is to define each list head using an anonymous struct:
Why struct? Union is much better, and doesn't pointlessly waste memory
for members that are only used for their type.
Anyway, as far as I can tell, your model is unworkable as-is, since it
only works for a list that is external to the types in question.
Which is not even remotely the interesting case. All serious list uses
are inside other types, and refer to each other.
So this seems to be fundamentally broken, in that it only works for
trivial things, and is not even as good as
https://lore.kernel.org/all/CAHk-=wiacQM76xec=Hr7cLchVZ8Mo9VDHmXRJzJ_EX4sOsApEA@mail.gmail.com/
that actually converted a real case.
That one didn't do the automatic offset thing, but see
https://lore.kernel.org/all/CAADWXX-Pr-D3wSr5wsqTEOBSJzB9k7bSH+7hnCAj0AeL0=U4mg@mail.gmail.com/
on the problems that has.
Again, you avoided those problems by making the use-case a narrow and
uninteresting one.
Linus