[PATCH][2.5] Single linked headed lists for Linux, v3

[PATCH][2.5] Single linked headed lists for Linux, v3

[Lightweight Patch Manager]

--- /dev/null	Wed Dec 31 17:00:00 1969
+++ slist-2.5/include/linux/shlist.h	Sat Sep 28 03:31:18 2002
@@ -0,0 +1,196 @@
+#ifdef __KERNEL__
+#ifndef _LINUX_SLIST_H
+#define _LINUX_SLIST_H
+
+#include <asm/processor.h>
+
+/*
+ * Type-preserving  single  linked  headed list  helper-functions  for
+ * circular and linear lists. (Code originally taken from list.h)
+ *
+ * Thomas 'Dent' Mirlacher, Daniel Phillips, Thunder from the hill
+ */
+
+/******************************************************************************
+ * Common stuff 
+ *****************************************************************************/
+
+/**
+ * slist_add_front - add a new entry at the first slot, moving the old head
+ *		     to the second slot
+ * @new:	new entry to be added
+ * @head:	head of the single linked list
+ *
+ * Insert a new entry before the specified head.
+ * This is good for implementing stacks.
+ */
+
+#define slist_add_front(_new_in, _head_in)	\
+do {						\
+	typeof(_head_in) _head = _head_in,	\
+		    _new = _new_in;		\
+	_new->next = _head;			\
+	_head = _new;				\
+} while (0)
+
+/**
+ * slist_add - add a new entry after the list head
+ * @new:       new entry to be added
+ * @head:      head of the single linked list
+ *
+ * Insert a new entry before the specified head.
+ * This is good for implementing stacks.
+ *
+ * Careful: if you do this concurrently, _head
+ * might get into nirvana...
+ */
+#define slist_add(_new_in, _head_in)		\
+do {						\
+	typeof(_head_in) _head = (_head_in),	\
+		    _new = (_new_in);		\
+	_new->next = _head->next;		\
+	_head->next = _new;			\
+} while (0)
+
+/**
+ * slist_del_single -	untag a list from an entry
+ * @list:	list entry to be untagged
+ */
+#define slist_del_single(_list)			\
+	((_list)->next = NULL)
+
+/**
+ * slist_pop	-	pop out list entry
+ * @list:	entry to be popped out
+ *
+ * Pop out an entry from a list.
+ */
+#define slist_pop(_list_in) ({			\
+	typeof(_list_in) _list = (_list_in),	\
+		    _NODE_ = _list;		\
+	if (_list) {				\
+	    (_list) = (_list)->next;		\
+	    _NODE_->next = NULL;		\
+	}					\
+	_NODE_; })
+
+/**
+ * slist_del -	remove an entry from a list, walking the list from the head
+ * @head:	list head, where the walking will start
+ * @entry:	entry to be removed
+ */
+#define slist_del(_entry_in,_head_in)			\
+do {							\
+	typeof(_entry_in) _entry = (_entry_in),		\
+			  _head  = (_head_in);		\
+	if (_head == _entry) {				\
+		_head = _entry->next;			\
+		slist_del_single(_entry);		\
+	} else {					\
+		typeof(_entry) _pos, _prev=_head;	\
+		while (_prev && (_pos = _prev->next)) {	\
+			if (_pos == _entry) {		\
+				_prev->next = _pos->next;\
+				slist_del_single(_pos);	\
+				break;			\
+			}				\
+			_prev = _pos;			\
+			if (_prev == _head) break;	\
+		}					\
+		/* Entry is not on list. BUG? --ct */	\
+	}						\
+} while (0)
+
+/**
+ * slist_del_quick -	(re)move an entry from list
+ * @buf:	a storage area, just as long as the entry
+ * @entry:	entry to be removed
+ */
+#define slist_del_quick(_entry_in,_buf_in)		\
+do {							\
+	typeof(_entry_in) _entry = (_entry_in),		\
+			  _buf = (_buf_in), _free;	\
+	_free = _entry->next;				\
+	memcpy(_buf, _entry, sizeof(_entry));		\
+	memcpy(_entry, _free, sizeof(_entry));		\
+	memcpy(_buf, _free, sizeof(_entry));		\
+	slist_del_single(_entry);			\
+} while (0)
+
+/******************************************************************************
+ * Linear specific
+ *****************************************************************************/
+
+#define INIT_SLIST_HEAD(name)			\
+	(name->next = NULL)
+
+#define SLIST_HEAD_INIT(name)			\
+	{ .next = NULL; }
+
+#define SLIST_HEAD(type,name)			\
+	typeof(type) name = SLIST_HEAD_INIT(name)
+
+/**
+ * slist_for_each	-	iterate over a list
+ * @pos:	the pointer to use as a loop counter.
+ * @head:	the head for your list (this is also the first entry).
+ */
+#define slist_for_each(pos, head)				\
+	for (pos = head; pos && ({ prefetch(pos->next); 1; });	\
+	    pos = pos->next)
+
+/**
+ * slist_for_each_del	-	iterate over a list, popping off entries
+ * @pos:       the pointer to use as a loop counter.
+ * @head:      the head for your list (this is also the first entry).
+ */
+#define slist_for_each_del(pos, head)			\
+	for (pos = slist_pop(head); pos &&		\
+    	    ({ prefetch(pos->next); 1; });		\
+	    pos = slist_pop(head))
+
+/******************************************************************************
+ * Circular specific
+ *****************************************************************************/
+
+#define INIT_SLIST_LOOP(name)			\
+	(name->next = name)
+
+#define SLIST_LOOP_INIT(name)			\
+	{ .next = name; }
+
+#define SLIST_LOOP(type,name)			\
+	typeof(type) name = SLIST_LOOP_INIT(name);
+
+/**
+ * slist_del_init -	remove an entry from list and initialize it
+ * @head:	head to remove it from
+ * @entry:	entry to be removed
+ */
+#define slist_del_init(_entry_in)			\
+({							\
+	typeof(_entry_in) _entry = (_entry_in), _head =	\
+	    kmalloc(sizeof(_entry), GFP_KERNEL), _free;	\
+	if (_head) {					\
+	    memcpy(_head, (_entry), sizeof(_entry));	\
+	    _free = (_entry);				\
+	    (_entry) = (_entry)->next;			\
+	    kfree(_free);				\
+	    _head->next = _head;			\
+	    _head;					\
+	} else						\
+	    NULL;					\
+})
+
+/**
+ * slist_for_each_circular	-	iterate over a circular list
+ * @pos:	the pointer to use as a loop counter.
+ * @head:	the head for your list (this is also the first entry).
+ */
+#define slist_for_each_circular(pos, head)		\
+	for (pos = head; pos && pos != head &&		\
+	    ({ prefetch(pos->next); 1; });		\
+	    pos = pos->next)
+
+#endif /* _LINUX_SLIST_H */
+#endif /* __KERNEL__ */

