[RFC PATCH v1 0/2] add type-safer list_head wrapper

[RFC PATCH v1 0/2] add type-safer list_head wrapper

[Barnabás Pőcze]

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/20220217184829.1991035-1-jakobkoschel@gmail.com/
[2]: https://lore.kernel.org/all/20220301075839.4156-1-xiam0nd.tong@gmail.com/
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

[RFC PATCH v1 1/2] list: add type-safer list_head wrapper

[Barnabás Pőcze]

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 <pobrn@protonmail.com>
---
 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

[RFC PATCH v1 2/2] platform/x86: wmi: use tlist for WMI blocks

[Barnabás Pőcze]

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 <pobrn@protonmail.com>
---
 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

Re: [RFC PATCH v1 1/2] list: add type-safer list_head wrapper

[Linus Torvalds]

On Thu, Mar 10, 2022 at 5:33 PM Barnabás Pőcze <pobrn@protonmail.com> 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

Re: [RFC PATCH v1 1/2] list: add type-safer list_head wrapper

[Linus Torvalds]

On Thu, Mar 10, 2022 at 5:42 PM Linus Torvalds
<torvalds@linux-foundation.org> 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

Re: [RFC PATCH v1 1/2] list: add type-safer list_head wrapper

[Barnabás Pőcze]

Hi


2022. március 11., péntek 2:42 keltezéssel, Linus Torvalds írta:
> On Thu, Mar 10, 2022 at 5:33 PM Barnabás Pőcze <pobrn@protonmail.com> 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.

As far as I can tell, zero-sized arrays won't take up any space. It's true
that if the type has excessive alignment requirements, then it may indeed
waste space. Changing it to a pointer+union is a simple change, nonetheless.


>
> 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.

Yes, I have mentioned at the end that there are limitations of this approach
(to keep it easy to use and sane) and that it won't work everywhere,
namely where the value type is incomplete. E.g.
  * you cannot have a list of T inside a T;
  * you cannot have a list of B inside A plus a list of A inside B.

Nonetheless, I still think there are legitimate use cases for this, where
the simple, limited interface works fine. And I am by no means suggesting
not going forward with the other ideas that came up. I mostly imagined this
tlist as an "addition" for the simple, trivial cases.

For example, there are currently more than 1000 occurrences of

  static LIST_HEAD(

in the source tree. I did not check, but I think it's very likely that most of
them would satisfy the constraints of the proposed interface. And while I cannot
provide any numbers, I would not be surprised if most list uses in the kernel were
"boring" and "trivial", where this interface would work.

But I understand if you don't want something that doesn't work for every case.


Best regards,
Barnabás Pőcze

Re: [RFC PATCH v1 1/2] list: add type-safer list_head wrapper

[Barnabás Pőcze]

Hi


2022. március 11., péntek 3:01 keltezéssel, Linus Torvalds írta:
> On Thu, Mar 10, 2022 at 5:42 PM Linus Torvalds
> <torvalds@linux-foundation.org> 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.

That is indeed a simpler thing to do, and doesn't need `offsetof()` at the
declaration, but there are places - not many -  where the `list_head` member
is inside a subobject, for example, so `member` now contains a period.


>
> And you'd avoid all the ugly complexities (described above) with lists
> that are embedded inside data structures that refer to each other)


Regards,
Barnabás Pőcze

Re: [RFC PATCH v1 1/2] list: add type-safer list_head wrapper

[Linus Torvalds]

On Thu, Mar 10, 2022 at 6:49 PM Barnabás Pőcze <pobrn@protonmail.com> wrote:
>
> That is indeed a simpler thing to do, and doesn't need `offsetof()` at the
> declaration, but there are places - not many -  where the `list_head` member
> is inside a subobject, for example, so `member` now contains a period.

Ahh, very true. And very annoying. So close, yet so far, and no way I
can see to really deal with that.

And it's not even really all that rare. It may not be the _common_
case, but it's still fairly wide-spread and not some "one or two odd
places" thing.

This grep catches at least a subset of cases:

    git grep '\<list_for_each_entry(.*\.[a-z_0-9]*)'

