Summary:ASTERISK-03081: [PATCH] make AST_LIST_TRAVERSE safe against entry modification
Reporter:Kevin P. Fleming (kpfleming)Labels:
Date Opened:2004-12-23 13:10:35.000-0600Date Closed:2008-01-15 15:19:19.000-0600
Versions:Frequency of
Environment:Attachments:( 0) list_traverse_safety_rev3.diff.txt
Description:This patch is a bit invasive (especially to any out-of-tree code that uses AST_LIST_TRAVERSE), but it is worth the pain, IMHO.

The idea here is to make it safe for users of AST_LIST_TRAVERSE to be able to modify the current entry's forward-link pointer (by putting it into another list, for example) or completely free the current entry, without breaking the traversal. This is done by precomputing the "next" entry pointer before the user's code does any manipulation of the current entry.

The downside to the patch is that AST_LIST_TRAVERSE has become a BEGIN/END macro pair. This is needed because the "next" pointer needs to be stored in a block-local variable. The patch brings all existing uses of AST_LIST_TRAVERSE in the tree in line with the new syntax.

Patch is relative to the patch in bug 3139.


Disclaimer is on file.
Comments:By: Mark Spencer (markster) 2004-12-23 17:15:37.000-0600

How about just adding a new macro called AST_LIST_TRAVERSE_SAFELY rather than change this one, assuming you need th enew safe version for something.

By: Kevin P. Fleming (kpfleming) 2004-12-23 17:51:27.000-0600

Could be... are you concerned about the impact on out-of-tree modules? If not, the changes to the existing modules are fairly obvious, so should be safe.

And yes, the new version is needed to solve the segfault problems in bug 3067; it's also better for people who try to use it in the future, so they won't run into the problems I did by not realizing the side effects of manipulating the current list entry during a list traversal.

Just so you know, all this list-macro related work is coming because I have nearly completed converting app_queue to using the list macros (and simpler locking) for all of its internal structures. Once these baseline patches have been merged, I'll be posting an experimental patch for app_queue so that people can try it out. The code is much clearer, easier to read and more logical now that it's using the same list processing for everything.

By: khb (khb) 2004-12-24 01:57:12.000-0600

Seems to me that the existing macro is a lot more intuitive and effective for most  or all existing applications.  Adding another parameter to the macro destroys the transparency of meaning and does, in fact, NOT add to readability.  If this is really needed, then it should be used locally where needed.  The added complexity harbors potentially more pitfalls than currently.  Creating built-in insurance policies into code against abuse or ignorance is expensive and is not the style of efficient C language programming.

By: Kevin P. Fleming (kpfleming) 2004-12-24 08:47:06.000-0600

Well, I will agree that it is somewhat less readable, but I won't agree that adding a parameter "destroys the transparency". It now has the same parameter list as 3 or 4 other list macros, and I don't see how having to provide the _type_ of the list entries when you are asking to traverse over those same entries is any sort of burden at all.

As far as using it "locally", with the existing macro this cannot be done; there is no way to use the existing macro safely. At a minimum, this new version should go in with a different name.

Finally, the code already has lots of "insurance" against abuse or ignorance, and it's not expensive in this case at all. In fact, I did a micro benchmark on this change, and the generated code is so close in both cases that the benchmark showed a negligible difference (and zero difference for the list lengths that would be common in Asterisk). This identical technique is used in a "safe" list traversal macro in the Linux kernel, and there is no complaint about it being "inefficient".

I'll post a new version of the patch with the existing macro left alone and the new version named appropriately, which will not require modification of existing users (except in cases where they benefit from the "safe" version).

By: Kevin P. Fleming (kpfleming) 2004-12-24 09:50:02.000-0600

New patch uploaded, new macro has a different name, so no existing uses have been modified.

By: Kevin P. Fleming (kpfleming) 2005-01-01 15:35:18.000-0600

Mark, you merged this in CVS. Do you want reassign and resolve this bug?

By: Mark Spencer (markster) 2005-01-01 15:58:24.000-0600

Added to CVS, but don't you think the ast_list is now basically obsolessant in light ast_obj?

By: Russell Bryant (russell) 2005-01-03 23:58:42.000-0600

not in 1.0

By: Digium Subversion (svnbot) 2008-01-15 15:19:19.000-0600

Repository: asterisk
Revision: 4629

U   trunk/apps/app_sql_postgres.c
U   trunk/channel.c
U   trunk/include/asterisk/linkedlists.h
U   trunk/pbx/pbx_dundi.c
U   trunk/pbx/pbx_loopback.c
U   trunk/pbx.c

r4629 | markster | 2008-01-15 15:19:18 -0600 (Tue, 15 Jan 2008) | 2 lines

List improvements from kpfleming (bugs ASTERISK-3105,ASTERISK-3081)