-- 
Lightweight Patch Manager, without pine.
If you have any objections (apart from who I am), tell me

Re: [PATCH][2.5] Single linked headed lists for Linux, v3

[Thunder from the hill]

Hi,

On Sat, 28 Sep 2002, Lightweight Patch Manager wrote:
> +/**
> + * slist_del_init -	remove an entry from list and initialize it
> + * @head:	head to remove it from
> + * @entry:	entry to be removed
> + */
> +#define slist_del_init(_entry_in)			\
> +({							\
> +	typeof(_entry_in) _entry = (_entry_in), _head =	\
> +	    kmalloc(sizeof(_entry), GFP_KERNEL), _free;	\
> +	if (_head) {					\
> +	    memcpy(_head, (_entry), sizeof(_entry));	\
> +	    _free = (_entry);				\
> +	    (_entry) = (_entry)->next;			\
> +	    kfree(_free);				\
> +	    _head->next = _head;			\
> +	    _head;					\
> +	} else						\
> +	    NULL;					\
> +})

Forget this piece...

			Thunder
-- 
assert(typeof((fool)->next) == typeof(fool));	/* wrong */

Re: [PATCH][2.5] Single linked headed lists for Linux, v3

[Christoph Hellwig]

Please kill the sillz ifdef __KERNEL__ and convert to inlines.
After that one could start to ctuallz review the implementation..

