list.h has this nifty macro called list_entry that takes a pointer to a "struct
list_head" and "casts" that to a pointer to some structure that
contains the "struct list_head".
However it doesn't do any type checking on the pointer, and you can
give it a pointer to something else... just as I did in line 850 of
md/md.c :-(
So I thought I would add some type checking to list_entry so that
you have to pass it a "struct list_head *", but I then discovered that
lots of places are using list_entry to do creative casting on
all sorts of other things like inodes embedded in bigger structures
and so on.
So... I have created "generic_out_cast" which is like the old
list_entry but with an extra type arguement. I have then
changed uses of list_entry that did not actually apply to lists to use
generic_out_cast, often indirectly.
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.
If anyone wants to suggest better names of any of the names I have
chosen, feel free to submit suggestions or patches.
NOTE: I probably haven't found all list_entry() calls that don't operate
on list_heads. I have found all that are necessary for a clean
compile with my standard .config, but it doesn't include everything.
If there are some I have missed, they will cause benign compiler
warnings and can easily be fixed later.
NOTE2: I placed generic_out_cast in list.h because I knew it would be
included in all the right places. Suggests for a better place are
welcome.
NeilBrown (who wishes the compiler could catch even more of his silly
typos than it currently does)
----------- Diffstat output ------------
./drivers/pci/pci-driver.c | 14 +++++++-------
./drivers/pci/proc.c | 4 ++--
./drivers/scsi/scsi.h | 2 ++
./drivers/scsi/scsi_scan.c | 3 +--
./drivers/usb/core/usb.c | 10 +++++-----
./fs/driverfs/inode.c | 8 ++++----
./fs/ext2/ext2.h | 2 +-
./include/linux/adfs_fs.h | 2 +-
./include/linux/driverfs_fs.h | 2 ++
./include/linux/efs_fs.h | 2 +-
./include/linux/ext3_fs.h | 2 +-
./include/linux/fs.h | 10 ++++++++--
./include/linux/hfs_fs.h | 2 +-
./include/linux/iso_fs.h | 2 +-
./include/linux/list.h | 13 ++++++++++++-
./include/linux/msdos_fs.h | 2 +-
./include/linux/ncp_fs.h | 2 +-
./include/linux/nfs_fs.h | 2 +-
./include/linux/pci.h | 4 ++++
./include/linux/proc_fs.h | 2 +-
./include/linux/qnx4_fs.h | 2 +-
./include/linux/reiserfs_fs.h | 2 +-
./include/linux/shmem_fs.h | 2 +-
./include/linux/smb_fs.h | 2 +-
./include/linux/ufs_fs.h | 2 +-
./include/linux/usb.h | 2 ++
./net/socket.c | 2 +-
27 files changed, 65 insertions(+), 39 deletions(-)
--- ./drivers/scsi/scsi.h 2002/07/23 07:08:05 1.1
+++ ./drivers/scsi/scsi.h 2002/07/23 11:14:05 1.2
@@ -627,6 +627,8 @@ struct scsi_device {
int allow_revalidate;
struct device sdev_driverfs_dev;
};
+#define to_scsi_device(d) \
+ generic_out_cast(struct device, d, struct scsi_device, sdev_driverfs_dev)
/*
--- ./drivers/scsi/scsi_scan.c 2002/07/23 07:10:04 1.1
+++ ./drivers/scsi/scsi_scan.c 2002/07/23 11:14:05 1.2
@@ -293,8 +293,7 @@ static int scsilun_to_int(ScsiLun *scsil
static ssize_t scsi_device_type_read(struct device *driverfs_dev, char *page,
size_t count, loff_t off)
{
- struct scsi_device *SDpnt = list_entry(driverfs_dev,
- struct scsi_device, sdev_driverfs_dev);
+ struct scsi_device *SDpnt = to_scsi_device(driverfs_dev);
if ((SDpnt->type <= MAX_SCSI_DEVICE_CODE) &&
(scsi_device_types[(int)SDpnt->type] != NULL))
--- ./drivers/usb/core/usb.c 2002/07/23 07:13:47 1.1
+++ ./drivers/usb/core/usb.c 2002/07/23 11:14:05 1.2
@@ -832,7 +832,7 @@ show_config (struct device *dev, char *b
if (off)
return 0;
- udev = list_entry (dev, struct usb_device, dev);
+ udev = to_usb_device (dev);
return sprintf (buf, "%u\n", udev->actconfig->bConfigurationValue);
}
static struct driver_file_entry usb_config_entry = {
@@ -851,7 +851,7 @@ show_altsetting (struct device *dev, cha
if (off)
return 0;
- interface = list_entry (dev, struct usb_interface, dev);
+ interface = to_usb_interface (dev);
return sprintf (buf, "%u\n", interface->altsetting->bAlternateSetting);
}
static struct driver_file_entry usb_altsetting_entry = {
@@ -868,7 +868,7 @@ static ssize_t show_product (struct devi
if (off)
return 0;
- udev = list_entry (dev, struct usb_device, dev);
+ udev = to_usb_device (dev);
len = usb_string(udev, udev->descriptor.iProduct, buf, PAGE_SIZE);
buf[len] = '\n';
@@ -890,7 +890,7 @@ show_manufacturer (struct device *dev, c
if (off)
return 0;
- udev = list_entry (dev, struct usb_device, dev);
+ udev = to_usb_device (dev);
len = usb_string(udev, udev->descriptor.iManufacturer, buf, PAGE_SIZE);
buf[len] = '\n';
@@ -912,7 +912,7 @@ show_serial (struct device *dev, char *b
if (off)
return 0;
- udev = list_entry (dev, struct usb_device, dev);
+ udev = to_usb_device (dev);
len = usb_string(udev, udev->descriptor.iSerialNumber, buf, PAGE_SIZE);
buf[len] = '\n';
--- ./drivers/pci/pci-driver.c 2002/07/23 07:05:59 1.1
+++ ./drivers/pci/pci-driver.c 2002/07/23 11:14:05 1.2
@@ -41,8 +41,8 @@ static int pci_device_probe(struct devic
struct pci_driver *drv;
struct pci_dev *pci_dev;
- drv = list_entry(dev->driver, struct pci_driver, driver);
- pci_dev = list_entry(dev, struct pci_dev, dev);
+ drv = to_pci_driver(dev->driver);
+ pci_dev = to_pci_dev(dev);
if (drv->probe) {
const struct pci_device_id *id;
@@ -60,7 +60,7 @@ static int pci_device_probe(struct devic
static int pci_device_remove(struct device * dev)
{
- struct pci_dev * pci_dev = list_entry(dev,struct pci_dev,dev);
+ struct pci_dev * pci_dev = to_pci_dev(dev);
struct pci_driver * drv = pci_dev->driver;
if (drv) {
@@ -73,7 +73,7 @@ static int pci_device_remove(struct devi
static int pci_device_suspend(struct device * dev, u32 state, u32 level)
{
- struct pci_dev * pci_dev = (struct pci_dev *)list_entry(dev,struct pci_dev,dev);
+ struct pci_dev * pci_dev = to_pci_dev(dev);
int error = 0;
if (pci_dev->driver) {
@@ -87,7 +87,7 @@ static int pci_device_suspend(struct dev
static int pci_device_resume(struct device * dev, u32 level)
{
- struct pci_dev * pci_dev = (struct pci_dev *)list_entry(dev,struct pci_dev,dev);
+ struct pci_dev * pci_dev = to_pci_dev(dev);
if (pci_dev->driver) {
if (level == RESUME_POWER_ON && pci_dev->driver->resume)
@@ -175,8 +175,8 @@ pci_dev_driver(const struct pci_dev *dev
*/
static int pci_bus_match(struct device * dev, struct device_driver * drv)
{
- struct pci_dev * pci_dev = list_entry(dev, struct pci_dev, dev);
- struct pci_driver * pci_drv = list_entry(drv,struct pci_driver,driver);
+ struct pci_dev * pci_dev = to_pci_dev(dev);
+ struct pci_driver * pci_drv = to_pci_driver(drv);
const struct pci_device_id * ids = pci_drv->id_table;
if (!ids)
--- ./drivers/pci/proc.c 2002/07/23 10:25:17 1.1
+++ ./drivers/pci/proc.c 2002/07/23 11:14:05 1.2
@@ -374,7 +374,7 @@ static struct proc_dir_entry *proc_bus_p
/* driverfs files */
static ssize_t pci_show_irq(struct device * dev, char * buf, size_t count, loff_t off)
{
- struct pci_dev * pci_dev = list_entry(dev,struct pci_dev,dev);
+ struct pci_dev * pci_dev = to_pci_dev(dev);
return off ? 0 : sprintf(buf,"%u\n",pci_dev->irq);
}
@@ -386,7 +386,7 @@ static struct driver_file_entry pci_irq_
static ssize_t pci_show_resources(struct device * dev, char * buf, size_t count, loff_t off)
{
- struct pci_dev * pci_dev = list_entry(dev,struct pci_dev,dev);
+ struct pci_dev * pci_dev = to_pci_dev(dev);
char * str = buf;
int i;
--- ./include/linux/list.h 2002/07/22 11:20:13 1.1
+++ ./include/linux/list.h 2002/07/23 11:14:05 1.2
@@ -178,13 +178,24 @@ static inline void list_splice_init(list
}
/**
+ * generic_out_cast - cast a member of a structure out to that structure
+ *
+ * @ptr_type: the type of the member
+ * @ptr: the pointer to the member.
+ * @type: the type of the struct this is embedded in.
+ * @member: the name of the member within the struct.
+ *
+ */
+#define generic_out_cast(ptr_type, ptr, type, member) \
+ ({ const ptr_type *__ptr = ptr ; (type *)((char *)(__ptr)-(unsigned long)(&((type *)0)->member));})
+/**
* list_entry - get the struct for this entry
* @ptr: the &list_t pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*/
#define list_entry(ptr, type, member) \
- ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
+ generic_out_cast(list_t, ptr, type, member)
/**
* list_for_each - iterate over a list
--- ./include/linux/fs.h 2002/07/22 11:30:57 1.1
+++ ./include/linux/fs.h 2002/07/23 11:14:05 1.2
@@ -407,14 +407,20 @@ struct socket_alloc {
struct inode vfs_inode;
};
+#define inode_out_cast(ptr, type, member) \
+ generic_out_cast(struct inode, ptr, type, member)
+
static inline struct socket *SOCKET_I(struct inode *inode)
{
- return &list_entry(inode, struct socket_alloc, vfs_inode)->socket;
+ return &inode_out_cast(inode, struct socket_alloc, vfs_inode)->socket;
}
+#define socket_out_cast(ptr, type, member) \
+ generic_out_cast(struct socket, ptr, type, member)
+
static inline struct inode *SOCK_INODE(struct socket *socket)
{
- return &list_entry(socket, struct socket_alloc, socket)->vfs_inode;
+ return &generic_out_cast(struct socket, socket, struct socket_alloc, socket)->vfs_inode;
}
/* will die */
--- ./include/linux/pci.h 2002/07/23 07:06:37 1.1
+++ ./include/linux/pci.h 2002/07/23 11:14:05 1.2
@@ -392,6 +392,7 @@ struct pci_dev {
#define pci_dev_g(n) list_entry(n, struct pci_dev, global_list)
#define pci_dev_b(n) list_entry(n, struct pci_dev, bus_list)
+#define to_pci_dev(n) generic_out_cast(struct device, n, struct pci_dev, dev)
/*
* For PCI devices, the region numbers are assigned this way:
@@ -490,6 +491,9 @@ struct pci_driver {
struct device_driver driver;
};
+
+#define to_pci_driver(drv) \
+ generic_out_cast(struct device_driver, drv,struct pci_driver, driver)
/* these external functions are only available when PCI support is enabled */
--- ./include/linux/adfs_fs.h 2002/07/22 11:38:14 1.1
+++ ./include/linux/adfs_fs.h 2002/07/23 11:14:05 1.2
@@ -68,7 +68,7 @@ static inline struct adfs_sb_info *ADFS_
static inline struct adfs_inode_info *ADFS_I(struct inode *inode)
{
- return list_entry(inode, struct adfs_inode_info, vfs_inode);
+ return inode_out_cast(inode, struct adfs_inode_info, vfs_inode);
}
#endif
--- ./include/linux/efs_fs.h 2002/07/22 11:38:24 1.1
+++ ./include/linux/efs_fs.h 2002/07/23 11:14:05 1.2
@@ -41,7 +41,7 @@ static const char cprt[] = "EFS: "EFS_VE
static inline struct efs_inode_info *INODE_INFO(struct inode *inode)
{
- return list_entry(inode, struct efs_inode_info, vfs_inode);
+ return inode_out_cast(inode, struct efs_inode_info, vfs_inode);
}
static inline struct efs_sb_info *SUPER_INFO(struct super_block *sb)
--- ./include/linux/ext3_fs.h 2002/07/22 11:38:36 1.1
+++ ./include/linux/ext3_fs.h 2002/07/23 11:14:05 1.2
@@ -447,7 +447,7 @@ struct ext3_super_block {
#define EXT3_SB(sb) (&((sb)->u.ext3_sb))
static inline struct ext3_inode_info *EXT3_I(struct inode *inode)
{
- return list_entry(inode, struct ext3_inode_info, vfs_inode);
+ return inode_out_cast(inode, struct ext3_inode_info, vfs_inode);
}
#else
/* Assume that user mode programs are passing in an ext3fs superblock, not
--- ./include/linux/hfs_fs.h 2002/07/22 11:38:43 1.1
+++ ./include/linux/hfs_fs.h 2002/07/23 11:14:05 1.2
@@ -322,7 +322,7 @@ extern void hfs_tolower(unsigned char *,
static inline struct hfs_inode_info *HFS_I(struct inode *inode)
{
- return list_entry(inode, struct hfs_inode_info, vfs_inode);
+ return inode_out_cast(inode, struct hfs_inode_info, vfs_inode);
}
static inline struct hfs_sb_info *HFS_SB(struct super_block *sb)
--- ./include/linux/iso_fs.h 2002/07/22 11:38:49 1.1
+++ ./include/linux/iso_fs.h 2002/07/23 11:14:05 1.2
@@ -179,7 +179,7 @@ static inline struct isofs_sb_info *ISOF
static inline struct iso_inode_info *ISOFS_I(struct inode *inode)
{
- return list_entry(inode, struct iso_inode_info, vfs_inode);
+ return inode_out_cast(inode, struct iso_inode_info, vfs_inode);
}
static inline int isonum_711(char *p)
--- ./include/linux/msdos_fs.h 2002/07/22 11:38:57 1.1
+++ ./include/linux/msdos_fs.h 2002/07/23 11:14:05 1.2
@@ -198,7 +198,7 @@ static inline struct msdos_sb_info *MSDO
static inline struct msdos_inode_info *MSDOS_I(struct inode *inode)
{
- return list_entry(inode, struct msdos_inode_info, vfs_inode);
+ return inode_out_cast(inode, struct msdos_inode_info, vfs_inode);
}
struct fat_cache {
--- ./include/linux/ncp_fs.h 2002/07/22 11:39:03 1.1
+++ ./include/linux/ncp_fs.h 2002/07/23 11:14:05 1.2
@@ -199,7 +199,7 @@ static inline struct ncp_server *NCP_SBP
#define NCP_SERVER(inode) NCP_SBP((inode)->i_sb)
static inline struct ncp_inode_info *NCP_FINFO(struct inode *inode)
{
- return list_entry(inode, struct ncp_inode_info, vfs_inode);
+ return inode_out_cast(inode, struct ncp_inode_info, vfs_inode);
}
#ifdef DEBUG_NCP_MALLOC
--- ./include/linux/nfs_fs.h 2002/07/22 11:39:14 1.1
+++ ./include/linux/nfs_fs.h 2002/07/23 11:14:05 1.2
@@ -176,7 +176,7 @@ struct nfs_inode {
static inline struct nfs_inode *NFS_I(struct inode *inode)
{
- return list_entry(inode, struct nfs_inode, vfs_inode);
+ return inode_out_cast(inode, struct nfs_inode, vfs_inode);
}
#define NFS_SB(s) ((struct nfs_server *)(s->u.generic_sbp))
--- ./include/linux/proc_fs.h 2002/07/22 11:39:23 1.1
+++ ./include/linux/proc_fs.h 2002/07/23 11:14:05 1.2
@@ -219,7 +219,7 @@ struct proc_inode {
static inline struct proc_inode *PROC_I(const struct inode *inode)
{
- return list_entry(inode, struct proc_inode, vfs_inode);
+ return inode_out_cast(inode, struct proc_inode, vfs_inode);
}
static inline struct proc_dir_entry *PDE(const struct inode *inode)
--- ./include/linux/qnx4_fs.h 2002/07/22 11:39:27 1.1
+++ ./include/linux/qnx4_fs.h 2002/07/23 11:14:05 1.2
@@ -140,7 +140,7 @@ static inline struct qnx4_sb_info *qnx4_
static inline struct qnx4_inode_info *qnx4_i(struct inode *inode)
{
- return list_entry(inode, struct qnx4_inode_info, vfs_inode);
+ return inode_out_cast(inode, struct qnx4_inode_info, vfs_inode);
}
static inline struct qnx4_inode_entry *qnx4_raw_inode(struct inode *inode)
--- ./include/linux/shmem_fs.h 2002/07/22 11:39:45 1.1
+++ ./include/linux/shmem_fs.h 2002/07/23 11:14:05 1.2
@@ -31,7 +31,7 @@ struct shmem_sb_info {
static inline struct shmem_inode_info *SHMEM_I(struct inode *inode)
{
- return list_entry(inode, struct shmem_inode_info, vfs_inode);
+ return inode_out_cast(inode, struct shmem_inode_info, vfs_inode);
}
#endif
--- ./include/linux/reiserfs_fs.h 2002/07/22 11:39:36 1.1
+++ ./include/linux/reiserfs_fs.h 2002/07/23 11:14:05 1.2
@@ -288,7 +288,7 @@ struct unfm_nodeinfo {
static inline struct reiserfs_inode_info *REISERFS_I(struct inode *inode)
{
- return list_entry(inode, struct reiserfs_inode_info, vfs_inode);
+ return inode_out_cast(inode, struct reiserfs_inode_info, vfs_inode);
}
static inline struct reiserfs_sb_info *REISERFS_SB(const struct super_block *sb)
--- ./include/linux/smb_fs.h 2002/07/22 11:40:00 1.1
+++ ./include/linux/smb_fs.h 2002/07/23 11:14:05 1.2
@@ -38,7 +38,7 @@ static inline struct smb_sb_info *SMB_SB
static inline struct smb_inode_info *SMB_I(struct inode *inode)
{
- return list_entry(inode, struct smb_inode_info, vfs_inode);
+ return inode_out_cast(inode, struct smb_inode_info, vfs_inode);
}
/* macro names are short for word, double-word, long value (?) */
--- ./include/linux/ufs_fs.h 2002/07/22 11:40:05 1.1
+++ ./include/linux/ufs_fs.h 2002/07/23 11:14:05 1.2
@@ -784,7 +784,7 @@ extern void ufs_truncate (struct inode *
static inline struct ufs_inode_info *UFS_I(struct inode *inode)
{
- return list_entry(inode, struct ufs_inode_info, vfs_inode);
+ return inode_out_cast(inode, struct ufs_inode_info, vfs_inode);
}
#endif /* __KERNEL__ */
--- ./include/linux/driverfs_fs.h 2002/07/23 10:26:09 1.1
+++ ./include/linux/driverfs_fs.h 2002/07/23 11:14:06 1.2
@@ -46,6 +46,8 @@ struct driver_file_entry {
ssize_t (*store)(struct device * dev, const char * buf, size_t count, loff_t off);
};
+#define dde_out_cast(d) generic_out_cast(struct driver_dir_entry, d, struct device, dir)
+
extern int
driverfs_create_dir(struct driver_dir_entry *, struct driver_dir_entry *);
--- ./include/linux/usb.h 2002/07/23 07:13:17 1.1
+++ ./include/linux/usb.h 2002/07/23 11:14:06 1.2
@@ -257,6 +257,7 @@ struct usb_interface {
struct device dev; /* interface specific device info */
void *private_data;
};
+#define to_usb_interface(d) generic_out_cast(struct device, d, struct usb_interface, dev)
/* USB_DT_CONFIG: Configuration descriptor information.
*
@@ -422,6 +423,7 @@ struct usb_device {
int maxchild; /* Number of ports if hub */
struct usb_device *children[USB_MAXCHILDREN];
};
+#define to_usb_device(d) generic_out_cast(struct device, d, struct usb_device, dev)
extern struct usb_device *usb_alloc_dev(struct usb_device *parent, struct usb_bus *);
extern struct usb_device *usb_get_dev(struct usb_device *dev);
--- ./net/socket.c 2002/07/23 07:16:26 1.1
+++ ./net/socket.c 2002/07/23 11:14:06 1.2
@@ -288,7 +288,7 @@ static struct inode *sock_alloc_inode(st
static void sock_destroy_inode(struct inode *inode)
{
kmem_cache_free(sock_inode_cachep,
- list_entry(inode, struct socket_alloc, vfs_inode));
+ inode_out_cast(inode, struct socket_alloc, vfs_inode));
}
static void init_once(void * foo, kmem_cache_t * cachep, unsigned long flags)
--- ./fs/ext2/ext2.h 2002/07/23 10:33:46 1.1
+++ ./fs/ext2/ext2.h 2002/07/23 11:14:06 1.2
@@ -34,7 +34,7 @@ struct ext2_inode_info {
static inline struct ext2_inode_info *EXT2_I(struct inode *inode)
{
- return list_entry(inode, struct ext2_inode_info, vfs_inode);
+ return inode_out_cast(inode, struct ext2_inode_info, vfs_inode);
}
/* balloc.c */
--- ./fs/driverfs/inode.c 2002/07/23 10:17:44 1.1
+++ ./fs/driverfs/inode.c 2002/07/23 11:14:06 1.2
@@ -267,7 +267,7 @@ driverfs_read_file(struct file *file, ch
if (count > PAGE_SIZE)
count = PAGE_SIZE;
- dev = list_entry(entry->parent,struct device, dir);
+ dev = dde_out_cast(entry->parent);
page = (unsigned char*)__get_free_page(GFP_KERNEL);
if (!page)
@@ -328,7 +328,7 @@ driverfs_write_file(struct file *file, c
if (!entry->store)
return 0;
- dev = list_entry(entry->parent,struct device, dir);
+ dev = dde_out_cast(entry->parent);
page = (char *)__get_free_page(GFP_KERNEL);
if (!page)
@@ -394,7 +394,7 @@ static int driverfs_open_file(struct ino
entry = (struct driver_file_entry *)inode->u.generic_ip;
if (!entry)
return -EFAULT;
- dev = (struct device *)list_entry(entry->parent,struct device,dir);
+ dev = dde_out_cast(entry->parent);
get_device(dev);
filp->private_data = entry;
return 0;
@@ -408,7 +408,7 @@ static int driverfs_release(struct inode
entry = (struct driver_file_entry *)filp->private_data;
if (!entry)
return -EFAULT;
- dev = (struct device *)list_entry(entry->parent,struct device,dir);
+ dev = dde_out_cast(entry->parent);
put_device(dev);
return 0;
}
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,
--
................................................................
: [email protected] : 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}...............:
remove-irqlock-2.5.27-F3Neil Brown wrote:
> list.h has this nifty macro called list_entry that takes a pointer to a "struct
> list_head" and "casts" that to a pointer to some structure that
> contains the "struct list_head".
>
> However it doesn't do any type checking on the pointer, and you can
> give it a pointer to something else... just as I did in line 850 of
> md/md.c :-(
>
> So I thought I would add some type checking to list_entry so that
> you have to pass it a "struct list_head *", but I then discovered that
> lots of places are using list_entry to do creative casting on
> all sorts of other things like inodes embedded in bigger structures
> and so on.
>
> So... I have created "generic_out_cast" which is like the old
> list_entry but with an extra type arguement. I have then
> changed uses of list_entry that did not actually apply to lists to use
> generic_out_cast, often indirectly.
>
> 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.
>
> If anyone wants to suggest better names of any of the names I have
> chosen, feel free to submit suggestions or patches.
How about member_to_struct() or unembed()?
--
Brian Gerst
Hmm, I don't disagree, but "out_cast" reads like "outcast" to me, which
has a totally different meaning than the one you want to imply.
I'd rather call it "container_struct()" or something like that, which at
least to me sounds more natural.
The difference is that in "out_cast()" you try to describe the operation
you're doing. Which is to me not very important or interesting (never mind
the confusion with a real word meaning something totally different).
In contrast, "container_struct()" tries to describe what the _result_ is,
not how we got there. And I think that's the much more important part,
especially when reading the code. You don't care how you get the result,
but you do care abotu what the result actually _means_.
And no, I'm not married to the "container_struct()" name. But any name we
come up with should have that kind of flavor to it, I feel. I think you
can more easily explain something like
#define to_pci_dev(n) \
container_struct(struct device, n, struct pci_dev, dev)
by telling somebody "the 'struct device' is contained within the 'struct
pci_dev', and 'to_pci_dev' converts from 'struct device' to the
container". You can explain it at a _conceptual_ level without having to
worry about what the implementation is. And that kind of conceptual notion
is always good.
While in contrast, to explain "out_cast()" you're already starting off at
a low-level compiler implementation level.
Maybe "member_to_container()" would be even better?
Linus
On Tue, Jul 23, 2002 at 09:28:26PM +1000, Neil Brown wrote:
> So... I have created "generic_out_cast" which is like the old
> list_entry but with an extra type arguement. I have then
> changed uses of list_entry that did not actually apply to lists to use
> generic_out_cast, often indirectly.
Two small nitpicks:
* the name is silly. what about get_container()?
* please move it away from list.h to e.g. kernel.h
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,
>
> --
> ................................................................
> : [email protected] : 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:
*/
On Tue, Jul 23, 2002 at 09:28:26PM +1000, Neil Brown wrote:
> However it doesn't do any type checking on the pointer, and you can
> give it a pointer to something else... just as I did in line 850 of
> md/md.c :-(
Hi Neil,
I've experienced the same problem with some of my own code. I came up with
the following macro to help solve the problem:
/* Given a pointer to a member of a struct, return a pointer to the struct
itself. */
#define BackPtr(ptr, type, member) ({ \
typeof( ((type *)0)->member ) *__mptr = (ptr); \
((type *)( (char *)__mptr - (unsigned long)(&((type *)0)->member) ));})
> So I thought I would add some type checking to list_entry so that
> you have to pass it a "struct list_head *", but I then discovered that
> lots of places are using list_entry to do creative casting on
> all sorts of other things like inodes embedded in bigger structures
> and so on.
>
> So... I have created "generic_out_cast" which is like the old
> list_entry but with an extra type arguement.
I don't think this is necessary. The compiler can get this information
from the type/member parameters and the typeof() call.
> Why "out_cast"???
Ugh.. I had a similar naming dilemma - I choose BackPtr (because the
macro causes a negative pointer offset).
-Kevin
--
------------------------------------------------------------------------
| Kevin O'Connor "BTW, IMHO we need a FAQ for |
| [email protected] 'IMHO', 'FAQ', 'BTW', etc. !" |
------------------------------------------------------------------------
On Tue, 23 Jul 2002 18:58:52 -0400, Kevin O'Connor wrote:
>#define BackPtr(ptr, type, member) ({ \
> typeof( ((type *)0)->member ) *__mptr = (ptr); \
> ((type *)( (char *)__mptr - (unsigned long)(&((type *)0)->member) ));})
I've seen this sort of code several times now in the Linux kernel,
and I've never liked it. Is there some reason why you guys avoid
offsetof() like the plague?
/Mikael
In article <[email protected]>,
Mikael Pettersson <[email protected]> wrote:
>On Tue, 23 Jul 2002 18:58:52 -0400, Kevin O'Connor wrote:
>>#define BackPtr(ptr, type, member) ({ \
>> typeof( ((type *)0)->member ) *__mptr = (ptr); \
>> ((type *)( (char *)__mptr - (unsigned long)(&((type *)0)->member) ));})
>
>I've seen this sort of code several times now in the Linux kernel,
>and I've never liked it. Is there some reason why you guys avoid
>offsetof() like the plague?
Trivial answer: offsetof() does not exist when you don't have system
header files.
So it's not that it's getting avoided, it _has_ to be re-implemented
anyway. And once you do that, you might as well do it right (ie what
the kernel wants is not offsetof, but a new pointer.
Linus
Hi,
On Tue, 23 Jul 2002, Linus Torvalds wrote:
> Maybe "member_to_container()" would be even better?
That sounds like trashing the member...
Regards,
Thunder
--
(Use http://www.ebb.org/ungeek if you can't decode)
------BEGIN GEEK CODE BLOCK------
Version: 3.12
GCS/E/G/S/AT d- s++:-- a? C++$ ULAVHI++++$ P++$ L++++(+++++)$ E W-$
N--- o? K? w-- O- M V$ PS+ PE- Y- PGP+ t+ 5+ X+ R- !tv b++ DI? !D G
e++++ h* r--- y-
------END GEEK CODE BLOCK------
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
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/
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
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
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.
--
................................................................
: [email protected] : 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}...............:
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.
--
................................................................
: [email protected] : 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}...............:
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
> --
> ................................................................
> : [email protected] : 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}...............:
>
> 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
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
>
>
>
>
>>--
>>................................................................
>>: [email protected] : 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 [email protected]
>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
On Wed, 24 Jul 2002 13:58:50 +0200, Jakob Oestergaard
<[email protected]> 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
In article <[email protected]>, Andi Kleen <[email protected]> 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
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
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
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
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
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