Summary:ASTERISK-03285: [PATCH] new ASTOBJ implementation, including hash-table containers
Reporter:Kevin P. Fleming (kpfleming)Labels:
Date Opened:2005-01-15 20:25:22.000-0600Date Closed:2011-06-07 14:04:52
Versions:Frequency of
Environment:Attachments:( 0) astobj_function_model_rev3.diff.txt
Description:This patch includes an entirely new ASTOBJ implementation, that uses fewer macros (generally one per object) and also provides a great deal of new functionality.

Essentially, the new implementation requires one macro call per object, to define the object. That macro creates the object's structure definition, along with related structures and all the functions needed to manipulate that object (all of them are created as "static inline" functions).

Some of the highlights of this new implementation:

- list- and hashtable-based object containers
- no need to repeat information about the object, hashing, comparison, types, etc. at each call (all of this information is embedded into the method functions that are created by the definition macro)
- use of atomic operations (on Linux only for now) to eliminate pthread lock operations for reference counts
- expanded debugging CLI commands, including statistics of hashtable distribution (these can be turned off in the Makefile)
- much simpler "traversal" mechanics (don't require putting a block of code into a macro argument), which makes debugging of traversal code far easier
- SIP peers are now doubly-indexed (on name and IP address), eliminating the need for sip_addrcmp to forcibly cast a char * back into a struct sip_peer *
- reduced memory consumption for object names (only the space needed is allocated)
- "insert tail" and "insert after" methods for list-based containers
- infrastructure is in place to support multiple simultaneous iterators (traversals); for list-based containers this will not be possible without switching to rwlocks, but for hashtable-based containers it will allow multiple iterators (in multiple threads) as long as they are traversing different buckets

The patch is currently very light on documentation, but as it gets closer to being deployable I will create full doxygen docs for the new macros and methods.

I have personally tested this patch on a box with over 4,300 SIP "friends" defined, in both list- and hashtable-based modes without trouble. However, that is not an SMP box, nor is it stressed, so the patch needs additional testing in different environments. Silikon has offered a testing box, and Hermie is going to put together some scenario files for SIPp to stress test it.

(Note: This patch also contains the code from ASTERISK-3323352, but in a different form since it touches that code).


Disclaimer is on file.
Comments:By: Mark Spencer (markster) 2005-01-16 00:43:46.000-0600

1) Debug should not be enabled in the Makefile by default (duh!, i assume this was just an oversight)

2) I don't want any unnecessary mallocs including those for the list containers.

3) Right now, I'm just generally unconvinced that this is an improvement over the existing system.  This, while perhaps more automated, appears to take away from the simple (if simplistic) transparency of the existing system.

I place a very strong premium on simplicity, and I'm not convinced that the complication this adds is worth its merit, but I'm certainly open to discussion.

By: Kevin P. Fleming (kpfleming) 2005-01-16 09:02:35.000-0600

1) Debug is turned on for now because this is experimental (and it only provides the same functionality that is already available by default in CVS HEAD).

2) The point of using "_new" for list containers is so that you can create _multiple_ containers of the same type; I have an application that wants to grab a bunch of entries from an existing "master" list and transfer them to a new list. This allows that function to create a temporary container, transfer the items, do its work and then destroy the items. If the containers are statically allocated, this is not possible, without completely redefining the container type again (and having to keep that definition in sync with any others). This patch adds no more mallocs than those; there are no additional mallocs for regular objects than currently exist.

3) I think if you review the changes to chan_sip specifically, you'll see that the users of this implementation are given a far simpler interface to deal with, and it's much more maintainable (since there is no repetition of details, thus there is no chance for them to be incorrectly repeated). Certainly the implementation in astobj.h is more complex, but does that actually affect the users? When a developer wants add this functionality to their module/app, they are just going to read the docs on the published interface and go about their business...

I spent many hours trying to work with the existing implementation to extend it to support multiple indexes, hash tables, atomic refcounts and the other bits. In the end, it was very difficult to work with, and the macros in astobj.h were far more complex than these new ones. In addition, because that complication had to be handled by the compiler on every single macro invocation, it likely would have taken far longer to compile, and it was nearly impossible to debug with gdb (since any failure in the macro can only show you the macro call, not the line of code that actually failed).

By: Mark Spencer (markster) 2005-01-16 10:19:40.000-0600

Understood with respect to the debug, when you have a version you want me to merge just be sure it's not got the debug set or i'll forget to turn it back off :)

Imagine for the moment a struct (or object) which in turn contains a container.  If your only interface to the container is to have to malloc it, then it forces an additional malloc on said object.

How about we have a _init and _new, giving us the capability to declare either the static structure and _init it or call _new to create one?

