On Wed, 26 May 2004 18:41:29 +0200, J?rn Engel wrote:
>
> Anyway, whether we go for 4k in 2.6 or not, we should do our best to
> fix bad code and I will go looking for some more so others can go and
> fix some more. There's still enough horror in mainline for more than
> one amusement park, we just haven't found it yet.
Here's some. My tool is still buggy, so if any results don't make
sense, please tell me. Full results are a bit verbose (2M), but
compress quite well, so I have them attached. For the lazy, here are
a few interesting things. First the recursions that shouldn't iterate
too often:
WARNING: recursion detected:
0 default_wake_function
36 try_to_wake_up
0 task_rq_unlock
0 preempt_schedule
68 schedule
52 load_balance
0 find_busiest_queue
0 double_lock_balance
0 __preempt_spin_lock
0 _raw_spin_lock
0 printk
0 printk
16 release_console_sem
16 __wake_up
0 __wait_queue->func
WARNING: recursion detected:
12 kfree
12 cache_flusharray
20 free_block
12 slab_destroy
0 kernel_map_pages
20 change_page_attr
12 __change_page_attr
16 split_large_page
0 alloc_pages_node
24 __alloc_pages
284 try_to_free_pages
0 backing_dev_info->congested_fn
0 dm_any_congested
0 dm_table_put
0 table_destroy
0 vfree
0 __vunmap
WARNING: recursion detected:
0 kernel_map_pages
20 change_page_attr
12 __change_page_attr
16 split_large_page
0 alloc_pages_node
24 __alloc_pages
284 try_to_free_pages
0 backing_dev_info->congested_fn
0 dm_any_congested
0 dm_table_put
0 table_destroy
0 vfree
0 __vunmap
0 __free_pages
0 free_hot_page
0 free_hot_cold_page
WARNING: recursion detected:
0 dm_table_any_congested
0 backing_dev_info->congested_fn
0 dm_any_congested
WARNING: recursion detected:
12 kmem_cache_free
12 cache_flusharray
20 free_block
12 slab_destroy
WARNING: recursion detected:
68 schedule
0 finish_task_switch
0 __put_task_struct
0 free_task
12 kfree
12 cache_flusharray
20 free_block
12 slab_destroy
0 kernel_map_pages
20 change_page_attr
12 __change_page_attr
16 split_large_page
0 alloc_pages_node
24 __alloc_pages
284 try_to_free_pages
12 shrink_caches
12 shrink_zone
124 shrink_cache
176 shrink_list
0 handle_write_error
0 lock_page
72 __lock_page
0 io_schedule
WARNING: recursion detected:
0 kmem_cache_alloc
16 cache_alloc_refill
36 cache_grow
0 alloc_slabmgmt
WARNING: recursion detected:
24 __alloc_pages
284 try_to_free_pages
12 shrink_caches
12 shrink_zone
124 shrink_cache
176 shrink_list
0 add_to_swap
0 __add_to_swap_cache
16 radix_tree_insert
0 radix_tree_node_alloc
0 kmem_cache_alloc
0 kmem_cache_alloc
16 cache_alloc_refill
36 cache_grow
0 kmem_getpages
0 __get_free_pages
0 alloc_pages_node
WARNING: recursion detected:
28 qla2x00_handle_port_rscn
28 qla2x00_send_login_iocb
0 qla2x00_issue_marker
28 qla2x00_marker
0 __qla2x00_marker
24 qla2x00_req_pkt
0 qla2x00_poll
28 qla2x00_intr_handler
100 qla2x00_async_event
WARNING: recursion detected:
0 qla2x00_process_iodesc
28 qla2x00_handle_port_rscn
28 qla2x00_send_login_iocb
0 qla2x00_issue_marker
28 qla2x00_marker
0 __qla2x00_marker
24 qla2x00_req_pkt
0 qla2x00_poll
28 qla2x00_intr_handler
100 qla2x00_async_event
0 qla2x00_process_response_queue
WARNING: recursion detected:
28 qla2x00_marker
0 __qla2x00_marker
24 qla2x00_req_pkt
0 qla2x00_poll
28 qla2x00_intr_handler
88 qla2x00_next
32 qla2x00_start_scsi
WARNING: recursion detected:
92 qla2x00_mailbox_command
40 qla2x00_abort_isp
24 qla2x00_restart_isp
24 qla2x00_setup_chip
96 qla2x00_verify_checksum
WARNING: recursion detected:
96 qla2x00_issue_iocb
92 qla2x00_mailbox_command
40 qla2x00_abort_isp
24 qla2x00_restart_isp
0 qla2x00_configure_loop
80 qla2x00_configure_fabric
0 qla2x00_rff_id
WARNING: recursion detected:
72 qla2x00_rsnn_nn
96 qla2x00_issue_iocb
92 qla2x00_mailbox_command
40 qla2x00_abort_isp
24 qla2x00_restart_isp
0 qla2x00_configure_loop
80 qla2x00_configure_fabric
WARNING: recursion detected:
16 acpi_ut_remove_reference
24 acpi_ut_update_object_reference
16 acpi_ut_update_ref_count
16 acpi_ut_delete_internal_obj
WARNING: recursion detected:
32 acpi_ex_field_datum_io
76 acpi_ex_insert_into_field
52 acpi_ex_write_with_update_rule
WARNING: recursion detected:
72 acpi_ex_extract_from_field
32 acpi_ex_field_datum_io
WARNING: recursion detected:
32 acpi_ex_read_data_from_field
72 acpi_ex_extract_from_field
32 acpi_ex_field_datum_io
32 acpi_ex_access_region
20 acpi_ex_setup_region
16 acpi_ds_get_region_arguments
28 acpi_ds_execute_arguments
24 acpi_ps_parse_aml
36 acpi_ps_parse_loop
0 acpi_walk_state->ascending_callback
24 acpi_ds_exec_end_op
40 acpi_ex_resolve_operands
20 acpi_ex_resolve_to_value
28 acpi_ex_resolve_object_to_value
WARNING: recursion detected:
28 acpi_ds_execute_arguments
24 acpi_ps_parse_aml
36 acpi_ps_parse_loop
0 acpi_walk_state->ascending_callback
24 acpi_ds_exec_end_op
40 acpi_ex_resolve_operands
20 acpi_ex_resolve_to_value
28 acpi_ex_resolve_object_to_value
16 acpi_ds_get_package_arguments
WARNING: recursion detected:
32 acpi_ex_resolve_node_to_value
32 acpi_ex_read_data_from_field
72 acpi_ex_extract_from_field
32 acpi_ex_field_datum_io
32 acpi_ex_access_region
20 acpi_ex_setup_region
16 acpi_ds_get_region_arguments
28 acpi_ds_execute_arguments
24 acpi_ps_parse_aml
36 acpi_ps_parse_loop
0 acpi_walk_state->ascending_callback
24 acpi_ds_exec_end_op
40 acpi_ex_resolve_operands
20 acpi_ex_resolve_to_value
WARNING: recursion detected:
28 acpi_ns_evaluate_by_handle
20 acpi_ns_get_object_value
32 acpi_ex_resolve_node_to_value
32 acpi_ex_read_data_from_field
72 acpi_ex_extract_from_field
32 acpi_ex_field_datum_io
32 acpi_ex_access_region
20 acpi_ex_setup_region
16 acpi_ds_get_region_arguments
28 acpi_ds_execute_arguments
24 acpi_ps_parse_aml
36 acpi_ps_parse_loop
0 acpi_walk_state->ascending_callback
24 acpi_ds_exec_end_op
32 acpi_ds_load2_end_op
20 acpi_ex_create_table_region
28 acpi_ev_initialize_region
36 acpi_ev_execute_reg_method
WARNING: recursion detected:
24 acpi_ps_parse_aml
36 acpi_ds_call_control_method
There are more, but this shows a few ugly spots. It also shows bugs
in my tool, I'll have to look into those. Next month.
Now some of the top stack killers:
stackframes for call path too long (3136):
size function
0 radeonfb_pci_resume
2576 radeonfb_set_par
0 preempt_schedule
68 schedule
0 __put_task_struct
0 audit_free
0 audit_log_end
12 audit_log_end_fast
12 netlink_unicast
76 netlink_attachskb
0 __kfree_skb
0 ip_conntrack_put
0 ip_conntrack_put
12 kfree
0 kernel_map_pages
20 change_page_attr
24 __alloc_pages
284 try_to_free_pages
0 out_of_memory
0 mmput
0 exit_aio
52 aio_cancel_all
0 list_kiocb
stackframes for call path too long (3056):
size function
720 ncp_ioctl
616 ncp_conn_logged_in
24 ncp_lookup_volume
0 ncp_request2
164 sock_sendmsg
0 wait_on_sync_kiocb
68 schedule
0 __put_task_struct
0 audit_free
0 audit_log_end
12 audit_log_end_fast
12 netlink_unicast
76 netlink_attachskb
0 __kfree_skb
0 ip_conntrack_put
0 ip_conntrack_put
12 kfree
0 kernel_map_pages
20 change_page_attr
24 __alloc_pages
284 try_to_free_pages
0 out_of_memory
0 mmput
0 exit_aio
0 __put_ioctx
16 do_munmap
0 fput
0 __fput
0 locks_remove_flock
0 panic
0 sys_sync
0 sync_inodes
308 sync_inodes_sb
0 do_writepages
128 mpage_writepages
4 write_boundary_block
0 ll_rw_block
28 submit_bh
0 bio_alloc
88 mempool_alloc
256 wakeup_bdflush
20 pdflush_operation
0 printk
16 release_console_sem
16 __wake_up
0 printk
0 vscnprintf
32 vsnprintf
112 number
stackframes for call path too long (3024):
size function
0 acpi_device_ops->bind
292 acpi_pci_bind
292 acpi_pci_irq_add_prt
20 acpi_get_irq_routing_table
20 acpi_rs_get_prt_method_data
24 acpi_ut_evaluate_object
32 acpi_ns_evaluate_relative
28 acpi_ns_evaluate_by_handle
20 acpi_ns_get_object_value
32 acpi_ex_resolve_node_to_value
32 acpi_ex_read_data_from_field
72 acpi_ex_extract_from_field
32 acpi_ex_field_datum_io
32 acpi_ex_access_region
20 acpi_ex_setup_region
16 acpi_ds_get_region_arguments
28 acpi_ds_execute_arguments
24 acpi_ps_parse_aml
36 acpi_ds_call_control_method
24 acpi_ps_parse_aml
36 acpi_ps_parse_loop
24 acpi_ds_exec_end_op
32 acpi_ds_load2_end_op
20 acpi_ex_create_table_region
24 acpi_tb_find_table
224 acpi_get_firmware_table
68 acpi_tb_get_table
24 acpi_tb_get_table_body
36 acpi_tb_table_override
36 acpi_tb_get_this_table
0 acpi_os_map_memory
0 __ioremap
0 __pmd_alloc
0 preempt_schedule
68 schedule
0 __put_task_struct
0 audit_free
0 audit_log_end
12 audit_log_end_fast
12 netlink_unicast
76 netlink_attachskb
0 __kfree_skb
0 ip_conntrack_put
0 ip_conntrack_put
12 kfree
0 kernel_map_pages
20 change_page_attr
24 __alloc_pages
284 try_to_free_pages
0 out_of_memory
0 mmput
0 exit_aio
0 __put_ioctx
16 do_munmap
0 fput
0 __fput
0 locks_remove_flock
0 panic
0 sys_sync
0 sync_inodes
308 sync_inodes_sb
0 do_writepages
128 mpage_writepages
4 write_boundary_block
0 ll_rw_block
28 submit_bh
0 bio_alloc
88 mempool_alloc
256 wakeup_bdflush
20 pdflush_operation
0 printk
0 preempt_schedule
68 schedule
stackframes for call path too long (3104):
size function
0 client_reg_t->event_handler
1168 ide_config
12 ide_register_hw
1596 ide_unregister
0 device_unregister
0 device_del
0 kobject_del
0 kobject_hotplug
132 call_usermodehelper
80 wait_for_completion
68 schedule
0 __put_task_struct
0 audit_free
16 audit_filter_syscall
32 audit_filter_rules
stackframes for call path too long (3144):
size function
148 generic_ide_ioctl
12 ide_register_hw
1596 ide_unregister
0 device_unregister
0 device_del
0 kobject_del
0 kobject_hotplug
132 call_usermodehelper
80 wait_for_completion
68 schedule
0 __put_task_struct
0 audit_free
0 audit_log_end
12 audit_log_end_fast
12 netlink_unicast
76 netlink_attachskb
0 __kfree_skb
0 ip_conntrack_put
0 ip_conntrack_put
12 kfree
0 kernel_map_pages
20 change_page_attr
24 __alloc_pages
284 try_to_free_pages
0 out_of_memory
0 mmput
0 exit_aio
0 __put_ioctx
16 do_munmap
0 fput
0 __fput
0 locks_remove_flock
0 panic
0 sys_sync
0 sync_inodes
308 sync_inodes_sb
0 do_writepages
128 mpage_writepages
204 mpage_writepage
12 mpage_alloc
0 bio_alloc
tackframes for call path too long (3004):
size function
0 ____FAKE.Name.Chip.stat.Regi.LILP.Opti.high.lowe->ProcessIMQEntry
2076 CpqTsProcessIMQEntry
12 cpqfcTSCompleteExchange
12 kfree
0 kernel_map_pages
20 change_page_attr
24 __alloc_pages
284 try_to_free_pages
0 out_of_memory
0 mmput
0 exit_aio
0 __put_ioctx
16 do_munmap
0 fput
0 __fput
0 locks_remove_flock
0 panic
0 sys_sync
0 sync_inodes
308 sync_inodes_sb
0 do_writepages
128 mpage_writepages
4 write_boundary_block
0 ll_rw_block
28 submit_bh
36 submit_bio
56 generic_make_request
0 bdev_get_queue
Not too many above 3k and none above 4k. Actually, intermezzo had
quite a few paths that went above 4k, but that one's gone.
So effectively, it comes down to the recursive paths. Unless someone
comes up with a semantical parser that can figure out the maximum
number of iterations, we have to look at them manually.
J?rn
--
My second remark is that our intellectual powers are rather geared to
master static relations and that our powers to visualize processes
evolving in time are relatively poorly developed.
-- Edsger W. Dijkstra
On Tue, 1 June 2004 07:56:16 +0200, J?rn Engel wrote:
>
> So effectively, it comes down to the recursive paths. Unless someone
> comes up with a semantical parser that can figure out the maximum
> number of iterations, we have to look at them manually.
Linus, Andrew, would you accept patches like the one below? With such
information and assuming that the comments will get maintained, it's
relatively simple to unroll recursions and measure stack comsumption
more accurately.
J?rn
--
ticks = jiffies;
while (ticks == jiffies);
ticks = jiffies;
-- /usr/src/linux/init/main.c
Add recursion markers to teach automated test tools how bad documented
recursions really are. Currently, there is only a single such too that
can use the information and there is always the danger of documentation
and reality getting out of sync. But until there's a better tool...
Currently, this patch also has a few cleanup bits included. The cleanups
were helpful to figure out the depth of some recursions and could be
useful on their own. If not, they are easily removed.
arch/i386/kernel/apm.c | 4 ++
drivers/char/random.c | 6 ++++
drivers/ide/ide-tape.c | 33 +++++++++++++-----------
drivers/ide/ide-timing.h | 60 ++++++++++++++++++--------------------------
drivers/isdn/i4l/isdn_tty.c | 5 +++
drivers/isdn/icn/icn.c | 5 +++
fs/block_dev.c | 5 +++
fs/quota_v2.c | 43 +++++++++++++++++++------------
kernel/signal.c | 7 +++++
kernel/sysctl.c | 10 +++++++
10 files changed, 113 insertions(+), 65 deletions(-)
--- linux-2.6.6stack/arch/i386/kernel/apm.c~recursion 2004-05-10 18:10:06.000000000 +0200
+++ linux-2.6.6stack/arch/i386/kernel/apm.c 2004-05-30 18:24:54.000000000 +0200
@@ -1058,6 +1058,10 @@
* monitor powerdown for us.
*/
+/**
+ * RECURSION: 2
+ * STEP: apm_console_blank
+ */
static int apm_console_blank(int blank)
{
int error;
--- linux-2.6.6stack/kernel/sysctl.c~recursion 2004-05-30 17:51:03.000000000 +0200
+++ linux-2.6.6stack/kernel/sysctl.c 2004-05-30 17:52:25.000000000 +0200
@@ -1188,6 +1188,11 @@
#ifdef CONFIG_PROC_FS
/* Scan the sysctl entries in table and add them all into /proc */
+
+/**
+ * RECURSION: 100
+ * STEP: register_proc_table
+ */
static void register_proc_table(ctl_table * table, struct proc_dir_entry *root)
{
struct proc_dir_entry *de;
@@ -1237,6 +1242,11 @@
/*
* Unregister a /proc sysctl table and any subdirectories.
*/
+
+/**
+ * RECURSION: 100
+ * STEP: unregister_proc_table
+ */
static void unregister_proc_table(ctl_table * table, struct proc_dir_entry *root)
{
struct proc_dir_entry *de;
--- linux-2.6.6stack/kernel/signal.c~recursion 2004-05-10 18:10:38.000000000 +0200
+++ linux-2.6.6stack/kernel/signal.c 2004-05-30 18:24:38.000000000 +0200
@@ -626,6 +626,13 @@
* actual continuing for SIGCONT, but not the actual stopping for stop
* signals. The process stop is done as a signal action for SIG_DFL.
*/
+
+/**
+ * RECURSION: 2
+ * STEP: handle_stop_signal
+ * STEP: do_notify_parent_cldstop
+ * STEP: __group_send_sig_info
+ */
static void handle_stop_signal(int sig, struct task_struct *p)
{
struct task_struct *t;
--- linux-2.6.6stack/fs/block_dev.c~recursion 2004-05-10 18:10:30.000000000 +0200
+++ linux-2.6.6stack/fs/block_dev.c 2004-05-31 17:20:53.000000000 +0200
@@ -547,6 +547,11 @@
}
EXPORT_SYMBOL(bd_set_size);
+/**
+ * RECURSION: 2
+ * STEP: do_open
+ * STEP: blkdev_get
+ */
static int do_open(struct block_device *bdev, struct file *file)
{
struct module *owner = NULL;
--- linux-2.6.6stack/fs/quota_v2.c~recursion 2004-05-10 18:10:32.000000000 +0200
+++ linux-2.6.6stack/fs/quota_v2.c 2004-05-30 18:36:23.000000000 +0200
@@ -352,6 +352,12 @@
}
/* Insert reference to structure into the trie */
+
+/**
+ * Recursion count equals V2_DQTREEDEPTH, keep both in sync
+ * RECURSION: 4
+ * STEP: do_insert_tree
+ */
static int do_insert_tree(struct dquot *dquot, uint *treeblk, int depth)
{
struct file *filp = sb_dqopt(dquot->dq_sb)->files[dquot->dq_type];
@@ -369,12 +375,9 @@
*treeblk = ret;
memset(buf, 0, V2_DQBLKSIZE);
newact = 1;
- }
- else {
- if ((ret = read_blk(filp, *treeblk, buf)) < 0) {
- printk(KERN_ERR "VFS: Can't read tree quota block %u.\n", *treeblk);
- goto out_buf;
- }
+ } else if ((ret = read_blk(filp, *treeblk, buf)) < 0) {
+ printk(KERN_ERR "VFS: Can't read tree quota block %u.\n", *treeblk);
+ goto out_buf;
}
ref = (u32 *)buf;
newblk = le32_to_cpu(ref[GETIDINDEX(dquot->dq_id, depth)]);
@@ -389,14 +392,12 @@
}
#endif
newblk = find_free_dqentry(dquot, &ret);
- }
- else
+ } else
ret = do_insert_tree(dquot, &newblk, depth+1);
if (newson && ret >= 0) {
ref[GETIDINDEX(dquot->dq_id, depth)] = cpu_to_le32(newblk);
ret = write_blk(filp, *treeblk, buf);
- }
- else if (newact && ret < 0)
+ } else if (newact && ret < 0)
put_free_dqblk(filp, dquot->dq_type, buf, *treeblk);
out_buf:
freedqbuf(buf);
@@ -498,6 +499,12 @@
}
/* Remove reference to dquot from tree */
+
+/**
+ * Recursion count equals V2_DQTREEDEPTH, keep both in sync
+ * RECURSION: 4
+ * STEP: remove_tree
+ */
static int remove_tree(struct dquot *dquot, uint *blk, int depth)
{
struct file *filp = sb_dqopt(dquot->dq_sb)->files[dquot->dq_type];
@@ -516,19 +523,17 @@
if (depth == V2_DQTREEDEPTH-1) {
ret = free_dqentry(dquot, newblk);
newblk = 0;
- }
- else
+ } else
ret = remove_tree(dquot, &newblk, depth+1);
if (ret >= 0 && !newblk) {
int i;
ref[GETIDINDEX(dquot->dq_id, depth)] = cpu_to_le32(0);
- for (i = 0; i < V2_DQBLKSIZE && !buf[i]; i++); /* Block got empty? */
+ for (i = 0; i < V2_DQBLKSIZE && !buf[i]; i++)
+ ; /* Block got empty? */
if (i == V2_DQBLKSIZE) {
put_free_dqblk(filp, dquot->dq_type, buf, *blk);
*blk = 0;
- }
- else
- if ((ret = write_blk(filp, *blk, buf)) < 0)
+ } else if ((ret = write_blk(filp, *blk, buf)) < 0)
printk(KERN_ERR "VFS: Can't write quota tree block %u.\n", *blk);
}
out_buf:
@@ -584,6 +589,12 @@
}
/* Find entry for given id in the tree */
+
+/**
+ * Recursion count equals V2_DQTREEDEPTH, keep both in sync
+ * RECURSION: 4
+ * STEP: find_tree_dqentry
+ */
static loff_t find_tree_dqentry(struct dquot *dquot, uint blk, int depth)
{
struct file *filp = sb_dqopt(dquot->dq_sb)->files[dquot->dq_type];
--- linux-2.6.6stack/drivers/char/random.c~recursion 2004-05-10 18:10:23.000000000 +0200
+++ linux-2.6.6stack/drivers/char/random.c 2004-05-30 18:48:55.000000000 +0200
@@ -1311,6 +1311,12 @@
* from the primary pool to the secondary extraction pool. We make
* sure we pull enough for a 'catastrophic reseed'.
*/
+
+/**
+ * RECURSION: 2
+ * STEP: xfer_secondary_pool
+ * STEP: extract_entropy
+ */
static inline void xfer_secondary_pool(struct entropy_store *r,
size_t nbytes, __u32 *tmp)
{
--- linux-2.6.6stack/drivers/ide/ide-timing.h~recursion 2004-01-09 07:59:26.000000000 +0100
+++ linux-2.6.6stack/drivers/ide/ide-timing.h 2004-05-31 16:56:23.000000000 +0200
@@ -208,63 +208,53 @@
return t;
}
+/**
+ * RECURSION: 2
+ * STEP: ide_timing_compute
+ */
static int ide_timing_compute(ide_drive_t *drive, short speed, struct ide_timing *t, int T, int UT)
{
struct hd_driveid *id = drive->id;
struct ide_timing *s, p;
-/*
- * Find the mode.
- */
-
- if (!(s = ide_timing_find_mode(speed)))
+ s = ide_timing_find_mode(speed);
+ if (!s)
return -EINVAL;
-/*
- * If the drive is an EIDE drive, it can tell us it needs extended
- * PIO/MWDMA cycle timing.
- */
-
- if (id && id->field_valid & 2) { /* EIDE drive */
-
+ /* If the drive is an EIDE drive, it can tell us it needs extended
+ * PIO/MWDMA cycle timing.
+ */
+ if (id && (id->field_valid & 2)) { /* EIDE drive */
memset(&p, 0, sizeof(p));
switch (speed & XFER_MODE) {
+ case XFER_PIO:
+ if (speed <= XFER_PIO_2)
+ p.cycle = p.cyc8b = id->eide_pio;
+ else
+ p.cycle = p.cyc8b = id->eide_pio_iordy;
+ break;
- case XFER_PIO:
- if (speed <= XFER_PIO_2) p.cycle = p.cyc8b = id->eide_pio;
- else p.cycle = p.cyc8b = id->eide_pio_iordy;
- break;
-
- case XFER_MWDMA:
- p.cycle = id->eide_dma_min;
- break;
+ case XFER_MWDMA:
+ p.cycle = id->eide_dma_min;
+ break;
}
-
ide_timing_merge(&p, t, t, IDE_TIMING_CYCLE | IDE_TIMING_CYC8B);
}
-/*
- * Convert the timing to bus clock counts.
- */
-
+ /* Convert the timing to bus clock counts. */
ide_timing_quantize(s, t, T, UT);
-/*
- * Even in DMA/UDMA modes we still use PIO access for IDENTIFY, S.M.A.R.T
- * and some other commands. We have to ensure that the DMA cycle timing is
- * slower/equal than the fastest PIO timing.
- */
-
+ /* Even in DMA/UDMA modes we still use PIO access for IDENTIFY,
+ * S.M.A.R.T and some other commands. We have to ensure that the
+ * DMA cycle timing is slower/equal than the fastest PIO timing.
+ */
if ((speed & XFER_MODE) != XFER_PIO) {
ide_timing_compute(drive, ide_find_best_mode(drive, XFER_PIO | XFER_EPIO), &p, T, UT);
ide_timing_merge(&p, t, t, IDE_TIMING_ALL);
}
-/*
- * Lenghten active & recovery time so that cycle time is correct.
- */
-
+ /* Lenghten active & recovery time so that cycle time is correct. */
if (t->act8b + t->rec8b < t->cyc8b) {
t->act8b += (t->cyc8b - (t->act8b + t->rec8b)) / 2;
t->rec8b = t->cyc8b - t->act8b;
--- linux-2.6.6stack/drivers/ide/ide-tape.c~recursion 2004-05-10 18:10:24.000000000 +0200
+++ linux-2.6.6stack/drivers/ide/ide-tape.c 2004-05-31 16:58:30.000000000 +0200
@@ -3653,6 +3653,11 @@
* the filemark is in our internal pipeline even if the tape doesn't
* support spacing over filemarks in the reverse direction.
*/
+
+/**
+ * RECURSION: 2
+ * STEP: idetape_space_over_filemarks
+ */
static int idetape_space_over_filemarks (ide_drive_t *drive,short mt_op,int mt_count)
{
idetape_tape_t *tape = drive->driver_data;
@@ -3711,21 +3716,21 @@
* Now we can issue the space command.
*/
switch (mt_op) {
- case MTFSF:
- case MTBSF:
- idetape_create_space_cmd(&pc,mt_count-count,IDETAPE_SPACE_OVER_FILEMARK);
- return (idetape_queue_pc_tail(drive, &pc));
- case MTFSFM:
- case MTBSFM:
- if (!tape->capabilities.sprev)
- return (-EIO);
- retval = idetape_space_over_filemarks(drive, MTFSF, mt_count-count);
- if (retval) return (retval);
- count = (MTBSFM == mt_op ? 1 : -1);
- return (idetape_space_over_filemarks(drive, MTFSF, count));
- default:
- printk(KERN_ERR "ide-tape: MTIO operation %d not supported\n",mt_op);
+ case MTFSF:
+ case MTBSF:
+ idetape_create_space_cmd(&pc,mt_count-count,IDETAPE_SPACE_OVER_FILEMARK);
+ return (idetape_queue_pc_tail(drive, &pc));
+ case MTFSFM:
+ case MTBSFM:
+ if (!tape->capabilities.sprev)
return (-EIO);
+ retval = idetape_space_over_filemarks(drive, MTFSF, mt_count-count);
+ if (retval) return (retval);
+ count = (MTBSFM == mt_op ? 1 : -1);
+ return (idetape_space_over_filemarks(drive, MTFSF, count));
+ default:
+ printk(KERN_ERR "ide-tape: MTIO operation %d not supported\n",mt_op);
+ return (-EIO);
}
}
--- linux-2.6.6stack/drivers/isdn/i4l/isdn_tty.c~recursion 2004-03-28 21:51:38.000000000 +0200
+++ linux-2.6.6stack/drivers/isdn/i4l/isdn_tty.c 2004-05-31 17:02:39.000000000 +0200
@@ -2519,6 +2519,11 @@
* For RING-message handle auto-ATA if register 0 != 0
*/
+/**
+ * RECURSION: 2
+ * STEP: isdn_tty_modem_result
+ * STEP: isdn_tty_cmd_ATA
+ */
static void
isdn_tty_modem_result(int code, modem_info * info)
{
--- linux-2.6.6stack/drivers/isdn/icn/icn.c~recursion 2004-03-28 21:51:38.000000000 +0200
+++ linux-2.6.6stack/drivers/isdn/icn/icn.c 2004-05-31 17:03:55.000000000 +0200
@@ -1097,6 +1097,11 @@
/*
* Delete card's pending timers, send STOP to linklevel
*/
+
+/**
+ * RECURSION: 2
+ * STEP: icn_stopcard
+ */
static void
icn_stopcard(icn_card * card)
{
Hi!
> > So effectively, it comes down to the recursive paths. Unless someone
> > comes up with a semantical parser that can figure out the maximum
> > number of iterations, we have to look at them manually.
>
> Linus, Andrew, would you accept patches like the one below? With such
> information and assuming that the comments will get maintained, it's
> relatively simple to unroll recursions and measure stack comsumption
> more accurately.
Perhaps some other format of comment should be introduced? Will not
this interfere with linuxdoc?
Pavel
--
934a471f20d6580d5aad759bf0d97ddc
On Tue, Jun 01, 2004 at 08:02:05AM +0200, J?rn Engel wrote:
> Add recursion markers to teach automated test tools how bad documented
> recursions really are. Currently, there is only a single such too that
> can use the information and there is always the danger of documentation
> and reality getting out of sync. But until there's a better tool...
> +/**
> + * RECURSION: 100
> + * STEP: register_proc_table
> + */
This is too ugly for words ;-/ Who will maintain that data, anyway?
On Tue, 1 June 2004 13:39:22 +0100, [email protected] wrote:
>
> > +/**
> > + * RECURSION: 100
> > + * STEP: register_proc_table
> > + */
>
> This is too ugly for words ;-/ Who will maintain that data, anyway?
What format do you propose? I don't care too much.
Maintenance would get easier with less recursions, obviously. ;)
I could hack up something that will generate digests from the function
source code (through smatch or so) and put those digests into the
comments. As long as they match, the comments remain valid. And that
should get past lawyers, as I work on a different basis now.
J?rn
--
Data dominates. If you've chosen the right data structures and organized
things well, the algorithms will almost always be self-evident. Data
structures, not algorithms, are central to programming.
-- Rob Pike
On Tue, 1 June 2004 14:20:13 +0200, Pavel Machek wrote:
>
> Perhaps some other format of comment should be introduced? Will not
> this interfere with linuxdoc?
I'm open for suggestions. ;)
J?rn
--
Data dominates. If you've chosen the right data structures and organized
things well, the algorithms will almost always be self-evident. Data
structures, not algorithms, are central to programming.
-- Rob Pike
Hi!
> > Perhaps some other format of comment should be introduced? Will not
> > this interfere with linuxdoc?
>
> I'm open for suggestions. ;)
/*! Recursion-count: 2 Whatever-else: 5 */
?
Pavel
--
934a471f20d6580d5aad759bf0d97ddc
On Tue, 1 June 2004 15:32:29 +0200, Pavel Machek wrote:
> >
> > I'm open for suggestions. ;)
>
> /*! Recursion-count: 2 Whatever-else: 5 */
What I need is:
1. Recursion count
2. All functions involved in the recursion in the correct order (a
calls b calls c calls d calls a, something like that).
How do you pass 2?
J?rn
--
ticks = jiffies;
while (ticks == jiffies);
ticks = jiffies;
-- /usr/src/linux/init/main.c
Pavel Machek <[email protected]> said:
> =?iso-8859-1?Q?J=F6rn?= Engel <[email protected]> said:
> > > So effectively, it comes down to the recursive paths. Unless someone
> > > comes up with a semantical parser that can figure out the maximum
> > > number of iterations, we have to look at them manually.
> > Linus, Andrew, would you accept patches like the one below? With such
> > information and assuming that the comments will get maintained, it's
> > relatively simple to unroll recursions and measure stack comsumption
> > more accurately.
>
> Perhaps some other format of comment should be introduced? Will not
> this interfere with linuxdoc?
If the comment gets out of sync, you are toast. Too easy for that to
happen, IMVHO.
--
Dr. Horst H. von Brand User #22616 counter.li.org
Departamento de Informatica Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria +56 32 654239
Casilla 110-V, Valparaiso, Chile Fax: +56 32 797513
=?iso-8859-1?Q?J=F6rn?= Engel <[email protected]> said:
[...]
> What I need is:
> 1. Recursion count
How do you know the limit is enforced? By guessing?
> 2. All functions involved in the recursion in the correct order (a
> calls b calls c calls d calls a, something like that).
But also b calls f calls g...
Maintaining the full possible-call-graph is a _huge_ job, better done
automatically (because somebody _will_screw up when doing it by hand). Plus
the fun "structure spicked with all sorts of function pointers" object
implementation in the kernel... note that your carefully maintained call
graph/counts can be screwed up royally by any random third-party device
driver or filesystem module.
--
Dr. Horst H. von Brand User #22616 counter.li.org
Departamento de Informatica Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria +56 32 654239
Casilla 110-V, Valparaiso, Chile Fax: +56 32 797513
On Tue, 1 Jun 2004, Horst von Brand wrote:
>
> If the comment gets out of sync, you are toast. Too easy for that to
> happen, IMVHO.
Yes.
Recursion should be detectable automatically, the only thing you can't
detect easily is the reason to _break_ recursion.
So how about just having a simple loop finder, and then the only comment
you need is a simple /* max recursion: N */ for any point in the loop.
That still makes it interesting if one function is part of two loops, and
is logically the place that breaks the recursion for one (or both - with
different logic) of them. But does that actually happen?
Linus
On Tue, 1 June 2004 12:58:12 -0700, Linus Torvalds wrote:
> On Tue, 1 Jun 2004, Horst von Brand wrote:
> >
> > If the comment gets out of sync, you are toast. Too easy for that to
> > happen, IMVHO.
>
> Yes.
>
> Recursion should be detectable automatically, the only thing you can't
> detect easily is the reason to _break_ recursion.
Correct. My tool already detects recursions and prints warning, it
just cannot make out the harmful ones and gives a warning for each.
> So how about just having a simple loop finder, and then the only comment
> you need is a simple /* max recursion: N */ for any point in the loop.
That's what I basically want, at least for trivial recursions with
only one function involved.
For a->b->c->a type recursions, I also need to identify all involved
functions in the correct order, that's where my ugly format comes
from.
RECURSION: 2
STEP: a
STEP: b
STEP: c
This mean that the recursion from a to b to c and back can happen
twice at most.
Sure, the format is ugly. If anyone really cares I can change it into
any other. But it gets the job done, so I don't care.
> That still makes it interesting if one function is part of two loops, and
> is logically the place that breaks the recursion for one (or both - with
> different logic) of them. But does that actually happen?
"Interesting" is the wrong word, really. Imo it doesn't make any
sense to write such code and therefore I don't want to deal with it
either. Print a warning and be done with it. See my output:
WARNING: multiple recursions around check_sig()
J?rn
--
A victorious army first wins and then seeks battle.
-- Sun Tzu
On Wed, 2 Jun 2004, J?rn Engel wrote:
>
> For a->b->c->a type recursions, I also need to identify all involved
> functions in the correct order, that's where my ugly format comes
> from.
Why?
You really only need to know that _one_ of the entries break the
recursion, and you need to know what the break depth is for that one
entry.
So for example, if "c" is annotated with "max recursion: 5", then you know
that the above loop will recurse at most 5 times.
I don't see why you need any other information.
Linus
On Wed, 2 June 2004 07:15:07 -0700, Linus Torvalds wrote:
> On Wed, 2 Jun 2004, J?rn Engel wrote:
> >
> > For a->b->c->a type recursions, I also need to identify all involved
> > functions in the correct order, that's where my ugly format comes
> > from.
>
> Why?
>
> You really only need to know that _one_ of the entries break the
> recursion, and you need to know what the break depth is for that one
> entry.
>
> So for example, if "c" is annotated with "max recursion: 5", then you know
> that the above loop will recurse at most 5 times.
>
> I don't see why you need any other information.
Then you see something I don't see. For example there are quite a few
recursions with some function like
void foo(int depth)
{
if (!depth) {
bar(1);
}
...
}
bar will, maybe through several more functions call foo(1).
How can you say that foo will beak this recursion after two rounds
max? What if a changed bar decrements the depth value? The recursion
will run for infinity now, won't it? And whoever changed bar doesn't
have a clue that he now fucked up your comment to foo.
I claim:
There is no way to tell the depth of any recursion without looking at
all involved functions.
Prove me wrong, please.
J?rn
--
When in doubt, use brute force.
-- Ken Thompson
On Wed, 2 Jun 2004, Linus Torvalds wrote:
> On Wed, 2 Jun 2004, J?rn Engel wrote:
> >
> > For a->b->c->a type recursions, I also need to identify all involved
> > functions in the correct order, that's where my ugly format comes
> > from.
>
> Why?
>
> You really only need to know that _one_ of the entries break the
> recursion, and you need to know what the break depth is for that one
> entry.
>
> So for example, if "c" is annotated with "max recursion: 5", then you know
> that the above loop will recurse at most 5 times.
>
> I don't see why you need any other information.
Hmmm, I see more data to maintain to support a method that will never be
even close to be perfect. How the thing works with callback triggered
loops for example, where a function is not directly called, but instead is
passed to another function (that maybe pass it to another function) that
triggers the call. Or maybe it's another set of functions that might
trigger the call (think about all *_operations for example). Eg, there's
an evident loop possibility in epoll (triggered by callback'd wakeups)
that is not in the list, and it's pretty hard to detect. Doing stack usage
analisys from the source code is not easy, once you abbandon the trivial
direct call scenario.
- Davide
On Wed, 2 Jun 2004, J?rn Engel wrote:
>
> Then you see something I don't see. For example there are quite a few
> recursions with some function like
>
> void foo(int depth)
> {
> if (!depth) {
> bar(1);
> }
> ...
> }
>
> bar will, maybe through several more functions call foo(1).
>
> How can you say that foo will beak this recursion after two rounds
> max?
The programmer had _better_ know that there is some upper limit.
> I claim:
> There is no way to tell the depth of any recursion without looking at
> all involved functions.
And I claim: recursion is illegal unless the programmer has some explicit
recursion limiter. And if he has that recursion limiter in one of the
functions, then he damn well better know it, and know the value it limits
recursion to.
Linus
On Wed, 2 June 2004 07:45:10 -0700, Linus Torvalds wrote:
>
> The programmer had _better_ know that there is some upper limit.
>
> And I claim: recursion is illegal unless the programmer has some explicit
> recursion limiter. And if he has that recursion limiter in one of the
> functions, then he damn well better know it, and know the value it limits
> recursion to.
Can I read this as:
Linus himself will use strong words to enforce all recursions in the
kernel to be either removed or properly documented.
In that case, you have 273 recursions to deal with. They are all in
the data I attached a few posts back. Recursions would basically be
in the same league as huge stack hogs, sounds good.
J?rn
--
Write programs that do one thing and do it well. Write programs to work
together. Write programs to handle text streams, because that is a
universal interface.
-- Doug MacIlroy
On Wed, 2 Jun 2004, J?rn Engel wrote:
>
> Can I read this as:
> Linus himself will use strong words to enforce all recursions in the
> kernel to be either removed or properly documented.
If we have a good detector that is reliable and easy to run, why not?
It will take some time, but I think the problem so far has been that the
recursion can be hard to see. Some "core" cases are well-known (memory
allocations during memory allocation, and filename lookup), and they
should be trivial to annotate. Knock wood. Others might be worse.
> In that case, you have 273 recursions to deal with. They are all in
> the data I attached a few posts back. Recursions would basically be
> in the same league as huge stack hogs, sounds good.
Yes. And with huge stack hogs, we've not exactly "fixed them all in a
weekend", have we? But having a few people run the checking tools and
nagging every once in a while ends up eventually fixing things. At least
the most common ones.
Linus
On Wed, 2 June 2004 08:12:00 -0700, Linus Torvalds wrote:
> On Wed, 2 Jun 2004, J?rn Engel wrote:
> >
> > Can I read this as:
> > Linus himself will use strong words to enforce all recursions in the
> > kernel to be either removed or properly documented.
>
> If we have a good detector that is reliable and easy to run, why not?
Great! So the official format to document recursions is plain english
for human readers?
> It will take some time, but I think the problem so far has been that the
> recursion can be hard to see. Some "core" cases are well-known (memory
> allocations during memory allocation, and filename lookup), and they
> should be trivial to annotate. Knock wood. Others might be worse.
For sure. There are some functions with multiple recursions around
them, real fun! :)
> > In that case, you have 273 recursions to deal with. They are all in
> > the data I attached a few posts back. Recursions would basically be
> > in the same league as huge stack hogs, sounds good.
>
> Yes. And with huge stack hogs, we've not exactly "fixed them all in a
> weekend", have we? But having a few people run the checking tools and
> nagging every once in a while ends up eventually fixing things. At least
> the most common ones.
s/a few people/J?rn/
Legal reasons. I'll try to do this from time to time.
J?rn
--
To recognize individual spam features you have to try to get into the
mind of the spammer, and frankly I want to spend as little time inside
the minds of spammers as possible.
-- Paul Graham
On Wed, 2 Jun 2004, J?rn Engel wrote:
> >
> > If we have a good detector that is reliable and easy to run, why not?
>
> Great! So the official format to document recursions is plain english
> for human readers?
Actually, I'd suggest making it a preprocessor directive at the very top
of the function itself. That way I can make sparse parse it too if I ever
want to.
So something like
/*
* This function is part of recursion, but we limit
* the depth with the "depth" parameter to 5
*/
int my_recursive_function(int depth, struct datastruct *arg)
{
declare_recursion_depth(5);
...
where we could either just #define it to some no-op like
#define declare_recursion_depth(x) \
extern void __dummy_function_never_used()
or even do something fancier:
#define declare_recursion_depth(x) \
static __init char recursion[] = __FILE__ ":" __FUNCTION__ "=" #x;
which will generate a nice clean variable that shows up in "objdump" in
all its glory, so that pretty much any tool can trivially parse it.
And for something like sparse or other automated tools, we can trivially
make it be something more appropriate, ie
#define recursion_depth(x) \
__builtin_recursion_depth(x)
or whatever checker-specific thing we want it to be.
And other tools should be equally able to easily pick it up, either by
just looking at the object file or re-defining the macro to suit
themselves.
I think the above syntax is both human-readable and "obviously parseable"
in many trivial ways. Whaddaya think? Works for you?
Linus
On Wed, 2 June 2004 08:52:53 -0700, Linus Torvalds wrote:
>
> I think the above syntax is both human-readable and "obviously parseable"
> in many trivial ways. Whaddaya think? Works for you?
Works for me for trivial recursions (just one function involved. With
a little more pain, it should work for basically everything. Only
exception are multiple recursions around the same function. So unless
you like to keep those suckers, I'm fine with it.
J?rn
--
The cheapest, fastest and most reliable components of a computer
system are those that aren't there.
-- Gordon Bell, DEC labratories
On Wed, 2 Jun 2004, J?rn Engel wrote:
>
> Works for me for trivial recursions (just one function involved. With
> a little more pain, it should work for basically everything. Only
> exception are multiple recursions around the same function. So unless
> you like to keep those suckers, I'm fine with it.
Well, multiple recursion around the same function seems to be solvable two
different ways:
- "don't do that then". It really seems broken, but maybe there are
really really good reasons _why_ it's not broken and why it happens.
- make sure that the separate loops are broken in some _other_ place than
in the function they share.
A combination of the two may work well.
I say "may", because maybe I'm wrong, and the condition is common and hard
to avoid limiting in the shared function. I don't have your data (and I'm
lazy, so quite frankly I'd much rather you do the analysis anyway ;).
That said, I just don't see any sane alternatives to my "break in one
place" thing. I believe that anything more complex that tries to explain
the whole loop is just going to be a nightmare to maintain, and fragile as
hell except for totally static legacy code that nobody touches any more.
Linus
On Wed, 2 June 2004 09:25:50 -0700, Linus Torvalds wrote:
>
> Well, multiple recursion around the same function seems to be solvable two
> different ways:
> - "don't do that then". It really seems broken, but maybe there are
> really really good reasons _why_ it's not broken and why it happens.
> - make sure that the separate loops are broken in some _other_ place than
> in the function they share.
>
> A combination of the two may work well.
>
> I say "may", because maybe I'm wrong, and the condition is common and hard
> to avoid limiting in the shared function. I don't have your data (and I'm
> lazy, so quite frankly I'd much rather you do the analysis anyway ;).
You *do* have my data, but I buy the lazy argument. ;)
> That said, I just don't see any sane alternatives to my "break in one
> place" thing. I believe that anything more complex that tries to explain
> the whole loop is just going to be a nightmare to maintain, and fragile as
> hell except for totally static legacy code that nobody touches any more.
Amen, brother. Anything complicated will contain bugs tomorrow, if
not already today.
Let's see. Right now, we have two cases of multiple recursions:
WARNING: multiple recursions around check_sig()
WARNING: multiple recursions around usb_audio_recurseunit()
check_sig() is bad code and can be cleaned up.
Leaves usb_audio_recurseunit() as the only function in question, that
one could actually be sane, although it looks rather interesting:
WARNING: trivial recursion detected:
0 usb_audio_recurseunit
WARNING: recursion detected:
16 usb_audio_selectorunit
0 usb_audio_recurseunit
WARNING: multiple recursions around usb_audio_recurseunit()
WARNING: recursion detected:
0 usb_audio_recurseunit
0 usb_audio_processingunit
Greg, can you say whether this construct makes sense?
J?rn
--
Eighty percent of success is showing up.
-- Woody Allen
On Wed, Jun 02, 2004 at 07:17:32PM +0200, J?rn Engel wrote:
>
> Leaves usb_audio_recurseunit() as the only function in question, that
> one could actually be sane, although it looks rather interesting:
> WARNING: trivial recursion detected:
> 0 usb_audio_recurseunit
> WARNING: recursion detected:
> 16 usb_audio_selectorunit
> 0 usb_audio_recurseunit
> WARNING: multiple recursions around usb_audio_recurseunit()
> WARNING: recursion detected:
> 0 usb_audio_recurseunit
> 0 usb_audio_processingunit
>
> Greg, can you say whether this construct makes sense?
Well it's sane only if you think that USB descriptors can be sane :)
Anyway, this loop will always terminate as we have a finite sized USB
descriptor that this function is parsing. As to how many times we will
recurse, I don't really know as I haven't spent much time looking into
the different messed up USB audio devices out there on the market...
Sorry I can't be of more help, but I don't think you need to worry about
this function.
thanks,
greg k-h
On Wed, 2 June 2004 10:32:00 -0700, Greg KH wrote:
> On Wed, Jun 02, 2004 at 07:17:32PM +0200, J?rn Engel wrote:
> >
> > Leaves usb_audio_recurseunit() as the only function in question, that
> > one could actually be sane, although it looks rather interesting:
> > WARNING: trivial recursion detected:
> > 0 usb_audio_recurseunit
> > WARNING: recursion detected:
> > 16 usb_audio_selectorunit
> > 0 usb_audio_recurseunit
> > WARNING: multiple recursions around usb_audio_recurseunit()
> > WARNING: recursion detected:
> > 0 usb_audio_recurseunit
> > 0 usb_audio_processingunit
> >
> > Greg, can you say whether this construct makes sense?
>
> Well it's sane only if you think that USB descriptors can be sane :)
>
> Anyway, this loop will always terminate as we have a finite sized USB
> descriptor that this function is parsing. As to how many times we will
> recurse, I don't really know as I haven't spent much time looking into
> the different messed up USB audio devices out there on the market...
>
> Sorry I can't be of more help, but I don't think you need to worry about
> this function.
That's ok. At least you can talk about that code without obvious
disgust, which is a quality criterium in itself.
Leaves exactly one multiply recursive function we might want to keep.
So I just won't worry too much and ignore the warnings about it, fine.
J?rn
--
ticks = jiffies;
while (ticks == jiffies);
ticks = jiffies;
-- /usr/src/linux/init/main.c
On Wed, 2 June 2004 07:35:39 -0700, Davide Libenzi wrote:
>
> Hmmm, I see more data to maintain to support a method that will never be
> even close to be perfect.
You get it wrong. This is mainly about Bad Code or Insufficient
Documentation. In general, I want recursions to be removed, full
stop. So there is not more data, but less.
If the recursion is actually wanted, then those cases should either be
so few and obvious that a single person can explain them all from
memory. That, or things have to be written down somehow and unless
you have a better suggestion, any format is better than nothing.
J?rn
--
Public Domain - Free as in Beer
General Public - Free as in Speech
BSD License - Free as in Enterprise
Shared Source - Free as in "Work will make you..."
On Wed, 2 Jun 2004, [iso-8859-1] J?rn Engel wrote:
> On Wed, 2 June 2004 07:35:39 -0700, Davide Libenzi wrote:
> >
> > Hmmm, I see more data to maintain to support a method that will never be
> > even close to be perfect.
>
> You get it wrong. This is mainly about Bad Code or Insufficient
> Documentation. In general, I want recursions to be removed, full
> stop. So there is not more data, but less.
You're requesting to add and maintain data to feed a tool that catches
only trivially visible recursion. I don't want to waste mine and your time
explaining why your tool will never work, but if you want an hint, you can
start thinking about all functions that sets/pass callbacks and/or sets
operational functions. I don't know if you noticed that, but Linux is
heavily function-pointer driven. Eg, one function setups a set of function
pointers, and another 317 indirectly calls them. Having such comments, not
only makes the maintainance heavier, but gives the false sense of safeness
that once you drop that data in, you're protected against recursion.
- Davide
On Wed, 2 June 2004 11:37:50 -0700, Davide Libenzi wrote:
>
> You're requesting to add and maintain data to feed a tool that catches
> only trivially visible recursion. I don't want to waste mine and your time
> explaining why your tool will never work, but if you want an hint, you can
> start thinking about all functions that sets/pass callbacks and/or sets
> operational functions. I don't know if you noticed that, but Linux is
> heavily function-pointer driven. Eg, one function setups a set of function
> pointers, and another 317 indirectly calls them. Having such comments, not
> only makes the maintainance heavier, but gives the false sense of safeness
> that once you drop that data in, you're protected against recursion.
Yeah, I know about the problems to generate a complete call graph.
With function pointers, it is plain impossible to get it right in the
most general case.
Note the "in the most general case" part. You can get things right if
you make some assumptions and those assumptions are actually valid.
In my case the assumptions are:
1. all relevant function pointers are stuffed into some struct and
2. no casts are used to disguise function pointer as something else.
If you stick with those rules, the resulting code is quite sane, which
is much more important than any tools being usable. If the kernel
doesn't stick to those rules for a good reason, I'd like to know about
it, so I can adjust my tool. And if the kernel doesn't stick to those
rules for no good reason, the code if broken and needs to be fixed.
Is this sane?
J?rn
--
A victorious army first wins and then seeks battle.
-- Sun Tzu
On Wed, 02 Jun 2004 20:58:32 +0200, =?iso-8859-1?Q?J=F6rn?= Engel said:
> Note the "in the most general case" part. You can get things right if
> you make some assumptions and those assumptions are actually valid.
> In my case the assumptions are:
> 1. all relevant function pointers are stuffed into some struct and
> 2. no casts are used to disguise function pointer as something else.
That seems to be reasonable. And if we're aliasing, or shadowing, or casting
function pointers to something else, or using a union to overlay it, that's
just a time bomb waiting to explode. At the very least, such code should
require a large "Danger! Here be large and nasty dragons!" marker.
On Wed, Jun 02, 2004 at 08:58:32PM +0200, J?rn Engel wrote:
> Note the "in the most general case" part. You can get things right if
> you make some assumptions and those assumptions are actually valid.
> In my case the assumptions are:
> 1. all relevant function pointers are stuffed into some struct and
Wrong. They are often passed as arguments to generic helpers, without
being ever put into any structures.
On Wed, 2 June 2004 20:37:20 +0100, [email protected] wrote:
> On Wed, Jun 02, 2004 at 08:58:32PM +0200, J?rn Engel wrote:
> > Note the "in the most general case" part. You can get things right if
> > you make some assumptions and those assumptions are actually valid.
> > In my case the assumptions are:
> > 1. all relevant function pointers are stuffed into some struct and
>
> Wrong. They are often passed as arguments to generic helpers, without
> being ever put into any structures.
Ok. Would it be ok to use the following then?
b1. Function pointer are passed as arguments to functions and
b2. those pointer are called directly from the function, they are
passed to.
Either that or the previous two rules, renamed to a1 and a2.
(Note that I care more about sane rules than what any random code in
some dark corner happens to do right now.)
J?rn
--
A surrounded army must be given a way out.
-- Sun Tzu
On Wed, 02 Jun 2004 20:37:20 BST, [email protected] said:
> Wrong. They are often passed as arguments to generic helpers, without
> being ever put into any structures.
At least those can *hopefully* be automatically detected by looking at the
function's definition. Are there any known cases where they're "passed
through" from caller to generic_a to generic_b which ends up calling the
function via pointer, or is it restricted to caller, generic_a, *(pointer)?
On Wed, Jun 02, 2004 at 09:45:15PM +0200, J?rn Engel wrote:
> On Wed, 2 June 2004 20:37:20 +0100, [email protected] wrote:
> > On Wed, Jun 02, 2004 at 08:58:32PM +0200, J?rn Engel wrote:
> > > Note the "in the most general case" part. You can get things right if
> > > you make some assumptions and those assumptions are actually valid.
> > > In my case the assumptions are:
> > > 1. all relevant function pointers are stuffed into some struct and
> >
> > Wrong. They are often passed as arguments to generic helpers, without
> > being ever put into any structures.
>
> Ok. Would it be ok to use the following then?
>
> b1. Function pointer are passed as arguments to functions and
> b2. those pointer are called directly from the function, they are
> passed to.
Again not guaranteed to be true - they can be (and often are) passed further.
Moreover, they are also stored untyped in structures. Common pattern
is
foo.callback = f;
foo.argument = p;
iterate_over_blah(blah, &foo);
Note that here f is the only thing that will see the value of p _and_ the
only thing that cares about type of p. iterator itself doesn't care and
can be used for different types.
On Wed, 2 Jun 2004, [iso-8859-1] J?rn Engel wrote:
> Yeah, I know about the problems to generate a complete call graph.
> With function pointers, it is plain impossible to get it right in the
> most general case.
>
> Note the "in the most general case" part. You can get things right if
> you make some assumptions and those assumptions are actually valid.
> In my case the assumptions are:
> 1. all relevant function pointers are stuffed into some struct and
> 2. no casts are used to disguise function pointer as something else.
>
> If you stick with those rules, the resulting code is quite sane, which
> is much more important than any tools being usable. If the kernel
> doesn't stick to those rules for a good reason, I'd like to know about
> it, so I can adjust my tool. And if the kernel doesn't stick to those
> rules for no good reason, the code if broken and needs to be fixed.
>
> Is this sane?
Think at file_operations as very simple example, and try to find out what
is actually called when somewhere the code does f_op->*(). How would you
build the graph down there. You'd have to record all the functions that
have been assigned to such method throughout the code, and nest *all*
their graph in place. And this will eventually trigger false positives.
Similar thing with functions that accepts callbacks, either directly or
inside structures. And this doesn't even start to take aliasing into
account. Hunting stack hungry functions is very good, and having a tool
that is maybe 60% precise in detecting loops is fine too. But requiring
metadata to be maintained to support such tool is IMO wrong.
- Davide
On Wed, 2 June 2004 20:59:44 +0100, [email protected] wrote:
> >
> > Ok. Would it be ok to use the following then?
> >
> > b1. Function pointer are passed as arguments to functions and
> > b2. those pointer are called directly from the function, they are
> > passed to.
>
> Again not guaranteed to be true - they can be (and often are) passed further.
Hmm. If that happens, I'm out of ideas for now. Cannot do more than
give a warning.
> Moreover, they are also stored untyped in structures. Common pattern
> is
> foo.callback = f;
> foo.argument = p;
> iterate_over_blah(blah, &foo);
>
> Note that here f is the only thing that will see the value of p _and_ the
> only thing that cares about type of p. iterator itself doesn't care and
> can be used for different types.
Those cases I should already catch. If foo is of type "struct bar",
"bar.callback" will be the function name for a pseudo-function. That
function is called by iterate_over_blah and calls f. Unnamed struct
get a name made up from the components of the struct, like
____FAKE.Name.Chip.stat.Regi.LILP.Opti.high.lowe->ProcessIMQEntry.
Doesn't look pretty, but works.
J?rn
--
Time? What's that? Time is only worth what you do with it.
-- Theo de Raadt
On Wed, 2 June 2004 16:20:24 -0700, Davide Libenzi wrote:
>
> Think at file_operations as very simple example, and try to find out what
> is actually called when somewhere the code does f_op->*(). How would you
> build the graph down there. You'd have to record all the functions that
> have been assigned to such method throughout the code, and nest *all*
> their graph in place. And this will eventually trigger false positives.
Bad example, I can deal with that just fine. :)
Any code calling f_op->read must not break for any f_op->read. So it
is perfectly sane to assume that all get called. I build the graph by
turning f_op->read into a pseudo-function that calls all functions
ever assigned to f_op->read.
> Similar thing with functions that accepts callbacks, either directly or
> inside structures.
Those I only handle, if the callbacks are inside structures, true.
Will fix it when I find the time for it.
> And this doesn't even start to take aliasing into
> account.
What exactly do you call aliasing? Do you have an example?
> Hunting stack hungry functions is very good, and having a tool
> that is maybe 60% precise in detecting loops is fine too. But requiring
> metadata to be maintained to support such tool is IMO wrong.
Since Linus feels that said metadata is still useful without any
tools, I'll just ignore this objection. ;)
Still, some of the complaints were valid, thanks a bunch! My todo
list has grown again.
J?rn
--
Write programs that do one thing and do it well. Write programs to work
together. Write programs to handle text streams, because that is a
universal interface.
-- Doug MacIlroy