Re: type safe lists (was Re: PATCH: type safe(r) list_entry repacement: generic_out_cast)

Re: type safe lists (was Re: PATCH: type safe(r) list_entry repacement: generic_out_cast)

[Andi Kleen]

> 
> As long as your pointers are 32bit this seems to be ok. But on 
> 64bit implementations pointers are not (unsigned long) so this cast 
> seems to be wrong.

A pointer fits into unsigned long on all 64bit linux ports.
The kernel very heavily relies on that.

You are probably thinking of Win64, but this is not Windows.

-Andi

Re: type safe lists (was Re: PATCH: type safe(r) list_entry repacement: generic_out_cast)

[Linus Torvalds]

In article <p73d6tdtg2s.fsf@oldwotan.suse.de>, Andi Kleen  <ak@suse.de> wrote:
>> 
>> As long as your pointers are 32bit this seems to be ok. But on 
>> 64bit implementations pointers are not (unsigned long) so this cast 
>> seems to be wrong.
>
>A pointer fits into unsigned long on all 64bit linux ports.
>The kernel very heavily relies on that.

Not just the kernel, afaik.  I think it's rather tightly integrated into
gcc internals too (ie pointers are eventually just converted to SI
inside the compiler, and making a non-SI pointer would be hard). 

			Linus

Re: type safe lists (was Re: PATCH: type safe(r) list_entry repacement: generic_out_cast)

[Jamie Lokier]

Linus Torvalds wrote:
> >> As long as your pointers are 32bit this seems to be ok. But on 
> >> 64bit implementations pointers are not (unsigned long) so this cast 
> >> seems to be wrong.
> >
> >A pointer fits into unsigned long on all 64bit linux ports.
> >The kernel very heavily relies on that.
> 
> Not just the kernel, afaik.  I think it's rather tightly integrated into
> gcc internals too (ie pointers are eventually just converted to SI
> inside the compiler, and making a non-SI pointer would be hard). 

That can't be the case, as how would GCC represent 64-bit pointers on
platforms like the Alpha, which support 64-bit, 32-bit, 16-bit and 8-bit
types?  64-bits must be DImode simply because QImode is the smallest
mode, and required for the 8-bit type.

-- Jamie

Re: PATCH: type safe(r) list_entry repacement: generic_out_cast

[Jakob Oestergaard]

On Tue, Jul 23, 2002 at 09:28:26PM +1000, Neil Brown wrote:
> 
...
> Why "out_cast"???
> 
> Well OO people would probably call it a "down cast" as you are
> effectively casting from a more-general type to a less-general (more
> specific) type that is there-fore lower on the type latice.
> So maybe it should be "generic_down_cast".
> But seeing that one is casting from an embeded internal structure to a
> containing external structure, "out_cast" seemed a little easier to
> intuitively understand.

This is one of the type issues that C++ would solve nicely - not because
of OO, but because of parameterized types.  Completely removing the need
to do any kind of casting (in this situation), and allowing the compiler
to inline based on the actual use of types in each specific
instantiation of a function such as a list utility funciton.  Type safe
code that runs faster, yay!.

Yes, I know, it doesn't help us one bit here, because they'll be selling
snow-cones in hell before the kernel is rewritten in C++.  And there are
many good reasons why it is like that.

I'm happy to see someone taking an initiative to improve type safety (as
much as the language allows).  And the above was just pointed out
because of the occational "why not C++" versus "no OO sucks" (as if C++
was just OO) debates.

Cheers,

-- 
................................................................
:   jakob@unthought.net   : And I see the elder races,         :
:.........................: putrid forms of man                :
:   Jakob Østergaard      : See him rise and claim the earth,  :
:        OZ9ABN           : his downfall is at hand.           :
:.........................:............{Konkhra}...............:

type safe lists (was Re: PATCH: type safe(r) list_entry repacement: generic_out_cast)

[Joshua MacDonald]

On Tue, 23 Jul 2002 13:47:03 +0200, Jakob Oestergaard wrote:
> 
> On Tue, Jul 23, 2002 at 09:28:26PM +1000, Neil Brown wrote:
> > 
> ...
> > Why "out_cast"???
> > 
> > Well OO people would probably call it a "down cast" as you are
> > effectively casting from a more-general type to a less-general (more
> > specific) type that is there-fore lower on the type latice.
> > So maybe it should be "generic_down_cast".
> > But seeing that one is casting from an embeded internal structure to a
> > containing external structure, "out_cast" seemed a little easier to
> > intuitively understand.
> 
> This is one of the type issues that C++ would solve nicely - not because
> of OO, but because of parameterized types.  Completely removing the need
> to do any kind of casting (in this situation), and allowing the compiler
> to inline based on the actual use of types in each specific
> instantiation of a function such as a list utility funciton.  Type safe
> code that runs faster, yay!.
> 
> Yes, I know, it doesn't help us one bit here, because they'll be selling
> snow-cones in hell before the kernel is rewritten in C++.  And there are
> many good reasons why it is like that.
> 
> I'm happy to see someone taking an initiative to improve type safety (as
> much as the language allows).  And the above was just pointed out
> because of the occational "why not C++" versus "no OO sucks" (as if C++
> was just OO) debates.

Jakob,

This may interest you.  We have written a type-safe doubly-linked list
template which is used extensively in reiser4.  This is the kind of thing that
some people like very much and some people hate, so I'll spare you the
advocacy.

Hans has asked me to submit this for l-k review, since it is part of reiser4,
and I have attached our code.

And while on the subject of type-safety and templates, I will repeat a message
I sent to l-k some time ago:

<include/linux/ghash.h> is a sorry piece of broken, ugly, undocumented generic
hash-table code that has been sitting in the kernel source for a long time
wasting everyone's resources.  Need I say more?  It doesn't compile, and
nothing uses it.  There's one for the trivial patchbot.