I certainly agree that inline functions are easier to debug than are macros, but can't we keep the traverse macro?

Why is ASTOBJ_COUNTER a #define as opposed to a typedef, out of curiosity?

The definitions in asm/atomic.h seems to suggest that it's not useful for userspace.  In any case, can we avoid using their atomic routines and come up with a brief set of our own?

By: Mark Spencer (markster) 2005-01-16 10:25:11.000-0600

Also, in your next rev of whichever patch, please updated CREDITS to add an appropriate entry for yourself.  Thanks!

By: Kevin P. Fleming (kpfleming) 2005-01-16 10:49:17.000-0600

You are correct, a statically allocated container would be a useful thing, so I'll create an _init method for them.

The traverse macro is actually what caused me to switch away from macro calls; I was fighting problems in chan_sip and couldn't debug them effectively because they were occurring inside the eval-block and the debugger can't see any of that. The new iterator methods are pretty simple (three function calls, four if you want to peek ahead), don't mess with your variable namespace (you can call the iterator anything you want, which means you can iterate inside an iterator and still be able to reference the outer loop's current entry) and they also use the "natural" method of leaving the loop early (break) instead of having to set some condition to be checked.

ASTOBJ_COUNTER: I don't know that there's a reason... I was just in the habit of doing those #defines for atomic vs. non-atomic and it was the pattern :-) It could certainly be a typedef instead.