and it's clearly all over.

As mentioned, I don't think that we have had huge problems with
getting the member name wrong. We do get a fair amount of checking in
that it obviously has to be part of the type we iterate over, and even
if you were to pick the wrong one, the result is a very simple "that
doesn't work".

But it would still undeniably be very nice to have some automatic
build-time checking for it.

Now, some checking could be done by just doing the "reverse" of what
that patch in

  https://lore.kernel.org/all/CAHk-=wiacQM76xec=Hr7cLchVZ8Mo9VDHmXRJzJ_EX4sOsApEA@mail.gmail.com/

does with 'list_traversal_head()', and have a

  #define list_traversal_entry()

that has a similar union with a type that also specifies the list
entry type (with that same "append marker to member name" model, which
still works fine with dots in the middle).

Then at least cross-checking that the type of the iterator matches
with the target list member is trivial, but _if_ a type has multiple
list entries, they often end up referring to the same type.

That very patch with 'struct task_struct' converted is actually an
example of exactly that: the <children,sibling> and <ptraced,
ptrace_entry> pairings have the exact same type tuple (all being
'struct task_struct', of course).

So it would strengthen the typechecking a bit in some cases, but
probably not all that noticeably.

            Linus

Re: [RFC PATCH v1 1/2] list: add type-safer list_head wrapper

[Barnabás Pőcze]

Hi


2022. március 11., péntek 6:06 keltezéssel, Linus Torvalds írta:
> On Thu, Mar 10, 2022 at 6:49 PM Barnabás Pőcze <pobrn@protonmail.com> wrote:
> >
> > That is indeed a simpler thing to do, and doesn't need `offsetof()` at the
> > declaration, but there are places - not many -  where the `list_head` member
> > is inside a subobject, for example, so `member` now contains a period.
>
> Ahh, very true. And very annoying. So close, yet so far, and no way I
> can see to really deal with that.
>
> And it's not even really all that rare. It may not be the _common_
> case, but it's still fairly wide-spread and not some "one or two odd
> places" thing.
>
> This grep catches at least a subset of cases:
>
>     git grep '\<list_for_each_entry(.*\.[a-z_0-9]*)'
>
> and it's clearly all over.
>
> As mentioned, I don't think that we have had huge problems with
> getting the member name wrong. We do get a fair amount of checking in
> that it obviously has to be part of the type we iterate over, and even
> if you were to pick the wrong one, the result is a very simple "that
> doesn't work".
>
> But it would still undeniably be very nice to have some automatic
> build-time checking for it.
>

Yes, I think compile-time errors are significantly better than whatever you get
at runtime. So, sorry to be this obtuse, but I gather the proposed interface
is a no-go in all ways, shapes, and forms in your eyes? I am fully aware that it
does not magically solve everything and it does not work in the "interesting"
and "convoluted" cases, but as mentioned in a previous email, I think there are
still a lot of "boring" places where it can be used. But of course I don't want
to bother anyone if it's a definitive no.


> [...]


Regards,
Barnabás Pőcze

Re: [RFC PATCH v1 1/2] list: add type-safer list_head wrapper

[Linus Torvalds]

On Fri, Mar 11, 2022 at 2:15 PM Barnabás Pőcze <pobrn@protonmail.com> wrote:
>
>      So, sorry to be this obtuse, but I gather the proposed interface
> is a no-go in all ways, shapes, and forms in your eyes?

Yeah, not with the limitation that it only works on global list heads.
We already have a lot of different list traversal things (rcu, safe,
hlist, continue-in-the-middle etc etc), and we clearly are going to
add a new set - but I don't want to add one that is so limited that it
only works for the simplest kind of list.

                  Linus

Re: [RFC PATCH v1 1/2] list: add type-safer list_head wrapper

[Linus Torvalds]

On Fri, Mar 11, 2022 at 3:45 PM Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>
> Yeah, not with the limitation that it only works on global list heads. [..]

"global" is the wrong word. Obviously it works on static list heads in
file - or even function - scope etc too. But you get what I'm saying..

            Linus