Re: [PATCH][2.5] Single linked headed lists for Linux, v3

[Thunder from the hill]

Hi,

On Sat, 28 Sep 2002, Christoph Hellwig wrote:
> Please kill the sillz ifdef __KERNEL__ and convert to inlines.
> After that one could start to ctuallz review the implementation..

Sorry, inline taints the concept. It's supposed to work with any type. 
(This time.) We've had crappy times with list.h, so slist.h shall not use 
inlines.

			Thunder

Re: [PATCH][2.5] Single linked headed lists for Linux, v3

[Christoph Hellwig]

On Sat, Sep 28, 2002 at 07:27:37AM -0600, Thunder from the hill wrote:
> Sorry, inline taints the concept. It's supposed to work with any type. 
> (This time.) We've had crappy times with list.h, so slist.h shall not use 
> inlines.

Define crappy times.

Re: [PATCH][2.5] Single linked headed lists for Linux, v3

[Thunder from the hill]

Hi,

On Sat, 28 Sep 2002, Christoph Hellwig wrote:
> On Sat, Sep 28, 2002 at 07:27:37AM -0600, Thunder from the hill wrote:
> > Sorry, inline taints the concept. It's supposed to work with any type. 
> > (This time.) We've had crappy times with list.h, so slist.h shall not use 
> > inlines.
> 
> Define crappy times.

 - casts
 - list members had to be in some specified place of the struct
 - some binary disadvantages

Remember? And -- I don't find the defines so unreadable. Try it!

			Thunder

Re: [PATCH][2.5] Single linked headed lists for Linux, v3

[Christoph Hellwig]

On Sat, Sep 28, 2002 at 07:45:00AM -0600, Thunder from the hill wrote:
> Hi,
> 
> On Sat, 28 Sep 2002, Christoph Hellwig wrote:
> > On Sat, Sep 28, 2002 at 07:27:37AM -0600, Thunder from the hill wrote:
> > > Sorry, inline taints the concept. It's supposed to work with any type. 
> > > (This time.) We've had crappy times with list.h, so slist.h shall not use 
> > > inlines.
> > 
> > Define crappy times.
> 
>  - casts
>  - list members had to be in some specified place of the struct
>  - some binary disadvantages

All of those are utter crap.  Older gcc's had some little inlining
problems that generated suboptimal code, but that's cured now and
I don't thikn it even made a difference for the small list_* functions.

Re: [PATCH][2.5] Single linked headed lists for Linux, v3

[Thunder from the hill]

Hi,

On Sat, 28 Sep 2002, Christoph Hellwig wrote:
> All of those are utter crap.  Older gcc's had some little inlining
> problems that generated suboptimal code, but that's cured now and I
> don't thikn it even made a difference for the small list_* functions.

I think if we scale slists to be like lists, we don't need to make the 
difference at all. slists are supposed to be lightweight lists, single 
direction, and working anywhere on any type of structure. (e.g. you can 
access a whole struct thread through the ->next pointer, instead of 
further crap.)