Its a fair idea, extending this type-safe template idea to hash tables, except
there are a lot more ways to build a hash table.  We have a similar type-safe
hash template in reiser4 but we have not found it extremely useful and
definetly not at all generic.

Comments are welcome.

-josh

> Cheers,
> 
> -- 
> ................................................................
> :   jakob@unthought.net   : And I see the elder races,         :
> :.........................: putrid forms of man                :
> :   Jakob Østergaard      : See him rise and claim the earth,  :
> :        OZ9ABN           : his downfall is at hand.           :
> :.........................:............{Konkhra}...............:

/* Copyright (C) 2001, 2002 Hans Reiser.  All rights reserved.
 */

#ifndef __REISER4_TSLIST_H__
#define __REISER4_TSLIST_H__

/* A circular doubly linked list that differs from the previous
 * <linux/list.h> implementation because it is parametrized to provide
 * type safety.  This data structure is also useful as a queue or stack.
 *
 * The "list template" consists of a set of types and methods for
 * implementing list operations.  All of the types and methods
 * associated with a single list class are assigned unique names and
 * type signatures, thus allowing the compiler to verify correct
 * usage.
 *
 * The first parameter of a list class is the item type being stored
 * in the list.  The list class maintains two pointers within each
 * item structure for its "next" and "prev" pointers.
 *
 * There are two structures associated with the list, in addition to
 * the item type itself.  The "list link" contains the two pointers
 * that are embedded within the item itself.  The "list head" also
 * contains two pointers which refer to the first item ("front") and
 * last item ("back") of the list.
 *
 * The list maintains a "circular" invariant, in that you can always
 * begin at the front and follow "next" pointers until eventually you
 * reach the same point.  The "list head" is included within the
 * cycle, even though it does not have the correct item type.  The
 * "list head" and "list link" types are different objects from the
 * user's perspective, but the core algorithms that operate on this
 * style of list treat the "list head" and "list link" as identical
 * types.  That is why these algorithms are so simple.
 *
 * The <linux/list.h> implementation uses the same algorithms as those
 * in this file but uses only a single type "struct list_head".  There
 * are two problems with this approach.  First, there are no type
 * distinctions made between the two objects despite their distinct
 * types, which greatly increases the possibility for mistakes.  For
 * example, the <linux/list.h> list_add function takes two "struct
 * list_head" arguments: the first is the item being inserted and the
 * second is the "struct list_head" which should precede the new
 * insertion to the list.  You can use this function to insert at any
 * point in the list, but by far the most common list operations are
 * to insert at the front or back of the list.  This common case
 * should accept two different argument types: a "list head" and an
 * "item", this allows for no confusion.
 *
 * The second problem with using a single "struct list_head" is that
 * it does not distinguish between list objects of distinct list
 * classes.  If a single item can belong to two separate lists, there
 * is easily the possibility of a mistake being made that causes the
 * item to be added to a "list head" using the wrong "list link".  By
 * using a parametrized list class we can statically detect such
 * mistakes, detecting mistakes as soon as they happen.
 *
 * To create a new list class takes several steps which are described
 * below.  Suppose for this example that you would like to link
 * together items of type "rx_event".  You should decide on
 * prefix-name to be used on all list functions and structures.  For
 * example, the string "rx_event" can be as a prefix for all the list
 * operations, resulting in a "list head" named rx_event_list_head and
 * a "list link" named rx_event_list_link.  The list operations on
 * this list class would be named "rx_event_list_empty",
 * "rx_event_list_init", "rx_event_list_push_front",
 * "rx_event_list_push_back", and so on.
 */

#define TS_LIST_LINK_INIT( name ) { &(name), &(name) }
#define TS_LIST_HEAD_INIT( name ) { &(name), &(name) }
#define TS_LIST_LINK_ZERO { NULL, NULL }
#define TS_LIST_HEAD_ZERO { NULL, NULL }

#define TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,LINK) \
	((ITEM_TYPE *)((char *)(LINK)-(unsigned long)(&((ITEM_TYPE *)0)->LINK_NAME)))

/* Step 1: Use the TS_LIST_DECLARE() macro to define the "list head"
 * and "list link" objects.  This macro takes one arguments, the
 * prefix-name, which is prepended to every structure and function
 * name of the list class.  Following the example, this will create
 * types named rx_event_list_head and rx_event_list_link.  In the
 * example you would write:
 *
 * TS_LIST_DECLARE(rx_event);
 *
 */
#define TS_LIST_DECLARE(PREFIX)                                                               \
                                                                                              \
typedef struct _##PREFIX##_list_head        PREFIX##_list_head;                               \
typedef struct _##PREFIX##_list_link        PREFIX##_list_link;                               \
                                                                                              \
struct _##PREFIX##_list_link                                                                  \
{                                                                                             \
  PREFIX##_list_link *_next;                                                                  \
  PREFIX##_list_link *_prev;                                                                  \
};                                                                                            \
                                                                                              \
struct _##PREFIX##_list_head                                                                  \
{                                                                                             \
  PREFIX##_list_link *_next;                                                                  \
  PREFIX##_list_link *_prev;                                                                  \
}

/* Step 2: Once you have defined the two list classes, you should
 * define the item type you intend to use.  The list classes must be
 * declared before the item type because the item type must contain an
 * embedded "list link" object.  Following the example, you might define
 * rx_event as follows:
 *
 * typedef struct _rx_event  rx_event;
 *
 * struct _rx_event
 * {
 *   ... other members ...
 *
 *   rx_event_list_link  _link;
 * };
 *
 * In this case we have given the rx_event a field named "_link" of
 * the appropriate type.
 */