The Linux kernel atomic routines actually do work properly in userspace, as long as you define CONFIG_SMP to make them use LOCK prefixes (that's why the huge warning in asterisk/atomic.h). I tried in vain to find a set of atomic operations with a non-GPL license that implemented decrement-and-test, because that particular operation is needed for reference counting.

I cannot write a set of alternative atomic operations, as I have already seen the Linux kernel ones and invariably they would end up the same. In fact, unless you make them _less_ efficient, _any_ x86 atomic operations will use the identical code as the Linux kernel ones do, as they are the most efficient way to get the job done. I don't know how to deal with that; even if someone spent all the time to learn x86 assembly and write them, they would end up the same, and I don't know what the legal/licensing issues around that are. It seemed safer to just use the existing ones (and there is already a movement afoot on the Linux kernel mailing list to make "official" userspace versions of these available, so I know they are safe to use).

By: Mark Spencer (markster) 2005-01-16 11:08:34.000-0600

How about we defer the atomic stuff until we see how the debate on the linux kernel mailing list goes?  If we get nice approved userspace atomic locks, that would be better.

If someone writes code independently of the linux code and ends up with the same code, that does not constitute a copyright infringment (ooh, the things you can learn from groklaw).

By: Kevin P. Fleming (kpfleming) 2005-01-16 11:15:32.000-0600

Sure, I can make the Linux atomic.h include non-functional in the patch for now (although I'll continue to use it locally <G>).

If you can find someone who can take the FreeBSD atomic operations header file and safely add dec_and_test to it, then we can use that for all platforms supported by FreeBSD (that's another advantage of using the ones from the Linux kernel, we get all architecture support for free). However, the Asterisk Makefiles will have to know what arch we are building for so they can include the proper atomic.h file, which will require more time to create and test than I can provide (since using the Linux files works for me!).

By: nick (nick) 2005-01-16 11:27:50.000-0600

I think we may have a winner: http://synesis.com.au/software/stlsoft/help/unixstl__atomic__functions_8h-source.html

It's written in that language that I love, C++, but it should be trivial to convert.  The license says:
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

- Redistributions of source code must retain the above copyright notice, this
  list of conditions and the following disclaimer.
- Redistributions in binary form must reproduce the above copyright notice,
  this list of conditions and the following disclaimer in the documentation
  and/or other materials provided with the distribution.
- Neither the name(s) of Matthew Wilson and Synesis Software nor the names of
  any contributors may be used to endorse or promote products derived from
  this software without specific prior written permission.

If that meets Mark's approval (looks to me basically just like the old BSD license) then I'd be happy to whip it into shape.

By: Mark Spencer (markster) 2005-01-16 11:28:41.000-0600

Okay, fantastic.  You might even say "this is where you would link to userspace atomic stuff" or whatever.  Just don't have it on by default or anything.

By: Kevin P. Fleming (kpfleming) 2005-01-16 11:37:45.000-0600


That looks interesting (and in fact even the comments are the same as the ones in the Linux kernel header), but it's x86 only. I'm curious as to the source of the Linux kernel operations now, since the "gcc alias warning" comment is a direct copy of the one from this file.

In any case Mark, the operations in this file are _identical_ to the ones in the Linux kernel, and the kernel ones are provided for 20+ architectures. In my mind, the only reason not to use the kernel ones would be a licensing issue, not a safety issue, since the code is the same.

By: nick (nick) 2005-01-16 12:39:35.000-0600

Sure enough... I was trying not to look at the Linux stuff so I could be a blind implementor, but after looking, Kevin is right--their atomic stuff is exactally the same, which is cute.

But, like Mark said, it would be easy enough to compile the atomic stuff in or out... so I guess this is kind of a non-issue.


By: Mark Spencer (markster) 2005-01-16 16:41:35.000-0600

Okies well at least we're on the same page, I think :)

By: Mark Spencer (markster) 2005-01-17 07:57:18.000-0600

Okies I think we're just waiting on the updated implementation with _init and the other comments then.

By: Kevin P. Fleming (kpfleming) 2005-01-18 08:12:09.000-0600

Yes, and I've been swamped the last few days. I may be able to post a new version tonight, but it will probably be Thursday.

By: nick (nick) 2005-01-18 19:24:30.000-0600

Hrm... I can't even get this to compile on my box.  First of all, the atomic functions in 2.4 don't include dec_and_test().  After fixing that, I get this while compiling:
acl.c:52: warning: `__warn_unused_result__' attribute directive ignored
acl.c:52: warning: `__warn_unused_result__' attribute directive ignored
acl.c:54: warning: `__warn_unused_result__' attribute directive ignored
acl.c: In function `ast_netsock_list_link':
acl.c:54: invalid type argument of `->'

...with the "invalid type argument" message repeating ad nauseam for each of the called inline functions in astobj.h.


By: Kevin P. Fleming (kpfleming) 2005-01-18 19:33:14.000-0600

What is your compiler version?

I didn't realize the 2.4 kernel headers did not include the dec_and_test function; in that case, if we leave the patch using the kernel-provided functions, we'll have to test the kernel version at compile time (not that it will matter if you compile on 2.6 and then move back to 2.4, since the atomic functions don't actually call into the kernel anyway).

I suspect the right course of action will be to disable the use of the kernel-provided functions by default, but put a note somewhere in the Makefile telling the user how to use them if they wish (and known limitations of enabling that feature).

By: nick (nick) 2005-01-18 19:42:33.000-0600

gcc (GCC) 3.2.2 20030222

It's not the newest, but it seems like it should be "supportably old"... although  I really should upgrade some time soon (grumble...).


By: Kevin P. Fleming (kpfleming) 2005-01-18 19:47:39.000-0600

OK, I'm going to move those compiler-specific defines into a new header file (asterisk/compiler.h) and then do a better job of determining which ones are supported by which versions of GCC (obviously the docs I was using are incomplete). Look for the changes in rev4, due to hit this bug in 48 hours or so...

By: Mark Spencer (markster) 2005-01-25 22:09:17.000-0600

Okay it's been about 168, what should we do?

By: Kevin P. Fleming (kpfleming) 2005-01-26 10:41:45.000-0600

Sorry, I've been busy (and ill) the last couple of days. Once I get over this bug I'll get the new rev uploaded.

edited on: 01-26-05 10:42

By: Mark Spencer (markster) 2005-02-08 01:44:07.000-0600

*poke* You about ready to give us another update here?

By: Mark Spencer (markster) 2005-03-02 23:07:44.000-0600

Lets try to finish this at VON, or close it until you have time to finish it.  Thanks!

By: Kevin P. Fleming (kpfleming) 2005-03-02 23:47:29.000-0600

Yes, that's a good plan... I think it will take some "work together" time to get it completed, and doing it over the phone is not as efficient as it could be :-)

By: Olle Johansson (oej) 2005-03-03 02:15:25.000-0600

For readability, I would like that everytime we include astobject in a structure, that we add a comment line saying what extra parameters are included, like "name" which is very important...

By: Kevin P. Fleming (kpfleming) 2005-03-03 10:10:39.000-0600

I don't mind doing that for things like 'name', but I don't really want to include all the fields, because then if the core astobj definitions get changed to include some more 'internal' fields, all those comments have to be updated...

How about we make the policy that the comments will list the fields that are intended for the user to use, but not the internal-use-only ones?

By: Olle Johansson (oej) 2005-03-03 10:43:24.000-0600

The internal ones should not be seen in the local source code, so I fully agree. But it would be a good thing to explain that "name" is defined automatically.

By: Brian West (bkw918) 2005-03-17 21:23:48.000-0600

Lobster in my eye... what is the status on this... OUCH!!!


By: Michael Jerris (mikej) 2005-06-26 18:08:21

Suspended due to no activity ;)  ..