If we can avoid type dependency, we should do now. If you want inlined 
code, go read list.h. (I remember that's why the lists were called 
`type-safe', BTW. Meant to be type-preserve, and definitely the same type 
as before.)

			Thunder
-- 

Re: [PATCH][2.5] Single linked headed lists for Linux, v3

[Christoph Hellwig]

On Sat, Sep 28, 2002 at 08:00:33AM -0600, Thunder from the hill wrote:
> Hi,
> 
> On Sat, 28 Sep 2002, Christoph Hellwig wrote:
> > All of those are utter crap.  Older gcc's had some little inlining
> > problems that generated suboptimal code, but that's cured now and I
> > don't thikn it even made a difference for the small list_* functions.
> 
> I think if we scale slists to be like lists, we don't need to make the 
> difference at all.

twice the size of each entry is a big enough difference.  No need to
add ugly code as second criteria.

Re: [PATCH][2.5] Single linked headed lists for Linux, v3

[Thunder from the hill]

Hi,

On Sat, 28 Sep 2002, Christoph Hellwig wrote:
> twice the size of each entry is a big enough difference.  No need to
> add ugly code as second criteria.

We just have to add one little ugliness in order to generate even more 
useful code. As to that, I do definitely disagree with inlining these 
functions. (There are really lots of functions where inlining actually 
makes an awful lot of sense, but this one isn't amongst them.)

			Thunder

Re: [PATCH][2.5] Single linked headed lists for Linux, v3

[Zwane Mwaikambo]

On Sat, 28 Sep 2002, Christoph Hellwig wrote:

> Please kill the sillz ifdef __KERNEL__ and convert to inlines.
> After that one could start to ctuallz review the implementation..

Someone just got a German keyboard? ;)

-- 
function.linuxpower.ca

Re: [PATCH][2.5] Single linked headed lists for Linux, v3

[Christoph Hellwig]

On Sat, Sep 28, 2002 at 09:29:31AM -0400, Zwane Mwaikambo wrote:
> Someone just got a German keyboard? ;)

Yupp :P  Internetcafes on the road have disadvantages..

Re: [PATCH][2.5] Single linked headed lists for Linux, v3

[Roman Zippel]

Hi,

On Sat, 28 Sep 2002, Christoph Hellwig wrote:

> Please kill the sillz ifdef __KERNEL__ and convert to inlines.
> After that one could start to ctuallz review the implementation..

Add using a real name to the list, using pseudonyms is just silly and
patches from anonymous sources (without _very_ good reasons) are highly
suspicious.

bye, Roman

Re: [PATCH][2.5] Single linked headed lists for Linux, v3

[Tomas Szepe]

> > Please kill the sillz ifdef __KERNEL__ and convert to inlines.
> > After that one could start to ctuallz review the implementation..
> 
> Add using a real name to the list, using pseudonyms is just silly and
> patches from anonymous sources (without _very_ good reasons) are highly
> suspicious.

Would you kindly refrain from dissing the author on this silly level and
actually evaluate the code he's submitting?

T.

Re: [PATCH][2.5] Single linked headed lists for Linux, v3

[Roman Zippel]

Hi,

On Sat, 28 Sep 2002, Tomas Szepe wrote:

> > Add using a real name to the list, using pseudonyms is just silly and
> > patches from anonymous sources (without _very_ good reasons) are highly
> > suspicious.
>
> Would you kindly refrain from dissing the author on this silly level and

Can anyone confirm this is his real name? This is simply not a typical
English name. If "Thunder from the hill" is his official name, I'll
apologize. Sometimes there are good reason (e.g. padeluun in Germany), but
until someone explains me this reason, this is just silly and I have real
problems to take this seriously.

> actually evaluate the code he's submitting?

The "C for dummies" mailing list is somewhere else.

bye, Roman

Re: [PATCH][2.5] Single linked headed lists for Linux, v3

[Thunder from the hill]

Hi,

On Sat, 28 Sep 2002, Roman Zippel wrote:
> Can anyone confirm this is his real name? This is simply not a typical
> English name.

It's not, and I think that's great since I'm not exactly a typical english
guy.

> > actually evaluate the code he's submitting?
> 
> The "C for dummies" mailing list is somewhere else.

I urge you to try to understand why I'm using #define over inline. I've 
explained that multiple times, and I won't abandon it.

			Thunder

Re: [PATCH][2.5] Single linked headed lists for Linux, v3

[Zach Brown]

It is mind-bogglingly clear that you haven't really used these at all.
I still think, because of the magical struct member pollution and the
limitation of structs being on a single list, that these #define-based
slists are fundamentally flawed.  This is the last email I'll send, I
think.  

> +#define SLIST_HEAD(type,name)			\
> +	typeof(type) name = SLIST_HEAD_INIT(name)

ok, problem #1.  I have to instantiate a full copy of the structs that
make up the list to have a head of the list?  say I'm walking a bunch of
tasks and want to have a temporary slist of tasks that I'm going to
later walk and destroy.  I'd like to have a list header on the stack in
that function, but now I can't, because a full task_struct is enormous.
the same goes for many data structures.  This, alone, is enough to
torpedo these lists ever being used.

> +#define SLIST_HEAD_INIT(name)			\
> +	{ .next = NULL; }

ok, right, problem 2.  to make these work, you need a magical .next
member and you get only one.  want to have structs on two lists?  tough.
is that 'next' member in a struct being used by slist macros or did the
author, not knowing about them, open code their own as is _very_ common
in C?  who knows!

go look through the kernel and find structs that have more than one
struct list_head.  realize that with your lists you couldn't do that.
ponder.

and, really, the reason I posted this.  an empty list has a NULL next
pointer as the head.

> +#define slist_add_front(_new_in, _head_in)	\
> +do {						\
> +	typeof(_head_in) _head = _head_in,	\
> +		    _new = _new_in;		\
> +	_new->next = _head;			\

ok, now a new item in the list has ->next null from the head.

> +#define slist_del_quick(_entry_in,_buf_in)		\
> +do {							\
> +	typeof(_entry_in) _entry = (_entry_in),		\
> +			  _buf = (_buf_in), _free;	\
> +	_free = _entry->next;				\
> +	memcpy(_buf, _entry, sizeof(_entry));		\
> +	memcpy(_entry, _free, sizeof(_entry));		\
> +	memcpy(_buf, _free, sizeof(_entry));		\
> +	slist_del_single(_entry);			\
> +} while (0)
> +

wow.

1) we just blindly memcpy()ed from NULL if entry was the last in the
	list.

2) I can only assume that you meant to be memcpy()ing the structs
around.  _entry_in is a pointer.  _buf and _free are pointers.  you're
copying the first pointer-sized chunk of structs around as you delete
entries, corrupting them.

3) you set entry->next to null, but the previous node to entry still
thinks it is the next node.  you just truncated the list, losing all the
later members.

4) if the entire structs really were copied, you just destroyed entry.
maybe you meant to copy buf into free in that last memcpy.

I just don't know what else to say.  just get rid of this concept, no
matter what it was you were really trying to do.  (a node swap concept?
a list seperating concept?  oy.)

> +#define slist_del(_entry_in,_head_in)			\
> +do {							\
> +	typeof(_entry_in) _entry = (_entry_in),		\
> +			  _head  = (_head_in);		\
> +	if (_head == _entry) {				\
> +		_head = _entry->next;			\

wait, we initialized head with .next = NULL, now we're setting it
straight?  one of these is wrong.  also, you're not changing the head,
you're changing the head pointer you allocated on the stack.  you seem
to have really meant _head->next;

> +#define slist_del_init(_entry_in)			\
> +({							\
> +	typeof(_entry_in) _entry = (_entry_in), _head =	\
> +	    kmalloc(sizeof(_entry), GFP_KERNEL), _free;	\
> +	if (_head) {					\
> +	    memcpy(_head, (_entry), sizeof(_entry));	\
> +	    _free = (_entry);				\
> +	    (_entry) = (_entry)->next;			\
> +	    kfree(_free);				\
> +	    _head->next = _head;			\
> +	    _head;					\
> +	} else						\
> +	    NULL;					\
> +})

wow, part 2.

look, thunder, I think we're all for experimentation.  go to town, learn
how lists work.  take it to kernelnewbies or kernel-janitors, I'm sure
someone will be glad to help out.  

but please don't bother sending them to l-k until you've put them
through even the most basic tests and have tried to convert open-coded
single lists in the kernel to them.  

-- 
 zach

Re: [PATCH][2.5] Single linked headed lists for Linux, v3

[Thunder from the hill]

Hi,

To all: I'm not interested in personal attacks. If I want them, I'll tell
you.

You won't see further works from me. I'll also stop communicating to the
maintainers. My work doesn't seem of interest to you. I really don't think
we'll get anywhere with this attitude. If it's about names, be glad to
have an accepted name. I like mine.

Have fun.

			Thunder