/* Step 3: The final step will define the list-functions for a
 * specific list class using the macro TS_LIST_DEFINE.  There are
 * three arguments to the TS_LIST_DEFINE macro: the prefix-name, the
 * item type name, and field name of the "list link" element within
 * the item type.  In the above example you would supply "rx_event" as
 * the type name and "_link" as the field name (without quotes).
 * E.g.,
 *
 * TS_LIST_DEFINE(rx_event,rx_event,_link)
 *
 * The list class you define is now complete with the functions:
 *
 * rx_event_list_init             Initialize a list_head
 * rx_event_list_clean            Initialize a list_link
 * rx_event_list_is_clean         True if list_link is not in a list
 * rx_event_list_push_front       Insert to the front of the list
 * rx_event_list_push_back        Insert to the back of the list
 * rx_event_list_insert_before    Insert just before given item in the list
 * rx_event_list_insert_after     Insert just after given item in the list
 * rx_event_list_remove           Remove an item from anywhere in the list
 * rx_event_list_remove_clean     Remove an item from anywhere in the list and clean link_item
 * rx_event_list_remove_get_next  Remove an item from anywhere in the list and return the next element
 * rx_event_list_remove_get_prev  Remove an item from anywhere in the list and return the prev element
 * rx_event_list_pop_front        Remove and return the front of the list, cannot be empty
 * rx_event_list_pop_back         Remove and return the back of the list, cannot be empty
 * rx_event_list_front            Get the front of the list
 * rx_event_list_back             Get the back of the list
 * rx_event_list_next             Iterate front-to-back through the list
 * rx_event_list_prev             Iterate back-to-front through the list
 * rx_event_list_end              Test to end an iteration, either direction
 * rx_event_list_splice           Join two lists at the head
 * rx_event_list_empty            True if the list is empty
 * rx_event_list_object_ok        Check that list element satisfies double 
 *                                list invariants. For debugging.
 *
 * To iterate over such a list use a for-loop such as:
 *
 *   rx_event_list_head *head = ...;
 *   rx_event *item;
 *
 *   for (item = rx_event_list_front (head);
 *             ! rx_event_list_end   (head, item);
 *        item = rx_event_list_next  (item))
 *     {...}
 * */
#define TS_LIST_DEFINE(PREFIX,ITEM_TYPE,LINK_NAME)                                            \
                                                                                              \
static __inline__ int                                                                         \
PREFIX##_list_link_invariant (PREFIX##_list_link  *_link)                                     \
{                                                                                             \
  return (_link != NULL) &&                                                                   \
	  (_link->_prev != NULL) && (_link->_next != NULL ) &&                                \
	  (_link->_prev->_next == _link) &&                                                   \
	  (_link->_next->_prev == _link);                                                     \
}                                                                                             \
                                                                                              \
static __inline__ void                                                                        \
PREFIX##_list_link_ok (PREFIX##_list_link  *_link UNUSED_ARG)                                 \
{                                                                                             \
  assert ("nikita-1054", PREFIX##_list_link_invariant (_link));                               \
}                                                                                             \
                                                                                              \
static __inline__ void                                                                        \
PREFIX##_list_object_ok (ITEM_TYPE           *item)                                           \
{                                                                                             \
  PREFIX##_list_link_ok (&item->LINK_NAME);                                                   \
}                                                                                             \
                                                                                              \
static __inline__ void                                                                        \
PREFIX##_list_init (PREFIX##_list_head  *head)                                                \
{                                                                                             \
  head->_next = (PREFIX##_list_link*) head;                                                   \
  head->_prev = (PREFIX##_list_link*) head;                                                   \
}                                                                                             \
                                                                                              \
static __inline__ void                                                                        \
PREFIX##_list_clean (ITEM_TYPE           *item)                                               \
{                                                                                             \
  PREFIX##_list_link *_link = &item->LINK_NAME;                                               \
                                                                                              \
  _link->_next = _link;                                                                       \
  _link->_prev = _link;                                                                       \
}                                                                                             \
                                                                                              \
static __inline__ int                                                                         \
PREFIX##_list_is_clean (ITEM_TYPE           *item)                                            \
{                                                                                             \
  PREFIX##_list_link *_link = &item->LINK_NAME;                                               \
                                                                                              \
  PREFIX##_list_link_ok (_link);                                                              \
  return (_link == _link->_next) && (_link == _link->_prev);                                  \
}                                                                                             \
                                                                                              \
static __inline__ void                                                                        \
PREFIX##_list_insert_int (PREFIX##_list_link  *next,                                          \
	 		         PREFIX##_list_link  *item)                                   \
{                                                                                             \
  PREFIX##_list_link *prev = next->_prev;                                                     \
  PREFIX##_list_link_ok (next);                                                               \
  PREFIX##_list_link_ok (prev);                                                               \
  next->_prev = item;                                                                         \
  item->_next = next;                                                                         \
  item->_prev = prev;                                                                         \
  prev->_next = item;                                                                         \
  PREFIX##_list_link_ok (next);                                                               \
  PREFIX##_list_link_ok (prev);                                                               \
  PREFIX##_list_link_ok (item);                                                               \
}                                                                                             \
                                                                                              \
static __inline__ void                                                                        \
PREFIX##_list_push_front (PREFIX##_list_head  *head,                                          \
			  ITEM_TYPE           *item)                                          \
{                                                                                             \
  PREFIX##_list_insert_int (head->_next, & item->LINK_NAME);                                  \
}                                                                                             \
                                                                                              \
static __inline__ void                                                                        \
PREFIX##_list_push_back (PREFIX##_list_head  *head,                                           \
			 ITEM_TYPE           *item)                                           \
{                                                                                             \
  PREFIX##_list_insert_int ((PREFIX##_list_link *) head, & item->LINK_NAME);                  \
}                                                                                             \
                                                                                              \
static __inline__ void                                                                        \
PREFIX##_list_insert_before (ITEM_TYPE         *reference,                                    \
			   ITEM_TYPE           *item)                                         \
{                                                                                             \
  PREFIX##_list_insert_int (& reference->LINK_NAME, & item->LINK_NAME);                       \
}                                                                                             \
                                                                                              \
