For those of you budding Asterisk developers out there, you may find yourself browsing the source code. All over, you’ll find function calls prefixed with “ast”, like “ast_read” or “ast_poll”. But then you’ll come across something that starts with “ao2”, and you might wonder “What does that mean? Why does it have that name?”. This blog post seeks to clear that all up for you.

A History Lesson

Anyone who has programmed in C will be familiar with two of its famous (or infamous) paradigms:

• Memory management is performed manually
• There is no standard container library

Every C project out there develops its own implementation of standard containers like linked lists, hash tables, etc. And most will also develop their own memory management libraries as well. The Asterisk project is no different, and what’s in Asterisk has evolved over the years.

Linked Lists (and ONLY linked lists)

In the early days of Asterisk, if you wanted to place any sort of items in a container, your one and only choice for doing so was a linked list. The linked list implementation in Asterisk is a mixed bag.

On the positive side:

• The implementation is fairly simple. Even if you are not familiar with the API, you likely would understand code that manipulates linked lists.
• It’s easy to declare a linked list of any particular type.
• Linked lists are efficient for scenarios where you are only adding/removing items from the ends of the list.
• Locks are built into lists by default. You can have a linked list with no lock, a mutex, or a read-write lock.
• There are both singly-linked lists and doubly-linked lists.
• Linked lists are well-tested and at this point can be considered “bulletproof”.

On the negative side:

• Searching for a specific object can be slow.
• Sorting a linked list is slow.
• Linked lists are not cache-friendly
• Asterisk’s linked list implementation is intrusive. This means that the objects in the list need to declare that they are part of a list. This can lead to potential ABI issues if the container type needs to change in a future release.
• Aside from insertion, removal, and traversal, there are not many utility functions built into the linked list API
• Linked lists are implemented using macros, meaning that if you are not careful, you might end up passing side-effect-causing statements into the macro.
• Linked lists have no concept of object ownership. They can easily be made to contain freed objects, and since the objects are intrusive, that can completely trash the list.
• The singly-linked and doubly-linked list implementations require a lot of repetition. In addition, the read-write lock lists and the standard lists require repetition as well.
• Some of the macros are not intuitively named. It may not be clear just from the name what the “safe” variant of a list traversal is. In defense of the API, this is documented well in doxygen, but the naming could have been thought through more.
• The definitions of the linked list macros are in the header file. This means that
  • There is not any opacity in the implementation.
  • Changing anything in the implementation requires recompilation of all linked list users.
  • It is more difficult to add in-line debugging to the implementation.

astobj

In 2004, the Asterisk Team added a new API for object management. The API took the shorthand name “astobj”. This API introduced several innovations to Asterisk:

• Reference-counting of objects.
• The potential for using different types of containers to hold objects (more on that later).
• Providing methods of traversal with callbacks.

Despite the innovations introduced, the API is not fondly remembered by current Asterisk developers. Despite its use in a few places, the API never really caught on and so people mostly continued with the old style of memory management and the use of linked lists. The negatives associated with astobj are:

• Just like with linked lists, everything is defined as macros in a header file.
• Just like with linked lists, the API is intrusive.
• The API is just plain wonky
  • ASTOBJ_RDLOCK and ASTOBJ_WRLOCK don’t actually operate on read-write locks. They just operate a mutex.
  • There were some magic builtin variable names, like “iterator” and “next” that you had to know were available to you in traversals.
  • The use of macros for everything led to some bizarre code constructs, like the following:

    ASTOBJ_CONTAINER_TRAVERSE(list, !found, {
        if (!strcmp(iterator, "foo")) {
            found = 1;
        }
    });

  • The destructor for an object was passed to the object unreferencing macro. This meant that you could accidentally call different destructor functions for different parts in the code.
  • There were macros built into the API that likely had no reason being there, such as “marking” all objects in a container.
  • The naming is in places unintuitive. Most API calls have a regular version and a “full” version. The “full” version usually has tons of unused parameters passed in.
• Despite the fact that the API was built with the idea of supporting more than one container type, nothing was ever implemented other than a linked list.
• Remember how I said that the linked list implementation was “bulletproof”? Well, for some reason, rather than using the linked list API directly, astobj decided to build in its own linked list implementation.
• Fine-grained control of container locks was difficult to achieve.

These days, the astobj API is deprecated. The only place it is still used is in another deprecated API (netsock).

astobj2

In 2007, Marta Carbone and Luigi Rizzo contributed the next generation of Asterisk object management. Since this was the successor to astobj, this was called astobj2, or just ao2. This took a new approach to object management in Asterisk. It brought the following innovations:

• Rather than using macros for the entire API, the header contains function declarations, letting the implementation be done in source files elsewhere.
• Rather than starting with a linked list as the default container type, ao2 started with a hash table. The thing about a hash table is that it can end up operating like a linked list if there is only a single hash bucket.
• Rather than writing five different variants of the same function, most functions take a “flags” argument. This argument allows for the function to behave differently. It also makes it much easier to add new behaviors to existing functions.
• Rather than requiring intrusion into the contained objects, ao2 uses some clever manipulation of memory to build in object metadata at allocation time.

ao2 was adopted rapidly by Asterisk developers. I suspect that ao2 was more readily accepted for the following reasons:

• Luigi did an excellent job of mentoring during the project, and Marta did a fantastic job of seeing it through to completion. Luigi’s experience in general with software development plus his experience on the Asterisk project ensured that the result was something people would be happy to use.
• The code went through code review prior to being committed. This meant that interested parties got to put in their feedback and find errors early in the process. Getting more developer eyes on the project also got those developers excited to get to use the new API.
• The code was documented well from the get-go. Linked lists and astobj both contain doxygen now, but when they first were committed, they had no documentation at all. This meant that if you wanted to use those APIs, you essentially had to read the code to learn how they worked rather than reading documentation. For astobj in particular, this could be a daunting task. Further, since the header file contained only function declarations, it was much easier to consume the documentation than if all function definitions were contained there.
• Developers had been wanting a reference counted hash table implementation for quite a while. Channels, SIP dialogs, SIP peers, and other data types in Asterisk naturally fit better in a hash table than a linear data structure. Many places in Asterisk switched overnight to use hash tables and saw performance improvements as a result.

ao2 has been enhanced quite a bit since its inception. The most notable changes are:

• Red-black tree.
• Safely-accessible global objects.
• Weak references.

Examples

Memory Management

astobj2 objects are declared the same as any other C struct. What sets them apart as ao2 objects is the way they are allocated. By using ao2_alloc() to allocate an object, it builds in reference counting metadata. Upon allocating an object, its reference count is one. You can directly manipulate the reference count of an object with the ao2_ref() function. For instance,

• ao2_ref(obj, +1) will increase the reference count of obj by 1.
• ao2_ref(obj, -1) will decrease the reference count of obj by 1.
• ao2_cleanup(obj) is an alias of ao2_ref(obj, -1) but is tolerant of obj being NULL.

When the reference count of an object reaches zero, the destructor for that object is called. In the following example, ao2_alloc() indicates that destroy_foo() is the destructor for foo objects. Therefore, when a foo’s reference count reaches zero, destroy_foo() is called. Notice that in destroy_foo(), the constituent memory within the foo is freed, but the foo itself is not.

struct foo {
 char *bar;
 char *baz;
};

void destroy_foo(void *obj)
{
 struct foo *doomed_foo = obj;

 ast_free(doomed_foo->bar);
 ast_free(doomed_foo->baz);
}

struct foo *allocate_foo(const char *bar, const char *baz)
{
 struct foo *new_foo;
 
 new_foo = ao2_alloc(sizeof(*new_foo), /* Allocation size */
                     destroy_foo); /* Destructor function */
 new_foo->bar = ast_strdup(bar);
 new_foo->baz = ast_strdup(baz);

 return new_foo;
}

Container Allocation

ao2 objects can be stored in a variety of containers. To date, there are three types of containers that can be used

• Hash table
• Red-black tree
• Linked list

ao2 containers are themselves ao2 objects. This means that they are reference-counted and are also destroyed when their reference count reaches zero. When a container is destroyed, it releases its reference on each object in the container.

Here are examples of container allocation for each container type.

struct ao2_container *hash_table;
struct ao2_container *rb_tree;                                                                          
struct ao2_container *linked_list;                                                                      
    
void alloc_containers(void)                                                                             
{
    /* ao2_container_alloc() allocates a hash table.
     * There is also a separate ao2_container_alloc_hash() function you can call that                   
     * has some extra parameters. I'll leave that as an exercise to the reader.                         
     */
    hash_table = ao2_container_alloc(13, /* Number of hash buckets */
        foo_hash, /* Hash function */
        foo_cmp); /* Comparison function */                                                                 
    /* ao2_container_alloc_rbtree() allocates a red-black tree. */
    rb_tree = ao2_container_alloc_rbtree(AO2_ALLOC_OPT_LOCK_RWLOCK, /* AO2 Object flags. Use a read-write lock. */
        AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT, /* AO2 Container flags. Don't allow duplicate keys in this container */
        foo_sort, /* Sorting function (required for a red-black tree) */
        foo_cmp); /* Comparison function */                                                            
    linked_list = ao2_container_alloc_list(0, /* AO2 object flags. 0 means to use the default behavior */
        AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN, /* AO2 container flags. New items should be added to the front of the list */
        NULL, /* Sorting function. NULL means the list will not be sorted */
        foo_cmp); /* Comparison function */                                                           
}   