static __inline__ void                                                                        \
PREFIX##_list_insert_after (ITEM_TYPE         *reference,                                     \
			  ITEM_TYPE           *item)                                          \
{                                                                                             \
  PREFIX##_list_insert_int (reference->LINK_NAME._next, & item->LINK_NAME);                   \
}                                                                                             \
                                                                                              \
static __inline__ PREFIX##_list_link*                                                         \
PREFIX##_list_remove_int (PREFIX##_list_link *list_link)                                      \
{                                                                                             \
  PREFIX##_list_link *next = list_link->_next;                                                \
  PREFIX##_list_link *prev = list_link->_prev;                                                \
  PREFIX##_list_link_ok (list_link);                                                          \
  PREFIX##_list_link_ok (next);                                                               \
  PREFIX##_list_link_ok (prev);                                                               \
  next->_prev = prev;                                                                         \
  prev->_next = next;                                                                         \
  PREFIX##_list_link_ok (next);                                                               \
  PREFIX##_list_link_ok (prev);                                                               \
  return list_link;                                                                           \
}                                                                                             \
                                                                                              \
static __inline__ void                                                                        \
PREFIX##_list_remove (ITEM_TYPE  *item)                                                       \
{                                                                                             \
  PREFIX##_list_remove_int (& item->LINK_NAME);                                               \
}                                                                                             \
                                                                                              \
static __inline__ void                                                                        \
PREFIX##_list_remove_clean (ITEM_TYPE  *item)                                                 \
{                                                                                             \
  PREFIX##_list_remove_int (& item->LINK_NAME);                                               \
  PREFIX##_list_clean (item);                                                                 \
}                                                                                             \
                                                                                              \
static __inline__ ITEM_TYPE*                                                                  \
PREFIX##_list_remove_get_next (ITEM_TYPE  *item)                                              \
{                                                                                             \
  PREFIX##_list_link *next = item->LINK_NAME._next;                                           \
  PREFIX##_list_remove_int (& item->LINK_NAME);                                               \
  return TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,next);                                           \
}                                                                                             \
                                                                                              \
static __inline__ ITEM_TYPE*                                                                  \
PREFIX##_list_remove_get_prev (ITEM_TYPE  *item)                                              \
{                                                                                             \
  PREFIX##_list_link *prev = item->LINK_NAME._prev;                                           \
  PREFIX##_list_remove_int (& item->LINK_NAME);                                               \
  return TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,prev);                                           \
}                                                                                             \
                                                                                              \
static __inline__ int                                                                         \
PREFIX##_list_empty (const PREFIX##_list_head  *head)                                         \
{                                                                                             \
  return head == (PREFIX##_list_head*) head->_next;                                           \
}                                                                                             \
                                                                                              \
static __inline__ ITEM_TYPE*                                                                  \
PREFIX##_list_pop_front (PREFIX##_list_head  *head)                                           \
{                                                                                             \
  assert ("nikita-1913", ! PREFIX##_list_empty (head));                                       \
  return TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,PREFIX##_list_remove_int (head->_next));         \
}                                                                                             \
                                                                                              \
static __inline__ ITEM_TYPE*                                                                  \
PREFIX##_list_pop_back (PREFIX##_list_head  *head)                                            \
{                                                                                             \
  assert ("nikita-1914", ! PREFIX##_list_empty (head)); /* WWI started */                     \
  return TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,PREFIX##_list_remove_int (head->_prev));         \
}                                                                                             \
                                                                                              \
static __inline__ ITEM_TYPE*                                                                  \
PREFIX##_list_front (const PREFIX##_list_head  *head)                                         \
{                                                                                             \
  return TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,head->_next);                                    \
}                                                                                             \
                                                                                              \
static __inline__ ITEM_TYPE*                                                                  \
PREFIX##_list_back (const PREFIX##_list_head  *head)                                          \
{                                                                                             \
  return TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,head->_prev);                                    \
}                                                                                             \
                                                                                              \
static __inline__ ITEM_TYPE*                                                                  \
PREFIX##_list_next (const ITEM_TYPE *item)                                                    \
{                                                                                             \
  return TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,item->LINK_NAME._next);                          \
}                                                                                             \
                                                                                              \
static __inline__ ITEM_TYPE*                                                                  \
PREFIX##_list_prev (const ITEM_TYPE *item)                                                    \
{                                                                                             \
  return TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,item->LINK_NAME._prev);                          \
}                                                                                             \
                                                                                              \
static __inline__ int                                                                         \
PREFIX##_list_end (const PREFIX##_list_head  *head,                                           \
 		   const ITEM_TYPE           *item)                                           \
{                                                                                             \
  return ((PREFIX##_list_link *) head) == (& item->LINK_NAME);                                \
}                                                                                             \
                                                                                              \
static __inline__ void                                                                        \
PREFIX##_list_splice (PREFIX##_list_head  *head_join,                                         \
 		      PREFIX##_list_head  *head_empty)                                        \
{                                                                                             \
  if (PREFIX##_list_empty (head_empty)) {                                                     \
    return;                                                                                   \
  }                                                                                           \
                                                                                              \
  head_empty->_prev->_next = (PREFIX##_list_link*) head_join;                                 \
  head_empty->_next->_prev = head_join->_prev;                                                \
                                                                                              \
  head_join->_prev->_next  = head_empty->_next;                                               \
  head_join->_prev         = head_empty->_prev;                                               \
                                                                                              \
  PREFIX##_list_link_ok ((PREFIX##_list_link*) head_join);                                    \
  PREFIX##_list_link_ok (head_join->_prev);                                                   \
  PREFIX##_list_link_ok (head_join->_next);                                                   \
                                                                                              \
  PREFIX##_list_init (head_empty);                                                            \
}                                                                                             \
                                                                                              \
static __inline__ void                                                                        \
PREFIX##_list_check (PREFIX##_list_head  *head)                                               \
{                                                                                             \
	PREFIX##_list_link *link;                                                             \
                                                                                              \
	for (link = head->_next ; link != ((PREFIX##_list_link *) head) ; link = link->_next) \
		PREFIX##_list_link_ok (link);                                                 \
}                                                                                             \
                                                                                              \
typedef struct { int foo; } PREFIX##_dummy_decl

/* The final typedef is to allow a semicolon at the end of TS_LIST_DEFINE(); */

#endif /* __REISER4_TSLIST_H__ */

/*
 * Local variables:
 * c-indentation-style: "K&R"
 * mode-name: "LC"
 * c-basic-offset: 8
 * tab-width: 8
 * fill-column: 120
 * End:
 */

Re: type safe lists (was Re: PATCH: type safe(r) list_entry repacement: generic_out_cast)

[Martin Brulisauer]

On 24 Jul 2002, at 2:07, Joshua MacDonald wrote:
> 
> This may interest you.  We have written a type-safe doubly-linked list
> template which is used extensively in reiser4.  This is the kind of thing that
> some people like very much and some people hate, so I'll spare you the
> advocacy.
> 
> Comments are welcome.

Hi,

In my oppinion the attached template is a very good school 
example of how to excessively use C-style macros. But macros 
tend to make debugging difficult and as you know every new code 
has bugs (if it seems not to have one, then it has at least two 
which "correct" each other until you fix one of them ...), and finding 
the bugs is mainly done by others. 

And who needs a "type-save" template for such a trivial thing like a 
dubbly-linked-list? If this is not buttom-line knowledge one should 
not try to do kernel level programming. By the way: Multiline C 
Macros are depreached and will not be supported by a future 
version of gcc and as for today will generate a bunch of warnings.

I have one additional comment to the current implementation:
> 
> #define TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,LINK) \
> 	((ITEM_TYPE *)((char *)(LINK)-(unsigned long)(&((ITEM_TYPE *)0)->LINK_NAME)))

As long as your pointers are 32bit this seems to be ok. But on 
64bit implementations pointers are not (unsigned long) so this cast 
seems to be wrong.

Regards,
Martin

Re: type safe lists (was Re: PATCH: type safe(r) list_entry repacement: generic_out_cast)

[Anton Altaparmakov]

At 08:39 24/07/02, Martin Brulisauer wrote:
>On 24 Jul 2002, at 2:07, Joshua MacDonald wrote:
>I have one additional comment to the current implementation:
> >
> > #define TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,LINK) \
> >       ((ITEM_TYPE *)((char *)(LINK)-(unsigned long)(&((ITEM_TYPE 
> *)0)->LINK_NAME)))
>
>As long as your pointers are 32bit this seems to be ok. But on
>64bit implementations pointers are not (unsigned long) so this cast
>seems to be wrong.

On 64-bit architectures unsigned long is 64-bits so there is no problem. In 
fact the core kernel code _requires_ that unsigned long is large enough to 
fully contain the contents of a pointer. (E.g. look at linux/mm/memory.c, 
well really linux/mm/*.c for the tip of the iceberg).

Of course if one wanted to be really pedantic, one could replace the 
unsigned long typecasts with ptrdiff_t. But you would have to go through a 
_lot_ of code where the kernel currently casts between unsigned long and 
(mostly) void * to do this in a one off conversion.

Best regards,

         Anton


-- 
   "I've not lost my mind. It's backed up on tape somewhere." - Unknown
-- 
Anton Altaparmakov <aia21 at cantab.net> (replace at with @)
Linux NTFS Maintainer / IRC: #ntfs on irc.openprojects.net
WWW: http://linux-ntfs.sf.net/ & http://www-stu.christs.cam.ac.uk/~aia21/

Re: type safe lists (was Re: PATCH: type safe(r) list_entry repacement: generic_out_cast)

[Joshua MacDonald]

On Wed, Jul 24, 2002 at 09:39:53AM +0200, Martin Brulisauer wrote:
> On 24 Jul 2002, at 2:07, Joshua MacDonald wrote:
> > 
> > This may interest you.  We have written a type-safe doubly-linked list
> > template which is used extensively in reiser4.  This is the kind of thing that
> > some people like very much and some people hate, so I'll spare you the
> > advocacy.
> > 
> > Comments are welcome.
> 
> Hi,
> 
> In my oppinion the attached template is a very good school 
> example of how to excessively use C-style macros. But macros 
> tend to make debugging difficult and as you know every new code 
> has bugs (if it seems not to have one, then it has at least two 
> which "correct" each other until you fix one of them ...), and finding 
> the bugs is mainly done by others. 
>
> And who needs a "type-save" template for such a trivial thing like a 
> dubbly-linked-list? If this is not buttom-line knowledge one should 
> not try to do kernel level programming. By the way: Multiline C 
> Macros are depreached and will not be supported by a future 
> version of gcc and as for today will generate a bunch of warnings.

The list code is trivial, but when you have 10 classes of list and no type
safety between independent list classes or even between the list head and list
item types, there is a strong possibility you will pass the wrong argument to
some list routine because there is nothing to stop you.

The list code is trivial.  It doesn't make debugging difficult.  It is
bottom-line knowledge.  But why make things difficult for yourself -- just to
prove you can?

I can say a lot of good and bad things about C++, but at least it lets you do
this kind of thing with type safety and without ugly macros.

> I have one additional comment to the current implementation:
> > 
> > #define TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,LINK) \
> > 	((ITEM_TYPE *)((char *)(LINK)-(unsigned long)(&((ITEM_TYPE *)0)->LINK_NAME)))
> 
> As long as your pointers are 32bit this seems to be ok. But on 
> 64bit implementations pointers are not (unsigned long) so this cast 
> seems to be wrong.

-josh

Re: type safe lists (was Re: PATCH: type safe(r) list_entry repacement: generic_out_cast)

[Martin Brulisauer]

On 24 Jul 2002, at 13:56, Joshua MacDonald wrote:
> The list code is trivial, but when you have 10 classes of list and no type
> safety between independent list classes or even between the list head and list
> item types, there is a strong possibility you will pass the wrong argument to
> some list routine because there is nothing to stop you.
So it is.

At kernel level nothing will stop me to halt() the cpu, if I realy want 
to. It is important to understand that tools (and all compilers are
just tools) will not enable me to write correct code. 
> 
> I can say a lot of good and bad things about C++, but at least it lets you do
> this kind of thing with type safety and without ugly macros.
> 
Yes. That's absolutely true for C++. But the kernel is implemented 
in C and C is "only" kind of a high-level-assembler language. It is
ment to be open - on purpose. There exist other languages that 
have these kinds of concepts you bring in (I would not use C++ as 
the best example - take OBERON/MODULA or EIFFEL). But these 
languages are not made to implement an operating system 
(remember the reason K&R have specified and implemented C?).

What I realy dislike is the approach to bring in any OO concepts 
into the C language the linux kernel bases on. Keep the code as 
simple and homogenous as possible (or try to rewrite it in OO).

The way I see this discussion is: Every software problem has it's 
proper language to be solved in. And for this, Linus decided it to be 
C.

Regards,
Martin

Re: type safe lists (was Re: PATCH: type safe(r) list_entry repacement: generic_out_cast)

[Jakob Oestergaard]

On Wed, Jul 24, 2002 at 12:50:28PM +0200, Martin Brulisauer wrote:
...
> So it is.
> 
> At kernel level nothing will stop me to halt() the cpu, if I realy want 
> to. It is important to understand that tools (and all compilers are
> just tools) will not enable me to write correct code. 

That is a lame argument.

We've just seen that very competent people can make really silly
mistakes because of generic code without type safety.

*IF* the code had type safety, such silly mistakes would be caught at
compile time.

Now there are arguments for and against implementations such as the type
safe list implementation.  But an argument against type-safety is
rediculous.  If the language does not allow for type safety in any
convenient manner, so be it, but type-safety really is useful for
avoiding silly mistakes, and this should be exploited whenever the
language (and clever *use* of the language) allows for it.

> > 
> > I can say a lot of good and bad things about C++, but at least it lets you do
> > this kind of thing with type safety and without ugly macros.
> > 
> Yes. That's absolutely true for C++. But the kernel is implemented 
> in C and C is "only" kind of a high-level-assembler language. It is

No, C has types.  It is not just portable assembly.

Why do you think it allows for typed pointers and not just void* or
even long?

> ment to be open - on purpose. There exist other languages that 
> have these kinds of concepts you bring in (I would not use C++ as 
> the best example - take OBERON/MODULA or EIFFEL). But these 
> languages are not made to implement an operating system 
> (remember the reason K&R have specified and implemented C?).

Wrong.  Look at Atheos for an example.  There is *nothing* you can do in
C that you cannot do in C++ with equal or better performance (there is C
code that is not valid C++, but it's small semantic details and scope
rules, re-writing is simple).

But this is of course irrelevant, as there are other good reasons for
not rewriting the kernel in any other language.

> 
> What I realy dislike is the approach to bring in any OO concepts 
> into the C language the linux kernel bases on. Keep the code as 
> simple and homogenous as possible (or try to rewrite it in OO).

Who is talking about OO ???

What Joshua presented is a C implementation of a list using
parameterized types using macros (instead of templates as could have
been used in C++).  Parameterized types has nothing what so ever in any
way to do with OO  (it goes well with some OO concepts, but that's an
entirely different story).

> 
> The way I see this discussion is: Every software problem has it's 
> proper language to be solved in. And for this, Linus decided it to be 
> C.

Yes. And I think that was a very clever decision - even if there had
been proper C++ compilers at the time (which there wan't, because the
language wasn't even standardized until 1998).

But did Linus decide to use "crappy C" or "error-prone C", or is there
some chance that the most generic code could perhaps be implemented in
"robust C" ?

Macros are not a pretty solution, but it is as I see it the only way to
achieve type safety in generic code.  If someone else out there has
other suggestions, please let me know - I actually like to be proven
wrong (because that means I learn something new).

I'd take macro-hell in generic code over void* hell in every single
list-using part of the kernel any day.

-- 
................................................................
:   jakob@unthought.net   : And I see the elder races,         :
:.........................: putrid forms of man                :
:   Jakob Østergaard      : See him rise and claim the earth,  :
:        OZ9ABN           : his downfall is at hand.           :
:.........................:............{Konkhra}...............:

Re: type safe lists (was Re: PATCH: type safe(r) list_entry repacement: generic_out_cast)

[John Alvord]

On Wed, 24 Jul 2002 13:58:50 +0200, Jakob Oestergaard
<jakob@unthought.net> wrote:

>On Wed, Jul 24, 2002 at 12:50:28PM +0200, Martin Brulisauer wrote:
>...
>> So it is.
>> 
>> At kernel level nothing will stop me to halt() the cpu, if I realy want 
>> to. It is important to understand that tools (and all compilers are
>> just tools) will not enable me to write correct code. 
>
>That is a lame argument.
......
>Macros are not a pretty solution, but it is as I see it the only way to
>achieve type safety in generic code.  If someone else out there has
>other suggestions, please let me know - I actually like to be proven
>wrong (because that means I learn something new).
>
>I'd take macro-hell in generic code over void* hell in every single
>list-using part of the kernel any day.

There was a similar flare-up about a year ago when type safety was
added to the min and max macros. The initial implementation was a bit
strange, but the final one used some gcc-ism and now no one complains.

john alvord

Re: type safe lists (was Re: PATCH: type safe(r) list_entry repacement: generic_out_cast)

[Greg KH]

On Wed, Jul 24, 2002 at 09:39:53AM +0200, Martin Brulisauer wrote:
> By the way: Multiline C Macros are depreached and will not be
> supported by a future version of gcc and as for today will generate a
> bunch of warnings.

Why is this?  Is it a C99 requirement?

thanks,

greg k-h

Re: type safe lists (was Re: PATCH: type safe(r) list_entry repacement: generic_out_cast)

[Roland Dreier]

    Martin> By the way: Multiline C Macros are depreached and will not
    Martin> be supported by a future version of gcc and as for today
    Martin> will generate a bunch of warnings.

    Greg> Why is this?  Is it a C99 requirement?

I'm not sure what Martin is talking about here.  I'm sure that
multiline macros are part of standard C.  The second translation phase
(immediately after character set mapping but _before_ preprocessing)
deletes any occurrences of \ followed by a newline.  The preprocessor
should not behave differently if a macro definition is broken up with \'s.

The copy of the ISO C standard that I have (the August 3, 1998 draft)
even has an example of a macro with a multiline definition in the
section on macro replacement.

I really doubt that gcc will break this standards-compliant,
extensively-used behavior.  Perhaps I misunderstood Martin but I don't
think there was anything wrong syntactically with the list macros
posted earlier.

Best,
  Roland

Re: type safe lists (was Re: PATCH: type safe(r) list_entry repacement: generic_out_cast)

[Alexander Kellett]

On Wed, Jul 24, 2002 at 10:29:57PM -0700, Greg KH wrote:
> On Wed, Jul 24, 2002 at 09:39:53AM +0200, Martin Brulisauer wrote:
> > By the way: Multiline C Macros are depreached and will not be
> > supported by a future version of gcc and as for today will generate a
> > bunch of warnings.
> 
> Why is this?  Is it a C99 requirement?

afaik its multi line strings that have been deprecated.

Alex

Re: type safe lists (was Re: PATCH: type safe(r) list_entry repacement: generic_out_cast)

[DervishD]

    Hi Alexander and Greg :)

>> > By the way: Multiline C Macros are depreached and will not be
>> Why is this?  Is it a C99 requirement?
>afaik its multi line strings that have been deprecated.

    Multiline C macros are not deprecated. In fact, there is nothing
such as 'multiline macros'. Multiline macros are built using the C
escape character, no more, no less, that makes the preprocesor to
ignore the carriage returns.

    Really it's multi line string literals that have been deprecated.

    Raúl

Re: type safe lists (was Re: PATCH: type safe(r) list_entry repacement: generic_out_cast)

[Jakob Oestergaard]

On Wed, Jul 24, 2002 at 02:07:45AM +0400, Joshua MacDonald wrote:
...
> This may interest you.  We have written a type-safe doubly-linked list
> template which is used extensively in reiser4.  This is the kind of thing that
> some people like very much and some people hate, so I'll spare you the
> advocacy.

Ok, here's my comments:

*) Using macros like that is ugly as hell, but as I see it it is the
only way to achieve type safety in such generic code.  If the ugliness
is confined to one header file, and possibly one .c file containing the
needed instantiations, I would argue that the ugliness is bearable.  In
other words, I think your solution is the prettiest one possible.

Since all list routines right now are extremely simple, it's probably ok
to just have it all in a header. If larger routines are added later on,
it may be desirable to create a .c file holding the needed (macro
instantiated) routines. In that case, the following applies:

*) I would suggest making one list_instances.c which holds all the
INSTANTIATE... definitions of the list types needed in the kernel. This
way we will avoid having two list codes generated for the same type (an
easy accident to make with the macro approach)
*) You would have to somehow separate the "simple" routines which should
be inlined, and the larger ones which should remain function calls. This
would mean that a .c file using the list header would have the inline
functions declared in the list header (using static inline so unused
routines won't bloat the .o), and find it's larger out-of-line routines
in the global list .o.

The reason I'm suggesting doing the above instead of simply
instantiating a list implementation for each type needed, whenever it is
needed, is simply to avoid code bloat.

My only comment for the code would be to require that the link from the
element into the list would always be called "rx_list_backlink" or
whatever (if the list name is "rx_list") - the freedom you have in
specifying what the LINK_NAME is, is useless as I see it, and only adds
to the confusion.

-- 
................................................................
:   jakob@unthought.net   : And I see the elder races,         :
:.........................: putrid forms of man                :
:   Jakob Østergaard      : See him rise and claim the earth,  :
:        OZ9ABN           : his downfall is at hand.           :
:.........................:............{Konkhra}...............:

Re: type safe lists (was Re: PATCH: type safe(r) list_entry repacement: generic_out_cast)

[Joshua MacDonald]

On Wed, Jul 24, 2002 at 02:22:32PM +0200, Jakob Oestergaard wrote:
> On Wed, Jul 24, 2002 at 02:07:45AM +0400, Joshua MacDonald wrote:
> ...
> > This may interest you.  We have written a type-safe doubly-linked list
> > template which is used extensively in reiser4.  This is the kind of thing that
> > some people like very much and some people hate, so I'll spare you the
> > advocacy.
> 
> Ok, here's my comments:
> 
> *) Using macros like that is ugly as hell, but as I see it it is the
> only way to achieve type safety in such generic code.  If the ugliness
> is confined to one header file, and possibly one .c file containing the
> needed instantiations, I would argue that the ugliness is bearable.  In
> other words, I think your solution is the prettiest one possible.
> 
> Since all list routines right now are extremely simple, it's probably ok
> to just have it all in a header. If larger routines are added later on,
> it may be desirable to create a .c file holding the needed (macro
> instantiated) routines. In that case, the following applies:
> 
> *) I would suggest making one list_instances.c which holds all the
> INSTANTIATE... definitions of the list types needed in the kernel. This
> way we will avoid having two list codes generated for the same type (an
> easy accident to make with the macro approach)
> *) You would have to somehow separate the "simple" routines which should
> be inlined, and the larger ones which should remain function calls. This
> would mean that a .c file using the list header would have the inline
> functions declared in the list header (using static inline so unused
> routines won't bloat the .o), and find it's larger out-of-line routines
> in the global list .o.
> 
> The reason I'm suggesting doing the above instead of simply
> instantiating a list implementation for each type needed, whenever it is
> needed, is simply to avoid code bloat.
> 
> My only comment for the code would be to require that the link from the
> element into the list would always be called "rx_list_backlink" or
> whatever (if the list name is "rx_list") - the freedom you have in
> specifying what the LINK_NAME is, is useless as I see it, and only adds
> to the confusion.

Jakob,

These are fine suggestions.  The debug-only list invariants, the splice
function, and possibly others are definetly candidates for non-static-inline
inclusion.  A single list_instances.c file makes a lot of sense (except for
modules--maybe?), and you are right that LINK_NAME is basically useless.

Since this code is already part of reiser4, it is likely to be crititically
reviewed again when Hans begins his push.  I will fix the LINK_NAME issue and
change the reiser4-specific assert() calls to generic ones.  We welcome
feedback.

-josh


> -- 
> ................................................................
> :   jakob@unthought.net   : And I see the elder races,         :
> :.........................: putrid forms of man                :
> :   Jakob Østergaard      : See him rise and claim the earth,  :
> :        OZ9ABN           : his downfall is at hand.           :
> :.........................:............{Konkhra}...............:

Re: type safe lists (was Re: PATCH: type safe(r) list_entry repacement: generic_out_cast)

[Hans Reiser]

Joshua MacDonald wrote:

>On Wed, Jul 24, 2002 at 02:22:32PM +0200, Jakob Oestergaard wrote:
>  
>
>>On Wed, Jul 24, 2002 at 02:07:45AM +0400, Joshua MacDonald wrote:
>>...
>>    
>>
>>>This may interest you.  We have written a type-safe doubly-linked list
>>>template which is used extensively in reiser4.  This is the kind of thing that
>>>some people like very much and some people hate, so I'll spare you the
>>>advocacy.
>>>      
>>>
>>Ok, here's my comments:
>>
>>*) Using macros like that is ugly as hell, but as I see it it is the
>>only way to achieve type safety in such generic code.  If the ugliness
>>is confined to one header file, and possibly one .c file containing the
>>needed instantiations, I would argue that the ugliness is bearable.  In
>>other words, I think your solution is the prettiest one possible.
>>
>>Since all list routines right now are extremely simple, it's probably ok
>>to just have it all in a header. If larger routines are added later on,
>>it may be desirable to create a .c file holding the needed (macro
>>instantiated) routines. In that case, the following applies:
>>
>>*) I would suggest making one list_instances.c which holds all the
>>INSTANTIATE... definitions of the list types needed in the kernel. This
>>way we will avoid having two list codes generated for the same type (an
>>easy accident to make with the macro approach)
>>*) You would have to somehow separate the "simple" routines which should
>>be inlined, and the larger ones which should remain function calls. This
>>would mean that a .c file using the list header would have the inline
>>functions declared in the list header (using static inline so unused
>>routines won't bloat the .o), and find it's larger out-of-line routines
>>in the global list .o.
>>
>>The reason I'm suggesting doing the above instead of simply
>>instantiating a list implementation for each type needed, whenever it is
>>needed, is simply to avoid code bloat.
>>
>>My only comment for the code would be to require that the link from the
>>element into the list would always be called "rx_list_backlink" or
>>whatever (if the list name is "rx_list") - the freedom you have in
>>specifying what the LINK_NAME is, is useless as I see it, and only adds
>>to the confusion.
>>    
>>
>
>Jakob,
>
>These are fine suggestions.  The debug-only list invariants, the splice
>function, and possibly others are definetly candidates for non-static-inline
>inclusion.  A single list_instances.c file makes a lot of sense (except for
>modules--maybe?), and you are right that LINK_NAME is basically useless.
>
>Since this code is already part of reiser4, it is likely to be crititically
>reviewed again when Hans begins his push.  I will fix the LINK_NAME issue and
>change the reiser4-specific assert() calls to generic ones.  We welcome
>feedback.
>
>-josh
>
>
>  
>
>>-- 
>>................................................................
>>:   jakob@unthought.net   : And I see the elder races,         :
>>:.........................: putrid forms of man                :
>>:   Jakob Østergaard      : See him rise and claim the earth,  :
>>:        OZ9ABN           : his downfall is at hand.           :
>>:.........................:............{Konkhra}...............:
>>    
>>
>-
>To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
>the body of a message to majordomo@vger.kernel.org
>More majordomo info at  http://vger.kernel.org/majordomo-info.html
>Please read the FAQ at  http://www.tux.org/lkml/
>
>
>  
>
Linus prefers his patches in digestible bytes, so things that are also 
valuable to persons not coding reiser4, and are working/stable should be 
sent in earlier than reiser4 (as you have done with this list code).

Unfortunately the other things of value to others (transactions API, 
reiser4 syscall) are the least stable parts of our code at the moment, 
or we would send them in.

-- 
Hans