Below is the definition of the foo_hash function. I’ll leave the definition of foo_sort and foo_cmp as exercises for the reader.  Other ao2 callback templates are available on the asterisk wiki.

int foo_hash(const void *obj, const int flags)
{
    const struct foo *object;
    const char *key;  
    
    /* This is a common template for hash functions. */
    switch (flags & OBJ_SEARCH_MASK) {       
    case OBJ_SEARCH_KEY:
        /* A key was passed to the hash function. */
        key = obj;
        break;
    case OBJ_SEARCH_OBJECT:   
        /* A foo was passed to the hash function. */
        object = obj;                    
        key = object->bar;
        break; 
    default:
        ast_assert(0);         
        return 0;                                
    }   
    /* ast_str_hash() is a handy utility for calculating the hash of a string */
    return ast_str_hash(key);    
}

Adding items to containers

The ao2_link() function is used to add an ao2 object into a container. When an object is linked into a container, its reference count is increased by one, thus giving the container shared ownership of the object.

void add_item(struct foo *to_add)        
{                                                                                                       
    ao2_link(hash_table, to_add);
    ao2_link(rb_tree, to_add);
    ao2_link(linked_list, to_add);
}

Notice that the same object was added to three different containers in the above example. Since the same object was linked into three containers, it means that the object’s reference count was increased by three.

Finding an item in a container

The ao2_find() function is used to find a specific object in a container.

struct foo *find_item_by_key(const char *bar)
{
    /* OBJ_SEARCH_KEY indicates we're passing in a key rather than an object itself */
    return ao2_find(hash_table, bar, OBJ_SEARCH_KEY);
}

ao2_find() uses the comparison function specified when the container was allocated in order to find a match.

Removing an item from a container

The ao2_unlink() function is used to remove an object from a container. When an object is removed from a container, the container’s reference of the object is removed, thus decreasing the reference count of the object by one.

void remove_item(struct foo *to_remove);
{
    ao2_unlink(hash_table, to_remove);
    ao2_unlink(rb_tree, to_remove);
    ao2_unlink(linked_list, to_remove);
}

Container callbacks

The ao2_callback() function is one of the most powerful tools in the ao2 toolbox. The premise is simple: it iterates over the container and calls a given callback function on each item. The callback’s return value indicates whether the container should continue calling the callback on additional objects. This means that you could, for instance, update a field on every item in the container (e.g. updating a timestamp). You can also use ao2_callback() as a way of finding an object using a custom matching method.

int find_by_baz(void *obj, void *arg, int flags)
{
    struct foo *candidate = obj; /* This is the object in the container */
    const char *baz = arg;

    if (!strcmp(baz, candidate->baz)) {
        return CMP_MATCH;
    } 
    return 0;
}

struct foo *find_item_by_baz(const char *baz)
{
    return ao2_callback(hash_table, /* The container to traverse */
        0, /* No special flags. */
        find_by_baz, /* Call find_by_baz on each object */
        baz, /* Pass baz as an argument to the callback each time */
}

In the previous example, find_by_baz() was called on each object in the container. Returning CMP_MATCH indicates that the traversal has found a match for ao2_callback() to return and the traversal should stop. Returning 0 indicates that the traversal should continue.

Here’s another example of ao2_callback():

int remove_items(void *obj, void *arg, int flags)
{   
    struct foo *candidate = obj;
    char *bad_letter = arg;
    
    if (*candidate->bar == *bad_letter) {
        return CMP_MATCH;
    }
    
    return 0;            
}

void callback_demo(const char bad_letter)
{       
    ao2_callback(hash_table, OBJ_MULTIPLE | OBJ_NODATA | OBJ_UNLINK, remove_items, &bad_letter);
}

In this example, we’re removing all objects whose bar field starts with the bad_letter. OBJ_MULTIPLE tells the traversal not to stop after the first return of CMP_MATCH. OBJ_NODATA says not to actually return any objects. OBJ_UNLINK removes matches from the container.

Final Thoughts

The previous examples scratched the surface of ao2 usage in Asterisk. There’s a lot more for you to explore in the API and it could be just what you need for whatever Asterisk code you’re writing.

If you are looking into making changes to ao2, feel free; we’d love to see the changes! We don’t currently have a wishlist of new features we’d like to see. I think if anything, we might want to see some of the fat trimmed in places. Since ao2 is so widely used, if we could get some good optimizations added, it would result in performance improvements all over the code.