diff options
author | Richard Mudgett <rmudgett@digium.com> | 2012-09-12 21:02:29 +0000 |
---|---|---|
committer | Richard Mudgett <rmudgett@digium.com> | 2012-09-12 21:02:29 +0000 |
commit | fb1d9a90a4e67c832486f35c54dab5b99ef62941 (patch) | |
tree | 667bde49b2a70ea07f608e7ed24220284f842d7f | |
parent | 189249cc73d66948957884494ed23da738ab4cd1 (diff) |
Enhance astobj2 to support other types of containers.
The new API allows for sorted containers, insertion options, duplicate
handling options, and traversal order options.
* Adds the ability for containers to be sorted when they are created.
* Adds container creation options to handle duplicates when they are
inserted.
* Adds container creation option to insert objects at the beginning or end
of the container traversal order.
* Adds OBJ_PARTIAL_KEY to allow searching with a partial key. The partial
key works similarly to the OBJ_KEY flag. (The real search speed
improvement with this flag will come when red-black trees are added.)
* Adds container traversal and iteration order options: Ascending and
Descending.
* Adds an AST_DEVMODE compile feature to check the stats and integrity of
registered containers using the CLI "astobj2 container stats <name>" and
"astobj2 container check <name>". The channels container is normally
registered since it is one of the most important containers in the system.
* Adds ao2_iterator_restart() to allow iteration to be restarted from the
beginning.
* Changes the generic container object to have a v_method table pointer to
support other types of containers.
* Changes the container nodes holding objects to be ref counted.
The ref counted nodes and v_method table pointer changes pave the way to
allow other types of containers.
* Includes a large astobj2 unit test enhancement that tests the new
features.
(closes issue ASTERISK-19969)
Reported by: rmudgett
Review: https://reviewboard.asterisk.org/r/2078/
git-svn-id: https://origsvn.digium.com/svn/asterisk/trunk@372997 65c4cc65-6c06-0410-ace0-fbb531ad65f3
-rw-r--r-- | include/asterisk/astobj2.h | 522 | ||||
-rw-r--r-- | main/astobj2.c | 2444 | ||||
-rw-r--r-- | main/channel.c | 3 | ||||
-rw-r--r-- | tests/test_astobj2.c | 1565 |
4 files changed, 3871 insertions, 663 deletions
diff --git a/include/asterisk/astobj2.h b/include/asterisk/astobj2.h index d7d9d79d2..3b93a029e 100644 --- a/include/asterisk/astobj2.h +++ b/include/asterisk/astobj2.h @@ -728,8 +728,10 @@ Operations on container include: OBJ_MULTIPLE - don't stop at first match OBJ_POINTER - if set, 'arg' is an object pointer, and a hash table search will be done. If not, a traversal is done. - OBJ_KEY - if set, 'arg', is a hashable item that is not an object. + OBJ_KEY - if set, 'arg', is a search key item that is not an object. Similar to OBJ_POINTER and mutually exclusive. + OBJ_PARTIAL_KEY - if set, 'arg', is a partial search key item that is not an object. + Similar to OBJ_KEY and mutually exclusive. - \b ao2_callback(c, flags, fn, arg) apply fn(obj, arg) to all objects in the container. @@ -743,8 +745,10 @@ Operations on container include: OBJ_POINTER - if set, 'arg' is an object pointer, and a hash table search will be done. If not, a traversal is done through all the hash table 'buckets'.. - OBJ_KEY - if set, 'arg', is a hashable item that is not an object. + OBJ_KEY - if set, 'arg', is a search key item that is not an object. Similar to OBJ_POINTER and mutually exclusive. + OBJ_PARTIAL_KEY - if set, 'arg', is a partial search key item that is not an object. + Similar to OBJ_KEY and mutually exclusive. - fn is a func that returns int, and takes 3 args: (void *obj, void *arg, int flags); obj is an object @@ -801,32 +805,6 @@ to define callback and hash functions and their arguments. */ /*! \brief - * Type of a generic callback function - * \param obj pointer to the (user-defined part) of an object. - * \param arg callback argument from ao2_callback() - * \param flags flags from ao2_callback() - * - * The return values are a combination of enum _cb_results. - * Callback functions are used to search or manipulate objects in a container. - */ -typedef int (ao2_callback_fn)(void *obj, void *arg, int flags); - -/*! \brief - * Type of a generic callback function - * \param obj pointer to the (user-defined part) of an object. - * \param arg callback argument from ao2_callback() - * \param data arbitrary data from ao2_callback() - * \param flags flags from ao2_callback() - * - * The return values are a combination of enum _cb_results. - * Callback functions are used to search or manipulate objects in a container. - */ -typedef int (ao2_callback_data_fn)(void *obj, void *arg, void *data, int flags); - -/*! \brief A common ao2_callback is one that matches by address. */ -int ao2_match_by_addr(void *obj, void *arg, int flags); - -/*! \brief * A callback function will return a combination of CMP_MATCH and CMP_STOP. * The latter will terminate the search in a container. */ @@ -835,8 +813,13 @@ enum _cb_results { CMP_STOP = 0x2, /*!< stop the search now */ }; -/*! \brief - * Flags passed to ao2_callback() and ao2_hash_fn() to modify its behaviour. +/*! + * \brief Flags passed to ao2_callback_fn(), ao2_hash_fn(), and ao2_sort_fn() to modify behaviour. + * + * \todo XXX OBJ_POINTER, OBJ_KEY, and OBJ_PARTIAL_KEY need to + * be put into a bit field like OBJ_ORDER_MASK since they are + * mutually exclusive. This change unfortunately is not + * backwards compatible. */ enum search_flags { /*! @@ -855,21 +838,42 @@ enum search_flags { */ OBJ_MULTIPLE = (1 << 2), /*! - * The given obj is an object of the same type as the one being - * searched for, so use the object's hash function for optimized - * searching. + * \brief The arg parameter is an object of the same type. + * + * \details + * The arg parameter is an object of the same type as the one + * being searched for, so use the object's ao2_hash_fn and/or + * ao2_sort_fn functions for optimized searching. * - * The matching function is unaffected (i.e. The cb_fn argument - * to ao2_callback). + * \note The supplied ao2_callback_fn is called after the + * container nodes have been filtered by the ao2_hash_fn and/or + * ao2_sort_fn functions. + * + * \note OBJ_POINTER, OBJ_KEY, and OBJ_PARTIAL_KEY are mutually + * exclusive. */ OBJ_POINTER = (1 << 3), /*! - * \brief Continue if a match is not found in the hashed out bucket + * \brief Continue if a match is not found. + * + * \details + * This flag forces a whole container search. The OBJ_POINTER, + * OBJ_KEY, and OBJ_PARTIAL_KEY flags just specify where to + * start the search in the container. If the search is not + * stopped early then the search _continues_ until the search + * wraps around to the starting point. * - * This flag is to be used in combination with OBJ_POINTER. This tells - * the ao2_callback() core to keep searching through the rest of the - * buckets if a match is not found in the starting bucket defined by - * the hash value on the argument. + * Normal searches start where the search key specifies to start + * and end when the search key indicates that the object is not + * in the container. + * + * For hash containers, this tells the ao2_callback() core to + * keep searching through the rest of the buckets if a match is + * not found in the starting bucket defined by the hash value on + * the argument. + * + * \note The supplied ao2_callback_fn is called for every node + * in the container from the starting point. */ OBJ_CONTINUE = (1 << 4), /*! @@ -887,26 +891,169 @@ enum search_flags { */ OBJ_NOLOCK = (1 << 5), /*! - * \brief The data is hashable, but is not an object. + * \brief The arg parameter is a search key, but is not an object. * * \details * This can be used when you want to be able to pass custom data - * to the container's stored ao2_hash_fn and ao2_find - * ao2_callback_fn functions that is not a full object, but - * perhaps just a string. + * to the container's stored ao2_hash_fn, ao2_sort_fn, and + * ao2_find ao2_callback_fn functions that is not a full object, + * but perhaps just a string. + * + * \note The supplied ao2_callback_fn is called after the + * container nodes have been filtered by the ao2_hash_fn and/or + * ao2_sort_fn functions. * - * \note OBJ_KEY and OBJ_POINTER are mutually exclusive options. + * \note OBJ_POINTER, OBJ_KEY, and OBJ_PARTIAL_KEY are mutually + * exclusive. */ OBJ_KEY = (1 << 6), + /*! + * \brief The arg parameter is a partial search key similar to OBJ_KEY. + * + * \details + * The partial key can be used by the ao2_sort_fn to guide the + * search to find a contiguous subset of a sorted container. + * For example, a sorted container holds: "A", "B", "Bert", + * "Beth", "Earnie". Doing a partial key search with "B" will + * find the sorted subset of all held objects starting with "B". + * + * \note The supplied ao2_callback_fn is called after the + * container nodes have been filtered by the ao2_sort_fn + * function. + * + * \note OBJ_POINTER, OBJ_KEY, and OBJ_PARTIAL_KEY are mutually + * exclusive. + */ + OBJ_PARTIAL_KEY = (1 << 7), + + /*! \brief Traverse order option field mask. */ + OBJ_ORDER_MASK = (0x03 << 8), + /*! \brief Traverse in ascending order (First to last container object) */ + OBJ_ORDER_ASCENDING = (0 << 8), + /*! \brief Traverse in descending order (Last to first container object) */ + OBJ_ORDER_DESCENDING = (1 << 8), +}; + +/*! + * \brief Options available when allocating an ao2 container object. + * + * \note Each option is open to some interpretation by the + * container type as long as it makes sense with the option + * name. + */ +enum ao2_container_opts { + /*! + * \brief Insert objects at the beginning of the container. + * (Otherwise it is the opposite; insert at the end.) + * + * \note If an ao2_sort_fn is provided, the object is inserted + * before any objects with duplicate keys. + * + * \note Hash containers insert the object in the computed hash + * bucket in the indicated manner. + */ + AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN = (1 << 0), + + /*! + * \brief The ao2 container objects with duplicate keys option field mask. + */ + AO2_CONTAINER_ALLOC_OPT_DUPS_MASK = (3 << 1), + /*! + * \brief Allow objects with duplicate keys in container. + */ + AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW = (0 << 1), + /*! + * \brief Reject objects with duplicate keys in container. + * + * \note The container must be sorted. i.e. have an + * ao2_sort_fn. + */ + AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT = (1 << 1), + /*! + * \brief Reject duplicate objects in container. + * + * \details Don't link the same object into the container twice. + * However, you can link a different object with the same key. + * + * \note The container must be sorted. i.e. have an + * ao2_sort_fn. + * + * \note It is assumed that the objects are located where the + * search key says they should be located. + */ + AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT = (2 << 1), + /*! + * \brief Replace objects with duplicate keys in container. + * + * \details The existing duplicate object is removed and the new + * object takes the old object's place. + * + * \note The container must be sorted. i.e. have an + * ao2_sort_fn. + */ + AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE = (3 << 1), }; /*! + * \brief Type of a generic callback function + * \param obj pointer to the (user-defined part) of an object. + * \param arg callback argument from ao2_callback() + * \param flags flags from ao2_callback() + * OBJ_POINTER - if set, 'arg', is an object. + * OBJ_KEY - if set, 'arg', is a search key item that is not an object. + * OBJ_PARTIAL_KEY - if set, 'arg', is a partial search key item that is not an object. + * + * The return values are a combination of enum _cb_results. + * Callback functions are used to search or manipulate objects in a container. + */ +typedef int (ao2_callback_fn)(void *obj, void *arg, int flags); + +/*! \brief A common ao2_callback is one that matches by address. */ +int ao2_match_by_addr(void *obj, void *arg, int flags); + +/*! + * \brief Type of a generic callback function + * \param obj pointer to the (user-defined part) of an object. + * \param arg callback argument from ao2_callback() + * \param data arbitrary data from ao2_callback() + * \param flags flags from ao2_callback() + * OBJ_POINTER - if set, 'arg', is an object. + * OBJ_KEY - if set, 'arg', is a search key item that is not an object. + * OBJ_PARTIAL_KEY - if set, 'arg', is a partial search key item that is not an object. + * + * The return values are a combination of enum _cb_results. + * Callback functions are used to search or manipulate objects in a container. + */ +typedef int (ao2_callback_data_fn)(void *obj, void *arg, void *data, int flags); + +/*! * Type of a generic function to generate a hash value from an object. - * flags is ignored at the moment. Eventually, it will include the - * value of OBJ_POINTER passed to ao2_callback(). + * + * \param obj pointer to the (user-defined part) of an object. + * \param flags flags from ao2_callback() + * OBJ_POINTER - if set, 'obj', is an object. + * OBJ_KEY - if set, 'obj', is a search key item that is not an object. + * + * \return Computed hash value. */ typedef int (ao2_hash_fn)(const void *obj, int flags); +/*! + * \brief Type of generic container sort function. + * + * \param obj_left pointer to the (user-defined part) of an object. + * \param obj_right pointer to the (user-defined part) of an object. + * \param flags flags from ao2_callback() + * OBJ_POINTER - if set, 'obj_right', is an object. + * OBJ_KEY - if set, 'obj_right', is a search key item that is not an object. + * OBJ_PARTIAL_KEY - if set, 'obj_right', is a partial search key item that is not an object. + * + * \retval <0 if obj_left < obj_right + * \retval =0 if obj_left == obj_right + * \retval >0 if obj_left > obj_right + */ +typedef int (ao2_sort_fn)(const void *obj_left, const void *obj_right, int flags); + /*! \name Object Containers * Here start declarations of containers. */ @@ -929,50 +1076,112 @@ struct ao2_container; * \return A pointer to a struct container. * * \note Destructor is set implicitly. + * \note This is legacy container creation that is mapped to the new method. */ -#if defined(REF_DEBUG) - #define ao2_t_container_alloc_options(options, n_buckets, hash_fn, cmp_fn, tag) \ - __ao2_container_alloc_debug((options), (n_buckets), (hash_fn), (cmp_fn), (tag), __FILE__, __LINE__, __PRETTY_FUNCTION__, 1) + ao2_t_container_alloc_hash((options), 0, (n_buckets), (hash_fn), NULL, (cmp_fn), (tag)) #define ao2_container_alloc_options(options, n_buckets, hash_fn, cmp_fn) \ - __ao2_container_alloc_debug((options), (n_buckets), (hash_fn), (cmp_fn), "", __FILE__, __LINE__, __PRETTY_FUNCTION__, 1) + ao2_container_alloc_hash((options), 0, (n_buckets), (hash_fn), NULL, (cmp_fn)) #define ao2_t_container_alloc(n_buckets, hash_fn, cmp_fn, tag) \ - __ao2_container_alloc_debug(AO2_ALLOC_OPT_LOCK_MUTEX, (n_buckets), (hash_fn), (cmp_fn), (tag), __FILE__, __LINE__, __PRETTY_FUNCTION__, 1) + ao2_t_container_alloc_options(AO2_ALLOC_OPT_LOCK_MUTEX, (n_buckets), (hash_fn), (cmp_fn), (tag)) #define ao2_container_alloc(n_buckets, hash_fn, cmp_fn) \ - __ao2_container_alloc_debug(AO2_ALLOC_OPT_LOCK_MUTEX, (n_buckets), (hash_fn), (cmp_fn), "", __FILE__, __LINE__, __PRETTY_FUNCTION__, 1) + ao2_container_alloc_options(AO2_ALLOC_OPT_LOCK_MUTEX, (n_buckets), (hash_fn), (cmp_fn)) -#elif defined(__AST_DEBUG_MALLOC) +/*! + * \brief Allocate and initialize a hash container with the desired number of buckets. + * + * \details + * We allocate space for a struct astobj_container, struct container + * and the buckets[] array. + * + * \param ao2_options Container ao2 object options (See enum ao2_alloc_opts) + * \param container_options Container behaviour options (See enum ao2_container_opts) + * \param n_buckets Number of buckets for hash + * \param hash_fn Pointer to a function computing a hash value. (NULL if everyting goes in first bucket.) + * \param sort_fn Pointer to a sort function. (NULL to not sort the buckets.) + * \param cmp_fn Pointer to a compare function used by ao2_find. (NULL to match everything) + * \param tag used for debugging. + * + * \return A pointer to a struct container. + * + * \note Destructor is set implicitly. + */ -#define ao2_t_container_alloc_options(options, n_buckets, hash_fn, cmp_fn, tag) \ - __ao2_container_alloc_debug((options), (n_buckets), (hash_fn), (cmp_fn), (tag), __FILE__, __LINE__, __PRETTY_FUNCTION__, 0) -#define ao2_container_alloc_options(options, n_buckets, hash_fn, cmp_fn) \ - __ao2_container_alloc_debug((options), (n_buckets), (hash_fn), (cmp_fn), "", __FILE__, __LINE__, __PRETTY_FUNCTION__, 0) +#if defined(REF_DEBUG) -#define ao2_t_container_alloc(n_buckets, hash_fn, cmp_fn, tag) \ - __ao2_container_alloc_debug(AO2_ALLOC_OPT_LOCK_MUTEX, (n_buckets), (hash_fn), (cmp_fn), (tag), __FILE__, __LINE__, __PRETTY_FUNCTION__, 0) -#define ao2_container_alloc(n_buckets, hash_fn, cmp_fn) \ - __ao2_container_alloc_debug(AO2_ALLOC_OPT_LOCK_MUTEX, (n_buckets), (hash_fn), (cmp_fn), "", __FILE__, __LINE__, __PRETTY_FUNCTION__, 0) +#define ao2_t_container_alloc_hash(ao2_options, container_options, n_buckets, hash_fn, sort_fn, cmp_fn, tag) \ + __ao2_container_alloc_hash_debug((ao2_options), (container_options), (n_buckets), (hash_fn), (sort_fn), (cmp_fn), (tag), __FILE__, __LINE__, __PRETTY_FUNCTION__, 1) +#define ao2_container_alloc_hash(ao2_options, container_options, n_buckets, hash_fn, sort_fn, cmp_fn) \ + __ao2_container_alloc_hash_debug((ao2_options), (container_options), (n_buckets), (hash_fn), (sort_fn), (cmp_fn), "", __FILE__, __LINE__, __PRETTY_FUNCTION__, 1) + +#elif defined(__AST_DEBUG_MALLOC) + +#define ao2_t_container_alloc_hash(ao2_options, container_options, n_buckets, hash_fn, sort_fn, cmp_fn, tag) \ + __ao2_container_alloc_hash_debug((ao2_options), (container_options), (n_buckets), (hash_fn), (sort_fn), (cmp_fn), (tag), __FILE__, __LINE__, __PRETTY_FUNCTION__, 0) +#define ao2_container_alloc_hash(ao2_options, container_options, n_buckets, hash_fn, sort_fn, cmp_fn) \ + __ao2_container_alloc_hash_debug((ao2_options), (container_options), (n_buckets), (hash_fn), (sort_fn), (cmp_fn), "", __FILE__, __LINE__, __PRETTY_FUNCTION__, 0) #else -#define ao2_t_container_alloc_options(options, n_buckets, hash_fn, cmp_fn, tag) \ - __ao2_container_alloc((options), (n_buckets), (hash_fn), (cmp_fn)) -#define ao2_container_alloc_options(options, n_buckets, hash_fn, cmp_fn) \ - __ao2_container_alloc((options), (n_buckets), (hash_fn), (cmp_fn)) +#define ao2_t_container_alloc_hash(ao2_options, container_options, n_buckets, hash_fn, sort_fn, cmp_fn, tag) \ + __ao2_container_alloc_hash((ao2_options), (container_options), (n_buckets), (hash_fn), (sort_fn), (cmp_fn)) +#define ao2_container_alloc_hash(ao2_options, container_options, n_buckets, hash_fn, sort_fn, cmp_fn) \ + __ao2_container_alloc_hash((ao2_options), (container_options), (n_buckets), (hash_fn), (sort_fn), (cmp_fn)) -#define ao2_t_container_alloc(n_buckets, hash_fn, cmp_fn, tag) \ - __ao2_container_alloc(AO2_ALLOC_OPT_LOCK_MUTEX, (n_buckets), (hash_fn), (cmp_fn)) -#define ao2_container_alloc(n_buckets, hash_fn, cmp_fn) \ - __ao2_container_alloc(AO2_ALLOC_OPT_LOCK_MUTEX, (n_buckets), (hash_fn), (cmp_fn)) +#endif + +struct ao2_container *__ao2_container_alloc_hash(unsigned int ao2_options, + unsigned int container_options, unsigned int n_buckets, ao2_hash_fn *hash_fn, + ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn); +struct ao2_container *__ao2_container_alloc_hash_debug(unsigned int ao2_options, + unsigned int container_options, unsigned int n_buckets, ao2_hash_fn *hash_fn, + ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn, + const char *tag, const char *file, int line, const char *func, int ref_debug); + +/*! + * \brief Allocate and initialize a list container. + * + * \param ao2_options Container ao2 object options (See enum ao2_alloc_opts) + * \param container_options Container behaviour options (See enum ao2_container_opts) + * \param sort_fn Pointer to a sort function. (NULL if list not sorted.) + * \param cmp_fn Pointer to a compare function used by ao2_find. (NULL to match everything) + * \param tag used for debugging. + * + * \return A pointer to a struct container. + * + * \note Destructor is set implicitly. + * \note Implemented as a degenerate hash table. + */ + +#if defined(REF_DEBUG) + +#define ao2_t_container_alloc_list(ao2_options, container_options, sort_fn, cmp_fn, tag) \ + __ao2_container_alloc_list_debug((ao2_options), (container_options), (sort_fn), (cmp_fn), (tag), __FILE__, __LINE__, __PRETTY_FUNCTION__, 1) +#define ao2_container_alloc_list(ao2_options, container_options, sort_fn, cmp_fn) \ + __ao2_container_alloc_list_debug((ao2_options), (container_options), (sort_fn), (cmp_fn), "", __FILE__, __LINE__, __PRETTY_FUNCTION__, 1) + +#elif defined(__AST_DEBUG_MALLOC) + +#define ao2_t_container_alloc_list(ao2_options, container_options, sort_fn, cmp_fn, tag) \ + __ao2_container_alloc_list_debug((ao2_options), (container_options), (sort_fn), (cmp_fn), (tag), __FILE__, __LINE__, __PRETTY_FUNCTION__, 0) +#define ao2_container_alloc_list(ao2_options, container_options, sort_fn, cmp_fn) \ + __ao2_container_alloc_list_debug((ao2_options), (container_options), (sort_fn), (cmp_fn), "", __FILE__, __LINE__, __PRETTY_FUNCTION__, 0) + +#else + +#define ao2_t_container_alloc_list(ao2_options, container_options, sort_fn, cmp_fn, tag) \ + __ao2_container_alloc_list((ao2_options), (container_options), (sort_fn), (cmp_fn)) +#define ao2_container_alloc_list(ao2_options, container_options, sort_fn, cmp_fn) \ + __ao2_container_alloc_list((ao2_options), (container_options), (sort_fn), (cmp_fn)) #endif -struct ao2_container *__ao2_container_alloc(unsigned int options, - unsigned int n_buckets, ao2_hash_fn *hash_fn, ao2_callback_fn *cmp_fn); -struct ao2_container *__ao2_container_alloc_debug(unsigned int options, - unsigned int n_buckets, ao2_hash_fn *hash_fn, ao2_callback_fn *cmp_fn, +struct ao2_container *__ao2_container_alloc_list(unsigned int ao2_options, + unsigned int container_options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn); +struct ao2_container *__ao2_container_alloc_list_debug(unsigned int ao2_options, + unsigned int container_options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn, const char *tag, const char *file, int line, const char *func, int ref_debug); /*! \brief @@ -1032,6 +1241,40 @@ struct ao2_container *__ao2_container_clone_debug(struct ao2_container *orig, en #endif +/*! + * \brief Perform an integrity check on the specified container. + * \since 12.0.0 + * + * \param self Container to check integrity. + * \param flags OBJ_NOLOCK if a lock is already held on the container. + * + * \retval 0 on success. + * \retval -1 on error. + */ +int ao2_container_check(struct ao2_container *self, enum search_flags flags); + +/*! + * \brief Register a container for CLI stats and integrity check. + * \since 12.0.0 + * + * \param name Name to register the container under. + * \param self Container to register. + * + * \retval 0 on success. + * \retval -1 on error. + */ +int ao2_container_register(const char *name, struct ao2_container *self); + +/*! + * \brief Unregister a container for CLI stats and integrity check. + * \since 12.0.0 + * + * \param name Name the container is registered under. + * + * \return Nothing + */ +void ao2_container_unregister(const char *name); + /*@} */ /*! \name Object Management @@ -1049,8 +1292,8 @@ struct ao2_container *__ao2_container_clone_debug(struct ao2_container *orig, en * \param obj The object to be added. * \param tag used for debugging. * - * \retval NULL on errors. - * \retval !NULL on success. + * \retval 0 on errors. + * \retval 1 on success. * * This function inserts an object in a container according its key. * @@ -1095,8 +1338,8 @@ struct ao2_container *__ao2_container_clone_debug(struct ao2_container *orig, en #endif -void *__ao2_link_debug(struct ao2_container *c, void *obj_new, int flags, const char *tag, const char *file, int line, const char *func); -void *__ao2_link(struct ao2_container *c, void *obj_new, int flags); +int __ao2_link_debug(struct ao2_container *c, void *obj_new, int flags, const char *tag, const char *file, int line, const char *func); +int __ao2_link(struct ao2_container *c, void *obj_new, int flags); /*! * \brief Remove an object from a container @@ -1230,7 +1473,8 @@ void *__ao2_unlink(struct ao2_container *c, void *obj, int flags); * OBJ_MULTIPLE return multiple matches * Default is no. * OBJ_POINTER the pointer is an object pointer - * OBJ_KEY the pointer is to a hashable key + * OBJ_KEY the pointer is to a search key + * OBJ_PARTIAL_KEY the pointer is to a partial search key * * \note When the returned object is no longer in use, ao2_ref() should * be used to free the additional reference possibly created by this function. @@ -1327,32 +1571,24 @@ void *__ao2_find(struct ao2_container *c, const void *arg, enum search_flags fla * ao2_iterator to keep track of the current position. * * Because the navigation is typically done without holding the - * lock on the container across the loop, objects can be inserted or deleted - * or moved while we work. As a consequence, there is no guarantee that - * we manage to touch all the elements in the container, and it is possible - * that we touch the same object multiple times. - * - * However, within the current hash table container, the following is true: - * - It is not possible to miss an object in the container while iterating - * unless it gets added after the iteration begins and is added to a bucket - * that is before the one the current object is in. In this case, even if - * you locked the container around the entire iteration loop, you still would - * not see this object, because it would still be waiting on the container - * lock so that it can be added. - * - It would be extremely rare to see an object twice. The only way this can - * happen is if an object got unlinked from the container and added again - * during the same iteration. Furthermore, when the object gets added back, - * it has to be in the current or later bucket for it to be seen again. - * - * An iterator must be first initialized with ao2_iterator_init(), - * then we can use o = ao2_iterator_next() to move from one - * element to the next. Remember that the object returned by - * ao2_iterator_next() has its refcount incremented, - * and the reference must be explicitly released when done with it. - * - * In addition, ao2_iterator_init() will hold a reference to the container - * being iterated, which will be freed when ao2_iterator_destroy() is called - * to free up the resources used by the iterator (if any). + * lock on the container across the loop, objects can be + * inserted or deleted or moved while we work. As a + * consequence, there is no guarantee that we manage to touch + * all the elements in the container, and it is possible that we + * touch the same object multiple times. + * + * An iterator must be first initialized with + * ao2_iterator_init(), then we can use o = ao2_iterator_next() + * to move from one element to the next. Remember that the + * object returned by ao2_iterator_next() has its refcount + * incremented, and the reference must be explicitly released + * when done with it. + * + * In addition, ao2_iterator_init() will hold a reference to the + * container being iterated and the last container node found. + * Thes objects will be unreffed when ao2_iterator_destroy() is + * called to free up the resources used by the iterator (if + * any). * * Example: * @@ -1369,14 +1605,20 @@ void *__ao2_find(struct ao2_container *c, const void *arg, enum search_flags fla * ao2_ref(o, -1); * } * + * ao2_iterator_restart(&i); + * while ((o = ao2_iterator_next(&i))) { + * ... do something on o ... + * ao2_ref(o, -1); + * } + * * ao2_iterator_destroy(&i); * * \endcode * */ -/*! \brief - * The astobj2 iterator +/*! + * \brief The astobj2 iterator * * \note You are not supposed to know the internals of an iterator! * We would like the iterator to be opaque, unfortunately @@ -1386,34 +1628,19 @@ void *__ao2_find(struct ao2_container *c, const void *arg, enum search_flags fla * The iterator has a pointer to the container, and a flags * field specifying various things e.g. whether the container * should be locked or not while navigating on it. - * The iterator "points" to the current object, which is identified - * by three values: - * - * - a bucket number; - * - the object_id, which is also the container version number - * when the object was inserted. This identifies the object - * uniquely, however reaching the desired object requires - * scanning a list. - * - a pointer, and a container version when we saved the pointer. - * If the container has not changed its version number, then we - * can safely follow the pointer to reach the object in constant time. + * The iterator "points" to the current container node. * * Details are in the implementation of ao2_iterator_next() - * A freshly-initialized iterator has bucket=0, version=0. */ struct ao2_iterator { - /*! the container */ + /*! The container (Has a reference) */ struct ao2_container *c; - /*! operation flags */ + /*! Last container node (Has a reference) */ + void *last_node; + /*! Nonzero if the iteration has completed. */ + int complete; + /*! operation flags (enum ao2_iterator_flags) */ int flags; - /*! current bucket */ - int bucket; - /*! container version */ - unsigned int c_version; - /*! pointer to the current object */ - void *obj; - /*! container version when the object was created */ - unsigned int version; }; /*! Flags that can be passed to ao2_iterator_init() to modify the behavior @@ -1431,7 +1658,10 @@ enum ao2_iterator_flags { * to the original locked state. * * \note Only use this flag if the ao2_container is manually - * locked already. + * locked already. You should hold the lock until after + * ao2_iterator_destroy(). If you must release the lock then + * you must at least hold the lock whenever you call an + * ao2_iterator_xxx function with this iterator. */ AO2_ITERATOR_DONTLOCK = (1 << 0), /*! @@ -1445,13 +1675,25 @@ enum ao2_iterator_flags { * from the container. */ AO2_ITERATOR_UNLINK = (1 << 2), + /*! + * Iterate in descending order (Last to first container object) + * (Otherwise ascending order) + * + * \note Other traversal orders such as pre-order and post-order + * do not make sense because they require the container + * structure to be static during the traversal. Iterators just + * about guarantee that is not going to happen because the + * container is allowed to change by other threads during the + * iteration. + */ + AO2_ITERATOR_DESCENDING = (1 << 3), }; /*! * \brief Create an iterator for a container * * \param c the container - * \param flags one or more flags from ao2_iterator_flags + * \param flags one or more flags from ao2_iterator_flags. * * \retval the constructed iterator * @@ -1461,7 +1703,6 @@ enum ao2_iterator_flags { * allocated on the stack or on the heap. * * This function will take a reference on the container being iterated. - * */ struct ao2_iterator ao2_iterator_init(struct ao2_container *c, int flags); @@ -1474,13 +1715,13 @@ struct ao2_iterator ao2_iterator_init(struct ao2_container *c, int flags); * * This function will release the container reference held by the iterator * and any other resources it may be holding. - * */ #if defined(TEST_FRAMEWORK) void ao2_iterator_destroy(struct ao2_iterator *iter) __attribute__((noinline)); #else void ao2_iterator_destroy(struct ao2_iterator *iter); -#endif +#endif /* defined(TEST_FRAMEWORK) */ + #ifdef REF_DEBUG #define ao2_t_iterator_next(iter, tag) __ao2_iterator_next_debug((iter), (tag), __FILE__, __LINE__, __PRETTY_FUNCTION__) @@ -1496,6 +1737,19 @@ void ao2_iterator_destroy(struct ao2_iterator *iter); void *__ao2_iterator_next_debug(struct ao2_iterator *iter, const char *tag, const char *file, int line, const char *func); void *__ao2_iterator_next(struct ao2_iterator *iter); +/*! + * \brief Restart an iteration. + * + * \param iter the iterator to restart + * + * \note A restart is not going to have any effect if the + * iterator was created with the AO2_ITERATOR_UNLINK flag. Any + * previous objects returned were removed from the container. + * + * \retval none + */ +void ao2_iterator_restart(struct ao2_iterator *iter); + /* extra functions */ void ao2_bt(void); /* backtrace */ diff --git a/main/astobj2.c b/main/astobj2.c index 176ea5aea..9b5f8420e 100644 --- a/main/astobj2.c +++ b/main/astobj2.c @@ -14,8 +14,11 @@ * at the top of the source tree. */ -/* - * Function implementing astobj2 objects. +/*! \file + * + * \brief Functions implementing astobj2 objects. + * + * \author Richard Mudgett <rmudgett@digium.com> */ /*** MODULEINFO @@ -28,7 +31,7 @@ ASTERISK_FILE_VERSION(__FILE__, "$Revision$") #include "asterisk/_private.h" #include "asterisk/astobj2.h" -#include "asterisk/linkedlists.h" +#include "asterisk/dlinkedlists.h" #include "asterisk/utils.h" #include "asterisk/cli.h" #define REF_FILE "/tmp/refs" @@ -161,11 +164,6 @@ static inline struct astobj2 *INTERNAL_OBJ(void *user_data) return p; } -enum ao2_callback_type { - DEFAULT, - WITH_DATA, -}; - /*! * \brief convert from a pointer _p to an astobj2 object * @@ -181,6 +179,7 @@ int __ao2_lock(void *user_data, enum ao2_lock_req lock_how, const char *file, co int res = 0; if (obj == NULL) { + ast_assert(0); return -1; } @@ -239,6 +238,7 @@ int __ao2_unlock(void *user_data, const char *file, const char *func, int line, int current_value; if (obj == NULL) { + ast_assert(0); return -1; } @@ -287,6 +287,7 @@ int __ao2_trylock(void *user_data, enum ao2_lock_req lock_how, const char *file, int res = 0; if (obj == NULL) { + ast_assert(0); return -1; } @@ -406,6 +407,7 @@ void *ao2_object_get_lockaddr(void *user_data) struct astobj2_lock *obj_mutex; if (obj == NULL) { + ast_assert(0); return NULL; } @@ -429,6 +431,7 @@ static int internal_ao2_ref(void *user_data, int delta, const char *file, int li int ret; if (obj == NULL) { + ast_assert(0); return -1; } @@ -513,8 +516,10 @@ int __ao2_ref_debug(void *user_data, int delta, const char *tag, const char *fil { struct astobj2 *obj = INTERNAL_OBJ(user_data); - if (obj == NULL) + if (obj == NULL) { + ast_assert(0); return -1; + } if (delta != 0) { FILE *refo = fopen(REF_FILE, "a"); @@ -539,6 +544,13 @@ int __ao2_ref(void *user_data, int delta) return internal_ao2_ref(user_data, delta, __FILE__, __LINE__, __FUNCTION__); } +void ao2_cleanup(void *obj) +{ + if (obj) { + ao2_ref(obj, -1); + } +} + static void *internal_ao2_alloc(size_t data_size, ao2_destructor_fn destructor_fn, unsigned int options, const char *file, int line, const char *func) { /* allocation */ @@ -645,10 +657,12 @@ void __ao2_global_obj_release(struct ao2_global_obj *holder, const char *tag, co if (!holder) { /* For sanity */ ast_log(LOG_ERROR, "Must be called with a global object!\n"); + ast_assert(0); return; } if (__ast_rwlock_wrlock(file, line, func, &holder->lock, name)) { /* Could not get the write lock. */ + ast_assert(0); return; } @@ -668,10 +682,12 @@ void *__ao2_global_obj_replace(struct ao2_global_obj *holder, void *obj, const c if (!holder) { /* For sanity */ ast_log(LOG_ERROR, "Must be called with a global object!\n"); + ast_assert(0); return NULL; } if (__ast_rwlock_wrlock(file, line, func, &holder->lock, name)) { /* Could not get the write lock. */ + ast_assert(0); return NULL; } @@ -705,11 +721,13 @@ void *__ao2_global_obj_ref(struct ao2_global_obj *holder, const char *tag, const if (!holder) { /* For sanity */ ast_log(LOG_ERROR, "Must be called with a global object!\n"); + ast_assert(0); return NULL; } if (__ast_rwlock_rdlock(file, line, func, &holder->lock, name)) { /* Could not get the read lock. */ + ast_assert(0); return NULL; } @@ -723,192 +741,339 @@ void *__ao2_global_obj_ref(struct ao2_global_obj *holder, const char *tag, const return obj; } -/* internal callback to destroy a container. */ -static void container_destruct(void *c); +enum ao2_callback_type { + AO2_CALLBACK_DEFAULT, + AO2_CALLBACK_WITH_DATA, +}; + +enum ao2_container_insert { + /*! The node was inserted into the container. */ + AO2_CONTAINER_INSERT_NODE_INSERTED, + /*! The node object replaced an existing node object. */ + AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED, + /*! The node was rejected (duplicate). */ + AO2_CONTAINER_INSERT_NODE_REJECTED, +}; -/* internal callback to destroy a container. */ -static void container_destruct_debug(void *c); +enum ao2_container_rtti { + /*! This is a hash container */ + AO2_CONTAINER_RTTI_HASH, +}; /*! - * A structure to create a linked list of entries, - * used within a bucket. - * XXX \todo this should be private to the container code + * \brief Generic container node. + * + * \details This is the base container node type that contains + * values common to all container nodes. */ -struct bucket_entry { - AST_LIST_ENTRY(bucket_entry) entry; - int version; - struct astobj2 *astobj;/* pointer to internal data */ +struct ao2_container_node { + /*! Stored object in node. */ + void *obj; + /*! Container holding the node. (Does not hold a reference.) */ + struct ao2_container *my_container; + /*! TRUE if the node is linked into the container. */ + unsigned int is_linked:1; }; -/* each bucket in the container is a tailq. */ -AST_LIST_HEAD_NOLOCK(bucket, bucket_entry); +/*! + * \brief Destroy this container. + * + * \param self Container to operate upon. + * + * \return Nothing + */ +typedef void (*ao2_container_destroy_fn)(struct ao2_container *self); /*! - * A container; stores the hash and callback functions, information on - * the size, the hash bucket heads, and a version number, starting at 0 - * (for a newly created, empty container) - * and incremented every time an object is inserted or deleted. - * The assumption is that an object is never moved in a container, - * but removed and readded with the new number. - * The version number is especially useful when implementing iterators. - * In fact, we can associate a unique, monotonically increasing number to - * each object, which means that, within an iterator, we can store the - * version number of the current object, and easily look for the next one, - * which is the next one in the list with a higher number. - * Since all objects have a version >0, we can use 0 as a marker for - * 'we need the first object in the bucket'. - * - * \todo Linking and unlink objects is typically expensive, as it - * involves a malloc() of a small object which is very inefficient. - * To optimize this, we allocate larger arrays of bucket_entry's - * when we run out of them, and then manage our own freelist. - * This will be more efficient as we can do the freelist management while - * we hold the lock (that we need anyways). + * \brief Create an empty copy of this container. + * + * \param self Container to operate upon. + * + * \retval empty-container on success. + * \retval NULL on error. */ -struct ao2_container { - ao2_hash_fn *hash_fn; - ao2_callback_fn *cmp_fn; - int n_buckets; - /*! Number of elements in the container */ - int elements; - /*! described above */ - int version; - /*! variable size */ - struct bucket buckets[0]; -}; +typedef struct ao2_container *(*ao2_container_alloc_empty_clone_fn)(struct ao2_container *self); /*! - * \brief always zero hash function + * \brief Create an empty copy of this container. (Debug version) * - * it is convenient to have a hash function that always returns 0. - * This is basically used when we want to have a container that is - * a simple linked list. + * \param self Container to operate upon. + * \param tag used for debugging. + * \param file Debug file name invoked from + * \param line Debug line invoked from + * \param func Debug function name invoked from + * \param ref_debug TRUE if to output a debug reference message. * - * \returns 0 + * \retval empty-container on success. + * \retval NULL on error. */ -static int hash_zero(const void *user_obj, const int flags) -{ - return 0; -} +typedef struct ao2_container *(*ao2_container_alloc_empty_clone_debug_fn)(struct ao2_container *self, const char *tag, const char *file, int line, const char *func, int ref_debug); -/* - * A container is just an object, after all! +/*! + * \brief Create a new container node. + * + * \param self Container to operate upon. + * \param obj_new Object to put into the node. + * \param tag used for debugging. + * \param file Debug file name invoked from + * \param line Debug line invoked from + * \param func Debug function name invoked from + * + * \retval initialized-node on success. + * \retval NULL on error. */ -static struct ao2_container *internal_ao2_container_alloc(struct ao2_container *c, - unsigned int n_buckets, ao2_hash_fn *hash_fn, ao2_callback_fn *cmp_fn) -{ - /* XXX maybe consistency check on arguments ? */ - /* compute the container size */ +typedef struct ao2_container_node *(*ao2_container_new_node_fn)(struct ao2_container *self, void *obj_new, const char *tag, const char *file, int line, const char *func); - if (!c) { - return NULL; - } +/*! + * \brief Insert a node into this container. + * + * \param self Container to operate upon. + * \param node Container node to insert into the container. + * + * \return enum ao2_container_insert value. + */ +typedef enum ao2_container_insert (*ao2_container_insert_fn)(struct ao2_container *self, struct ao2_container_node *node); - c->version = 1; /* 0 is a reserved value here */ - c->n_buckets = hash_fn ? n_buckets : 1; - c->hash_fn = hash_fn ? hash_fn : hash_zero; - c->cmp_fn = cmp_fn; +/*! + * \brief Find the first container node in a traversal. + * + * \param self Container to operate upon. + * \param flags search_flags to control traversing the container + * \param arg Comparison callback arg parameter. + * \param v_state Traversal state to restart container traversal. + * + * \retval node-ptr of found node (Reffed). + * \retval NULL when no node found. + */ +typedef struct ao2_container_node *(*ao2_container_find_first_fn)(struct ao2_container *self, enum search_flags flags, void *arg, void *v_state); -#ifdef AO2_DEBUG - ast_atomic_fetchadd_int(&ao2.total_containers, 1); -#endif +/*! + * \brief Find the next container node in a traversal. + * + * \param self Container to operate upon. + * \param v_state Traversal state to restart container traversal. + * \param prev Previous node returned by the traversal search functions. + * The ref ownership is passed back to this function. + * + * \retval node-ptr of found node (Reffed). + * \retval NULL when no node found. + */ +typedef struct ao2_container_node *(*ao2_container_find_next_fn)(struct ao2_container *self, void *v_state, struct ao2_container_node *prev); - return c; -} +/*! + * \brief Cleanup the container traversal state. + * + * \param v_state Traversal state to cleanup. + * + * \return Nothing + */ +typedef void (*ao2_container_find_cleanup_fn)(void *v_state); -struct ao2_container *__ao2_container_alloc_debug(unsigned int options, - unsigned int n_buckets, ao2_hash_fn *hash_fn, ao2_callback_fn *cmp_fn, - const char *tag, const char *file, int line, const char *func, int ref_debug) -{ - /* XXX maybe consistency check on arguments ? */ - /* compute the container size */ - unsigned int num_buckets = hash_fn ? n_buckets : 1; - size_t container_size = sizeof(struct ao2_container) + num_buckets * sizeof(struct bucket); - struct ao2_container *c = __ao2_alloc_debug(container_size, container_destruct_debug, options, tag, file, line, func, ref_debug); +/*! + * \brief Find the next non-empty iteration node in the container. + * + * \param self Container to operate upon. + * \param prev Previous node returned by the iterator. + * \param flags search_flags to control iterating the container. + * Only AO2_ITERATOR_DESCENDING is useful by the method. + * + * \note The container is already locked. + * + * \retval node on success. + * \retval NULL on error or no more nodes in the container. + */ +typedef struct ao2_container_node *(*ao2_iterator_next_fn)(struct ao2_container *self, struct ao2_container_node *prev, enum ao2_iterator_flags flags); - return internal_ao2_container_alloc(c, num_buckets, hash_fn, cmp_fn); -} +/*! + * \brief Display statistics of the specified container. + * + * \param self Container to display statistics. + * \param fd File descriptor to send output. + * \param prnt Print output callback function to use. + * + * \note The container is already locked for reading. + * + * \return Nothing + */ +typedef void (*ao2_container_statistics)(struct ao2_container *self, int fd, void (*prnt)(int fd, const char *fmt, ...) __attribute__((format(printf, 2, 3)))); -struct ao2_container *__ao2_container_alloc(unsigned int options, - unsigned int n_buckets, ao2_hash_fn *hash_fn, ao2_callback_fn *cmp_fn) -{ - /* XXX maybe consistency check on arguments ? */ - /* compute the container size */ - const unsigned int num_buckets = hash_fn ? n_buckets : 1; - size_t container_size = sizeof(struct ao2_container) + num_buckets * sizeof(struct bucket); - struct ao2_container *c = __ao2_alloc(container_size, container_destruct, options); +/*! + * \brief Perform an integrity check on the specified container. + * + * \param self Container to check integrity. + * + * \note The container is already locked for reading. + * + * \retval 0 on success. + * \retval -1 on error. + */ +typedef int (*ao2_container_integrity)(struct ao2_container *self); + +/*! Container virtual methods template. */ +struct ao2_container_methods { + /*! Run Time Type Identification */ + enum ao2_container_rtti type; + /*! Destroy this container. */ + ao2_container_destroy_fn destroy; + /*! \brief Create an empty copy of this container. */ + ao2_container_alloc_empty_clone_fn alloc_empty_clone; + /*! \brief Create an empty copy of this container. (Debug version) */ + ao2_container_alloc_empty_clone_debug_fn alloc_empty_clone_debug; + /*! Create a new container node. */ + ao2_container_new_node_fn new_node; + /*! Insert a node into this container. */ + ao2_container_insert_fn insert; + /*! Traverse the container, find the first node. */ + ao2_container_find_first_fn traverse_first; + /*! Traverse the container, find the next node. */ + ao2_container_find_next_fn traverse_next; + /*! Traverse the container, cleanup state. */ + ao2_container_find_cleanup_fn traverse_cleanup; + /*! Find the next iteration element in the container. */ + ao2_iterator_next_fn iterator_next; +#if defined(AST_DEVMODE) + /*! Display container debug statistics. (Method for debug purposes) */ + ao2_container_statistics stats; + /*! Perform an integrity check on the container. (Method for debug purposes) */ + ao2_container_integrity integrity; +#endif /* defined(AST_DEVMODE) */ +}; - return internal_ao2_container_alloc(c, num_buckets, hash_fn, cmp_fn); -} +/*! + * \brief Generic container type. + * + * \details This is the base container type that contains values + * common to all container types. + * + * \todo Linking and unlinking container objects is typically + * expensive, as it involves a malloc()/free() of a small object + * which is very inefficient. To optimize this, we can allocate + * larger arrays of container nodes when we run out of them, and + * then manage our own freelist. This will be more efficient as + * we can do the freelist management while we hold the lock + * (that we need anyway). + */ +struct ao2_container { + /*! Container virtual method table. */ + const struct ao2_container_methods *v_table; + /*! Container sort function if the container is sorted. */ + ao2_sort_fn *sort_fn; + /*! Container traversal matching function for ao2_find. */ + ao2_callback_fn *cmp_fn; + /*! The container option flags */ + uint32_t options; + /*! Number of elements in the container. */ + int elements; +#if defined(AST_DEVMODE) + /*! Number of nodes in the container. */ + int nodes; + /*! Maximum number of empty nodes in the container. (nodes - elements) */ + int max_empty_nodes; +#endif /* defined(AST_DEVMODE) */ + /*! + * \brief TRUE if the container is being destroyed. + * + * \note The destruction traversal should override any requested + * search order to do the most efficient order for destruction. + * + * \note There should not be any empty nodes in the container + * during destruction. If there are then an error needs to be + * issued about container node reference leaks. + */ + unsigned int destroying:1; +}; /*! * return the number of elements in the container */ int ao2_container_count(struct ao2_container *c) { - return c->elements; + return ast_atomic_fetchadd_int(&c->elements, 0); } -/* - * link an object to a container +#if defined(AST_DEVMODE) +static void hash_ao2_link_node_stat(struct ao2_container *hash, struct ao2_container_node *hash_node); +static void hash_ao2_unlink_node_stat(struct ao2_container *hash, struct ao2_container_node *hash_node); +#endif /* defined(AST_DEVMODE) */ + +/*! + * \internal + * \brief Link an object into this container. (internal) + * + * \param self Container to operate upon. + * \param obj_new Object to insert into the container. + * \param flags search_flags to control linking the object. (OBJ_NOLOCK) + * \param tag used for debugging. + * \param file Debug file name invoked from + * \param line Debug line invoked from + * \param func Debug function name invoked from + * + * \retval 0 on errors. + * \retval 1 on success. */ -static struct bucket_entry *internal_ao2_link(struct ao2_container *c, void *user_data, int flags, const char *tag, const char *file, int line, const char *func) +static int internal_ao2_link(struct ao2_container *self, void *obj_new, int flags, const char *tag, const char *file, int line, const char *func) { - int i; + int res; enum ao2_lock_req orig_lock; - /* create a new list entry */ - struct bucket_entry *p; - struct astobj2 *obj = INTERNAL_OBJ(user_data); - - if (obj == NULL) { - return NULL; - } + struct ao2_container_node *node; - if (INTERNAL_OBJ(c) == NULL) { - return NULL; - } - - p = ast_calloc(1, sizeof(*p)); - if (!p) { - return NULL; + if (!INTERNAL_OBJ(obj_new) || !INTERNAL_OBJ(self) + || !self->v_table || !self->v_table->new_node || !self->v_table->insert) { + /* Sanity checks. */ + ast_assert(0); + return 0; } - i = abs(c->hash_fn(user_data, OBJ_POINTER)); - if (flags & OBJ_NOLOCK) { - orig_lock = adjust_lock(c, AO2_LOCK_REQ_WRLOCK, 1); + orig_lock = adjust_lock(self, AO2_LOCK_REQ_WRLOCK, 1); } else { - ao2_wrlock(c); + ao2_wrlock(self); orig_lock = AO2_LOCK_REQ_MUTEX; } - i %= c->n_buckets; - p->astobj = obj; - p->version = ast_atomic_fetchadd_int(&c->version, 1); - AST_LIST_INSERT_TAIL(&c->buckets[i], p, entry); - ast_atomic_fetchadd_int(&c->elements, 1); + res = 0; + node = self->v_table->new_node(self, obj_new, tag, file, line, func); + if (node) { + /* Insert the new node. */ + switch (self->v_table->insert(self, node)) { + case AO2_CONTAINER_INSERT_NODE_INSERTED: + node->is_linked = 1; + ast_atomic_fetchadd_int(&self->elements, 1); +#if defined(AST_DEVMODE) + ++self->nodes; + switch (self->v_table->type) { + case AO2_CONTAINER_RTTI_HASH: + hash_ao2_link_node_stat(self, node); + break; + } +#endif /* defined(AST_DEVMODE) */ - if (tag) { - __ao2_ref_debug(user_data, +1, tag, file, line, func); - } else { - __ao2_ref(user_data, +1); + res = 1; + break; + case AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED: + res = 1; + /* Fall through */ + case AO2_CONTAINER_INSERT_NODE_REJECTED: + __ao2_ref(node, -1); + break; + } } if (flags & OBJ_NOLOCK) { - adjust_lock(c, orig_lock, 0); + adjust_lock(self, orig_lock, 0); } else { - ao2_unlock(c); + ao2_unlock(self); } - return p; + return res; } -void *__ao2_link_debug(struct ao2_container *c, void *obj_new, int flags, const char *tag, const char *file, int line, const char *func) +int __ao2_link_debug(struct ao2_container *c, void *obj_new, int flags, const char *tag, const char *file, int line, const char *func) { return internal_ao2_link(c, obj_new, flags, tag, file, line, func); } -void *__ao2_link(struct ao2_container *c, void *obj_new, int flags) +int __ao2_link(struct ao2_container *c, void *obj_new, int flags) { return internal_ao2_link(c, obj_new, flags, NULL, __FILE__, __LINE__, __PRETTY_FUNCTION__); } @@ -928,7 +1093,9 @@ int ao2_match_by_addr(void *user_data, void *arg, int flags) void *__ao2_unlink_debug(struct ao2_container *c, void *user_data, int flags, const char *tag, const char *file, int line, const char *func) { - if (INTERNAL_OBJ(user_data) == NULL) { /* safety check on the argument */ + if (!INTERNAL_OBJ(user_data)) { + /* Sanity checks. */ + ast_assert(0); return NULL; } @@ -940,7 +1107,9 @@ void *__ao2_unlink_debug(struct ao2_container *c, void *user_data, int flags, void *__ao2_unlink(struct ao2_container *c, void *user_data, int flags) { - if (INTERNAL_OBJ(user_data) == NULL) { /* safety check on the argument */ + if (!INTERNAL_OBJ(user_data)) { + /* Sanity checks. */ + ast_assert(0); return NULL; } @@ -966,27 +1135,51 @@ static int cb_true_data(void *user_data, void *arg, void *data, int flags) return CMP_MATCH; } +/*! Allow enough room for container specific traversal state structs */ +#define AO2_TRAVERSAL_STATE_SIZE 100 + /*! - * Browse the container using different stategies accoding the flags. - * \return Is a pointer to an object or to a list of object if OBJ_MULTIPLE is - * specified. - * Luckily, for debug purposes, the added args (tag, file, line, func) - * aren't an excessive load to the system, as the callback should not be - * called as often as, say, the ao2_ref func is called. + * \internal + * \brief Traverse the container. (internal) + * + * \param self Container to operate upon. + * \param flags search_flags to control traversing the container + * \param cb_fn Comparison callback function. + * \param arg Comparison callback arg parameter. + * \param data Data comparison callback data parameter. + * \param type Type of comparison callback cb_fn. + * \param tag used for debugging. + * \param file Debug file name invoked from + * \param line Debug line invoked from + * \param func Debug function name invoked from + * + * \retval NULL on failure or no matching object found. + * + * \retval object found if OBJ_MULTIPLE is not set in the flags + * parameter. + * + * \retval ao2_iterator pointer if OBJ_MULTIPLE is set in the + * flags parameter. The iterator must be destroyed with + * ao2_iterator_destroy() when the caller no longer needs it. */ -static void *internal_ao2_callback(struct ao2_container *c, enum search_flags flags, - void *cb_fn, void *arg, void *data, enum ao2_callback_type type, const char *tag, - const char *file, int line, const char *func) +static void *internal_ao2_traverse(struct ao2_container *self, enum search_flags flags, + void *cb_fn, void *arg, void *data, enum ao2_callback_type type, + const char *tag, const char *file, int line, const char *func) { - int i, start, last; /* search boundaries */ - enum ao2_lock_req orig_lock; - void *ret = NULL; + void *ret; ao2_callback_fn *cb_default = NULL; ao2_callback_data_fn *cb_withdata = NULL; + struct ao2_container_node *node; + void *traversal_state; + + enum ao2_lock_req orig_lock; struct ao2_container *multi_container = NULL; struct ao2_iterator *multi_iterator = NULL; - if (INTERNAL_OBJ(c) == NULL) { /* safety check on the argument */ + if (!INTERNAL_OBJ(self) || !self->v_table || !self->v_table->traverse_first + || !self->v_table->traverse_next) { + /* Sanity checks. */ + ast_assert(0); return NULL; } @@ -1003,7 +1196,8 @@ static void *internal_ao2_callback(struct ao2_container *c, enum search_flags fl * is destroyed, the container will be automatically * destroyed as well. */ - multi_container = __ao2_container_alloc(AO2_ALLOC_OPT_LOCK_NOLOCK, 1, NULL, NULL); + multi_container = __ao2_container_alloc_list(AO2_ALLOC_OPT_LOCK_NOLOCK, 0, NULL, + NULL); if (!multi_container) { return NULL; } @@ -1013,159 +1207,171 @@ static void *internal_ao2_callback(struct ao2_container *c, enum search_flags fl } } - /* override the match function if necessary */ - if (cb_fn == NULL) { /* if NULL, match everything */ - if (type == WITH_DATA) { + if (!cb_fn) { + /* Match everything if no callback match function provided. */ + if (type == AO2_CALLBACK_WITH_DATA) { cb_withdata = cb_true_data; } else { cb_default = cb_true; } } else { - /* We do this here to avoid the per object casting penalty (even though - that is probably optimized away anyway). */ - if (type == WITH_DATA) { + /* + * We do this here to avoid the per object casting penalty (even + * though that is probably optimized away anyway). + */ + if (type == AO2_CALLBACK_WITH_DATA) { cb_withdata = cb_fn; } else { cb_default = cb_fn; } } - /* - * XXX this can be optimized. - * If we have a hash function and lookup by pointer, - * run the hash function. Otherwise, scan the whole container - * (this only for the time being. We need to optimize this.) - */ - if ((flags & (OBJ_POINTER | OBJ_KEY))) { - /* we know hash can handle this case */ - start = i = c->hash_fn(arg, flags & (OBJ_POINTER | OBJ_KEY)) % c->n_buckets; - } else { - /* don't know, let's scan all buckets */ - start = i = -1; /* XXX this must be fixed later. */ - } - - /* determine the search boundaries: i..last-1 */ - if (i < 0) { - start = i = 0; - last = c->n_buckets; - } else if ((flags & OBJ_CONTINUE)) { - last = c->n_buckets; - } else { - last = i + 1; - } - /* avoid modifications to the content */ if (flags & OBJ_NOLOCK) { if (flags & OBJ_UNLINK) { - orig_lock = adjust_lock(c, AO2_LOCK_REQ_WRLOCK, 1); + orig_lock = adjust_lock(self, AO2_LOCK_REQ_WRLOCK, 1); } else { - orig_lock = adjust_lock(c, AO2_LOCK_REQ_RDLOCK, 1); + orig_lock = adjust_lock(self, AO2_LOCK_REQ_RDLOCK, 1); } } else { orig_lock = AO2_LOCK_REQ_MUTEX; if (flags & OBJ_UNLINK) { - ao2_wrlock(c); + ao2_wrlock(self); } else { - ao2_rdlock(c); + ao2_rdlock(self); } } - for (; i < last ; i++) { - /* scan the list with prev-cur pointers */ - struct bucket_entry *cur; + /* Create a buffer for the traversal state. */ + traversal_state = alloca(AO2_TRAVERSAL_STATE_SIZE); - AST_LIST_TRAVERSE_SAFE_BEGIN(&c->buckets[i], cur, entry) { - int match = (CMP_MATCH | CMP_STOP); - - if (type == WITH_DATA) { - match &= cb_withdata(EXTERNAL_OBJ(cur->astobj), arg, data, flags); - } else { - match &= cb_default(EXTERNAL_OBJ(cur->astobj), arg, flags); - } + ret = NULL; + for (node = self->v_table->traverse_first(self, flags, arg, traversal_state); + node; + node = self->v_table->traverse_next(self, traversal_state, node)) { + int match; - /* we found the object, performing operations according flags */ - if (match == 0) { /* no match, no stop, continue */ - continue; - } else if (match == CMP_STOP) { /* no match but stop, we are done */ - i = last; - break; - } + /* Visit the current node. */ + match = (CMP_MATCH | CMP_STOP); + if (type == AO2_CALLBACK_WITH_DATA) { + match &= cb_withdata(node->obj, arg, data, flags); + } else { + match &= cb_default(node->obj, arg, flags); + } + if (match == 0) { + /* no match, no stop, continue */ + continue; + } + if (match == CMP_STOP) { + /* no match but stop, we are done */ + break; + } - /* we have a match (CMP_MATCH) here */ - if (!(flags & OBJ_NODATA)) { /* if must return the object, record the value */ - /* it is important to handle this case before the unlink */ - ret = EXTERNAL_OBJ(cur->astobj); - if (!(flags & (OBJ_UNLINK | OBJ_MULTIPLE))) { + /* + * CMP_MATCH is set here + * + * we found the object, performing operations according to flags + */ + if (node->obj) { + /* The object is still in the container. */ + if (!(flags & OBJ_NODATA)) { + /* + * We are returning the object, record the value. It is + * important to handle this case before the unlink. + */ + if (multi_container) { + /* + * Link the object into the container that will hold the + * results. + */ if (tag) { - __ao2_ref_debug(ret, 1, tag, file, line, func); + __ao2_link_debug(multi_container, node->obj, flags, + tag, file, line, func); } else { - __ao2_ref(ret, 1); + __ao2_link(multi_container, node->obj, flags); } - } - } - - /* If we are in OBJ_MULTIPLE mode and OBJ_NODATA is off, - * link the object into the container that will hold the results. - */ - if (ret && (multi_container != NULL)) { - if (tag) { - __ao2_link_debug(multi_container, ret, flags, tag, file, line, func); } else { - __ao2_link(multi_container, ret, flags); + ret = node->obj; + /* Returning a single object. */ + if (!(flags & OBJ_UNLINK)) { + /* + * Bump the ref count since we are not going to unlink and + * transfer the container's object ref to the returned object. + */ + if (tag) { + __ao2_ref_debug(ret, 1, tag, file, line, func); + } else { + __ao2_ref(ret, 1); + } + } } - ret = NULL; } - if (flags & OBJ_UNLINK) { /* must unlink */ - /* we are going to modify the container, so update version */ - ast_atomic_fetchadd_int(&c->version, 1); - AST_LIST_REMOVE_CURRENT(entry); + if (flags & OBJ_UNLINK) { /* update number of elements */ - ast_atomic_fetchadd_int(&c->elements, -1); - - /* - When unlinking and not returning the result, (OBJ_NODATA), the ref from the container - * must be decremented. - * - When unlinking with OBJ_MULTIPLE the ref from the original container - * must be decremented regardless if OBJ_NODATA is used. This is because the result is - * returned in a new container that already holds its own ref for the object. If the ref - * from the original container is not accounted for here a memory leak occurs. */ - if (flags & (OBJ_NODATA | OBJ_MULTIPLE)) { - if (tag) - __ao2_ref_debug(EXTERNAL_OBJ(cur->astobj), -1, tag, file, line, func); - else - __ao2_ref(EXTERNAL_OBJ(cur->astobj), -1); + ast_atomic_fetchadd_int(&self->elements, -1); +#if defined(AST_DEVMODE) + { + int empty = self->nodes - self->elements; + + if (self->max_empty_nodes < empty) { + self->max_empty_nodes = empty; + } } - ast_free(cur); /* free the link record */ - } + switch (self->v_table->type) { + case AO2_CONTAINER_RTTI_HASH: + hash_ao2_unlink_node_stat(self, node); + break; + } +#endif /* defined(AST_DEVMODE) */ + + /* + * - When unlinking and not returning the result, OBJ_NODATA is + * set, the ref from the container must be decremented. + * + * - When unlinking with a multi_container the ref from the + * original container must be decremented. This is because the + * result is returned in a new container that already holds its + * own ref for the object. + * + * If the ref from the original container is not accounted for + * here a memory leak occurs. + */ + if (multi_container || (flags & OBJ_NODATA)) { + if (tag) { + __ao2_ref_debug(node->obj, -1, tag, file, line, func); + } else { + __ao2_ref(node->obj, -1); + } + } + node->obj = NULL; - if ((match & CMP_STOP) || !(flags & OBJ_MULTIPLE)) { - /* We found our only (or last) match, so force an exit from - the outside loop. */ - i = last; - break; + /* Unref the node from the container. */ + __ao2_ref(node, -1); } } - AST_LIST_TRAVERSE_SAFE_END; - if (ret) { + if ((match & CMP_STOP) || !(flags & OBJ_MULTIPLE)) { + /* We found our only (or last) match, so we are done */ break; } - - if (i == c->n_buckets - 1 && (flags & OBJ_POINTER) && (flags & OBJ_CONTINUE)) { - /* Move to the beginning to ensure we check every bucket */ - i = -1; - last = start; - } + } + if (self->v_table->traverse_cleanup) { + self->v_table->traverse_cleanup(traversal_state); + } + if (node) { + /* Unref the node from self->v_table->traverse_first/traverse_next() */ + __ao2_ref(node, -1); } if (flags & OBJ_NOLOCK) { - adjust_lock(c, orig_lock, 0); + adjust_lock(self, orig_lock, 0); } else { - ao2_unlock(c); + ao2_unlock(self); } /* if multi_container was created, we are returning multiple objects */ - if (multi_container != NULL) { + if (multi_container) { *multi_iterator = ao2_iterator_init(multi_container, AO2_ITERATOR_UNLINK | AO2_ITERATOR_MALLOCD); ao2_ref(multi_container, -1); @@ -1179,26 +1385,26 @@ void *__ao2_callback_debug(struct ao2_container *c, enum search_flags flags, ao2_callback_fn *cb_fn, void *arg, const char *tag, const char *file, int line, const char *func) { - return internal_ao2_callback(c,flags, cb_fn, arg, NULL, DEFAULT, tag, file, line, func); + return internal_ao2_traverse(c, flags, cb_fn, arg, NULL, AO2_CALLBACK_DEFAULT, tag, file, line, func); } void *__ao2_callback(struct ao2_container *c, enum search_flags flags, ao2_callback_fn *cb_fn, void *arg) { - return internal_ao2_callback(c,flags, cb_fn, arg, NULL, DEFAULT, NULL, NULL, 0, NULL); + return internal_ao2_traverse(c, flags, cb_fn, arg, NULL, AO2_CALLBACK_DEFAULT, NULL, NULL, 0, NULL); } void *__ao2_callback_data_debug(struct ao2_container *c, enum search_flags flags, ao2_callback_data_fn *cb_fn, void *arg, void *data, const char *tag, const char *file, int line, const char *func) { - return internal_ao2_callback(c, flags, cb_fn, arg, data, WITH_DATA, tag, file, line, func); + return internal_ao2_traverse(c, flags, cb_fn, arg, data, AO2_CALLBACK_WITH_DATA, tag, file, line, func); } void *__ao2_callback_data(struct ao2_container *c, enum search_flags flags, ao2_callback_data_fn *cb_fn, void *arg, void *data) { - return internal_ao2_callback(c, flags, cb_fn, arg, data, WITH_DATA, NULL, NULL, 0, NULL); + return internal_ao2_traverse(c, flags, cb_fn, arg, data, AO2_CALLBACK_WITH_DATA, NULL, NULL, 0, NULL); } /*! @@ -1209,6 +1415,11 @@ void *__ao2_find_debug(struct ao2_container *c, const void *arg, enum search_fla { void *arged = (void *) arg;/* Done to avoid compiler const warning */ + if (!c) { + /* Sanity checks. */ + ast_assert(0); + return NULL; + } return __ao2_callback_debug(c, flags, c->cmp_fn, arged, tag, file, line, func); } @@ -1216,6 +1427,11 @@ void *__ao2_find(struct ao2_container *c, const void *arg, enum search_flags fla { void *arged = (void *) arg;/* Done to avoid compiler const warning */ + if (!c) { + /* Sanity checks. */ + ast_assert(0); + return NULL; + } return __ao2_callback(c, flags, c->cmp_fn, arged); } @@ -1234,16 +1450,57 @@ struct ao2_iterator ao2_iterator_init(struct ao2_container *c, int flags) return a; } -/*! - * destroy an iterator - */ +void ao2_iterator_restart(struct ao2_iterator *iter) +{ + /* Release the last container node reference if we have one. */ + if (iter->last_node) { + enum ao2_lock_req orig_lock; + + /* + * Do a read lock in case the container node unref does not + * destroy the node. If the container node is destroyed then + * the lock will be upgraded to a write lock. + */ + if (iter->flags & AO2_ITERATOR_DONTLOCK) { + orig_lock = adjust_lock(iter->c, AO2_LOCK_REQ_RDLOCK, 1); + } else { + orig_lock = AO2_LOCK_REQ_MUTEX; + ao2_rdlock(iter->c); + } + + ao2_ref(iter->last_node, -1); + iter->last_node = NULL; + + if (iter->flags & AO2_ITERATOR_DONTLOCK) { + adjust_lock(iter->c, orig_lock, 0); + } else { + ao2_unlock(iter->c); + } + } + + /* The iteration is no longer complete. */ + iter->complete = 0; +} + void ao2_iterator_destroy(struct ao2_iterator *iter) { + /* Release any last container node reference. */ + ao2_iterator_restart(iter); + + /* Release the iterated container reference. */ ao2_ref(iter->c, -1); + iter->c = NULL; + + /* Free the malloced iterator. */ if (iter->flags & AO2_ITERATOR_MALLOCD) { ast_free(iter); - } else { - iter->c = NULL; + } +} + +void ao2_iterator_cleanup(struct ao2_iterator *iter) +{ + if (iter) { + ao2_iterator_destroy(iter); } } @@ -1252,12 +1509,18 @@ void ao2_iterator_destroy(struct ao2_iterator *iter) */ static void *internal_ao2_iterator_next(struct ao2_iterator *iter, const char *tag, const char *file, int line, const char *func) { - int lim; enum ao2_lock_req orig_lock; - struct bucket_entry *p = NULL; + struct ao2_container_node *node; void *ret; - if (INTERNAL_OBJ(iter->c) == NULL) { + if (!INTERNAL_OBJ(iter->c) || !iter->c->v_table || !iter->c->v_table->iterator_next) { + /* Sanity checks. */ + ast_assert(0); + return NULL; + } + + if (iter->complete) { + /* Don't return any more objects. */ return NULL; } @@ -1276,65 +1539,55 @@ static void *internal_ao2_iterator_next(struct ao2_iterator *iter, const char *t } } - /* optimization. If the container is unchanged and - * we have a pointer, try follow it - */ - if (iter->c->version == iter->c_version && (p = iter->obj)) { - if ((p = AST_LIST_NEXT(p, entry))) { - goto found; - } - /* nope, start from the next bucket */ - iter->bucket++; - iter->version = 0; - iter->obj = NULL; - } - - lim = iter->c->n_buckets; - - /* Browse the buckets array, moving to the next - * buckets if we don't find the entry in the current one. - * Stop when we find an element with version number greater - * than the current one (we reset the version to 0 when we - * switch buckets). - */ - for (; iter->bucket < lim; iter->bucket++, iter->version = 0) { - /* scan the current bucket */ - AST_LIST_TRAVERSE(&iter->c->buckets[iter->bucket], p, entry) { - if (p->version > iter->version) { - goto found; - } - } - } + node = iter->c->v_table->iterator_next(iter->c, iter->last_node, iter->flags); + if (node) { + ret = node->obj; -found: - if (p) { - ret = EXTERNAL_OBJ(p->astobj); if (iter->flags & AO2_ITERATOR_UNLINK) { - /* we are going to modify the container, so update version */ - ast_atomic_fetchadd_int(&iter->c->version, 1); - AST_LIST_REMOVE(&iter->c->buckets[iter->bucket], p, entry); /* update number of elements */ ast_atomic_fetchadd_int(&iter->c->elements, -1); - iter->version = 0; - iter->obj = NULL; - iter->c_version = iter->c->version; - ast_free(p); - } else { - iter->version = p->version; - iter->obj = p; - iter->c_version = iter->c->version; +#if defined(AST_DEVMODE) + { + int empty = iter->c->nodes - iter->c->elements; + + if (iter->c->max_empty_nodes < empty) { + iter->c->max_empty_nodes = empty; + } + } + switch (iter->c->v_table->type) { + case AO2_CONTAINER_RTTI_HASH: + hash_ao2_unlink_node_stat(iter->c, node); + break; + } +#endif /* defined(AST_DEVMODE) */ - /* inc refcount of returned object */ + /* Transfer the object ref from the container to the returned object. */ + node->obj = NULL; + + /* Transfer the container's node ref to the iterator. */ + } else { + /* Bump ref of returned object */ if (tag) { - __ao2_ref_debug(ret, 1, tag, file, line, func); + __ao2_ref_debug(ret, +1, tag, file, line, func); } else { - __ao2_ref(ret, 1); + __ao2_ref(ret, +1); } + + /* Bump the container's node ref for the iterator. */ + __ao2_ref(node, +1); } } else { + /* The iteration has completed. */ + iter->complete = 1; ret = NULL; } + /* Replace the iterator's node */ + if (iter->last_node) { + __ao2_ref(iter->last_node, -1); + } + iter->last_node = node; + if (iter->flags & AO2_ITERATOR_DONTLOCK) { adjust_lock(iter->c, orig_lock, 0); } else { @@ -1354,34 +1607,17 @@ void *__ao2_iterator_next(struct ao2_iterator *iter) return internal_ao2_iterator_next(iter, NULL, __FILE__, __LINE__, __PRETTY_FUNCTION__); } -/* callback for destroying container. - * we can make it simple as we know what it does - */ -static int cd_cb(void *obj, void *arg, int flag) -{ - __ao2_ref(obj, -1); - return 0; -} - -static int cd_cb_debug(void *obj, void *arg, int flag) -{ - __ao2_ref_debug(obj, -1, "deref object via container destroy", __FILE__, __LINE__, __PRETTY_FUNCTION__); - return 0; -} - static void container_destruct(void *_c) { struct ao2_container *c = _c; - int i; - - __ao2_callback(c, OBJ_UNLINK, cd_cb, NULL); - for (i = 0; i < c->n_buckets; i++) { - struct bucket_entry *current; + /* Unlink any stored objects in the container. */ + c->destroying = 1; + __ao2_callback(c, OBJ_UNLINK | OBJ_NODATA | OBJ_MULTIPLE, NULL, NULL); - while ((current = AST_LIST_REMOVE_HEAD(&c->buckets[i], entry))) { - ast_free(current); - } + /* Perform any extra container cleanup. */ + if (c->v_table && c->v_table->destroy) { + c->v_table->destroy(c); } #ifdef AO2_DEBUG @@ -1392,16 +1628,15 @@ static void container_destruct(void *_c) static void container_destruct_debug(void *_c) { struct ao2_container *c = _c; - int i; - - __ao2_callback_debug(c, OBJ_UNLINK, cd_cb_debug, NULL, "container_destruct_debug called", __FILE__, __LINE__, __PRETTY_FUNCTION__); - for (i = 0; i < c->n_buckets; i++) { - struct bucket_entry *current; + /* Unlink any stored objects in the container. */ + c->destroying = 1; + __ao2_callback_debug(c, OBJ_UNLINK | OBJ_NODATA | OBJ_MULTIPLE, NULL, NULL, + "container_destruct_debug called", __FILE__, __LINE__, __PRETTY_FUNCTION__); - while ((current = AST_LIST_REMOVE_HEAD(&c->buckets[i], entry))) { - ast_free(current); - } + /* Perform any extra container cleanup. */ + if (c->v_table && c->v_table->destroy) { + c->v_table->destroy(c); } #ifdef AO2_DEBUG @@ -1458,18 +1693,15 @@ int ao2_container_dup(struct ao2_container *dest, struct ao2_container *src, enu struct ao2_container *__ao2_container_clone(struct ao2_container *orig, enum search_flags flags) { struct ao2_container *clone; - struct astobj2 *orig_obj; - unsigned int options; int failed; - orig_obj = INTERNAL_OBJ(orig); - if (!orig_obj) { + /* Create the clone container with the same properties as the original. */ + if (!INTERNAL_OBJ(orig) || !orig->v_table || !orig->v_table->alloc_empty_clone) { + /* Sanity checks. */ + ast_assert(0); return NULL; } - options = orig_obj->priv_data.options; - - /* Create the clone container with the same properties as the original. */ - clone = __ao2_container_alloc(options, orig->n_buckets, orig->hash_fn, orig->cmp_fn); + clone = orig->v_table->alloc_empty_clone(orig); if (!clone) { return NULL; } @@ -1492,19 +1724,15 @@ struct ao2_container *__ao2_container_clone(struct ao2_container *orig, enum sea struct ao2_container *__ao2_container_clone_debug(struct ao2_container *orig, enum search_flags flags, const char *tag, const char *file, int line, const char *func, int ref_debug) { struct ao2_container *clone; - struct astobj2 *orig_obj; - unsigned int options; int failed; - orig_obj = INTERNAL_OBJ(orig); - if (!orig_obj) { + /* Create the clone container with the same properties as the original. */ + if (!INTERNAL_OBJ(orig) || !orig->v_table || !orig->v_table->alloc_empty_clone_debug) { + /* Sanity checks. */ + ast_assert(0); return NULL; } - options = orig_obj->priv_data.options; - - /* Create the clone container with the same properties as the original. */ - clone = __ao2_container_alloc_debug(options, orig->n_buckets, orig->hash_fn, - orig->cmp_fn, tag, file, line, func, ref_debug); + clone = orig->v_table->alloc_empty_clone_debug(orig, tag, file, line, func, ref_debug); if (!clone) { return NULL; } @@ -1528,18 +1756,1260 @@ struct ao2_container *__ao2_container_clone_debug(struct ao2_container *orig, en return clone; } -void ao2_cleanup(void *obj) +#if defined(AST_DEVMODE) +/*! + * \internal + * \brief Display statistics of the specified container. + * \since 12.0.0 + * + * \param self Container to display statistics. + * \param fd File descriptor to send output. + * \param prnt Print output callback function to use. + * + * \return Nothing + */ +static void ao2_container_stats(struct ao2_container *self, int fd, void (*prnt)(int fd, const char *fmt, ...) __attribute__((format(printf, 2, 3)))) { - if (obj) { - ao2_ref(obj, -1); + if (!INTERNAL_OBJ(self) || !self->v_table) { + prnt(fd, "Invalid container\n"); + ast_assert(0); + return; + } + + ao2_rdlock(self); + prnt(fd, "Number of objects: %d\n", self->elements); + prnt(fd, "Number of nodes: %d\n", self->nodes); + prnt(fd, "Number of empty nodes: %d\n", self->nodes - self->elements); + /* + * XXX + * If the max_empty_nodes count gets out of single digits you + * likely have a code path where ao2_iterator_destroy() is not + * called. + * + * Empty nodes do not harm the container but they do make + * container operations less efficient. + */ + prnt(fd, "Maximum empty nodes: %d\n", self->max_empty_nodes); + if (self->v_table->stats) { + self->v_table->stats(self, fd, prnt); } + ao2_unlock(self); } +#endif /* defined(AST_DEVMODE) */ -void ao2_iterator_cleanup(struct ao2_iterator *iter) +int ao2_container_check(struct ao2_container *self, enum search_flags flags) { - if (iter) { - ao2_iterator_destroy(iter); + int res = 0; + + if (!INTERNAL_OBJ(self) || !self->v_table) { + /* Sanity checks. */ + ast_assert(0); + return -1; + } +#if defined(AST_DEVMODE) + if (!self->v_table->integrity) { + /* No ingetrigy check available. Assume container is ok. */ + return 0; + } + + if (!(flags & OBJ_NOLOCK)) { + ao2_rdlock(self); + } + res = self->v_table->integrity(self); + if (!(flags & OBJ_NOLOCK)) { + ao2_unlock(self); + } +#endif /* defined(AST_DEVMODE) */ + return res; +} + +/*! + * A structure to create a linked list of entries, + * used within a bucket. + */ +struct hash_bucket_node { + /*! + * \brief Items common to all container nodes. + * \note Must be first in the specific node struct. + */ + struct ao2_container_node common; + /*! Next node links in the list. */ + AST_DLLIST_ENTRY(hash_bucket_node) links; + /*! Hash bucket holding the node. */ + int my_bucket; +}; + +struct hash_bucket { + /*! List of objects held in the bucket. */ + AST_DLLIST_HEAD_NOLOCK(, hash_bucket_node) list; +#if defined(AST_DEVMODE) + /*! Number of elements currently in the bucket. */ + int elements; + /*! Maximum number of elements in the bucket. */ + int max_elements; +#endif /* defined(AST_DEVMODE) */ +}; + +/*! + * A hash container in addition to values common to all + * container types, stores the hash callback function, the + * number of hash buckets, and the hash bucket heads. + */ +struct ao2_container_hash { + /*! + * \brief Items common to all containers. + * \note Must be first in the specific container struct. + */ + struct ao2_container common; + ao2_hash_fn *hash_fn; + /*! Number of hash buckets in this container. */ + int n_buckets; + /*! Hash bucket array of n_buckets. Variable size. */ + struct hash_bucket buckets[0]; +}; + +/*! + * \internal + * \brief Create an empty copy of this container. + * \since 12.0.0 + * + * \param self Container to operate upon. + * + * \retval empty-clone-container on success. + * \retval NULL on error. + */ +static struct ao2_container *hash_ao2_alloc_empty_clone(struct ao2_container_hash *self) +{ + struct astobj2 *orig_obj; + unsigned int ao2_options; + + /* Get container ao2 options. */ + orig_obj = INTERNAL_OBJ(self); + if (!orig_obj) { + return NULL; + } + ao2_options = orig_obj->priv_data.options; + + return __ao2_container_alloc_hash(ao2_options, self->common.options, self->n_buckets, + self->hash_fn, self->common.sort_fn, self->common.cmp_fn); +} + +/*! + * \internal + * \brief Create an empty copy of this container. (Debug version) + * \since 12.0.0 + * + * \param self Container to operate upon. + * \param tag used for debugging. + * \param file Debug file name invoked from + * \param line Debug line invoked from + * \param func Debug function name invoked from + * \param ref_debug TRUE if to output a debug reference message. + * + * \retval empty-clone-container on success. + * \retval NULL on error. + */ +static struct ao2_container *hash_ao2_alloc_empty_clone_debug(struct ao2_container_hash *self, const char *tag, const char *file, int line, const char *func, int ref_debug) +{ + struct astobj2 *orig_obj; + unsigned int ao2_options; + + /* Get container ao2 options. */ + orig_obj = INTERNAL_OBJ(self); + if (!orig_obj) { + return NULL; + } + ao2_options = orig_obj->priv_data.options; + + return __ao2_container_alloc_hash_debug(ao2_options, self->common.options, + self->n_buckets, self->hash_fn, self->common.sort_fn, self->common.cmp_fn, + tag, file, line, func, ref_debug); +} + +/*! + * \internal + * \brief Destroy a hash container list node. + * \since 12.0.0 + * + * \param v_doomed Container node to destroy. + * + * \details + * The container node unlinks itself from the container as part + * of its destruction. The node must be destroyed while the + * container is already locked. + * + * \return Nothing + */ +static void hash_ao2_node_destructor(void *v_doomed) +{ + struct hash_bucket_node *doomed = v_doomed; + + if (doomed->common.is_linked) { + struct ao2_container_hash *my_container; + struct hash_bucket *bucket; + + /* + * Promote to write lock if not already there. Since + * adjust_lock() can potentially release and block waiting for a + * write lock, care must be taken to ensure that node references + * are released before releasing the container references. + * + * Node references held by an iterator can only be held while + * the iterator also holds a reference to the container. These + * node references must be unreferenced before the container can + * be unreferenced to ensure that the node will not get a + * negative reference and the destructor called twice for the + * same node. + */ + my_container = (struct ao2_container_hash *) doomed->common.my_container; + adjust_lock(my_container, AO2_LOCK_REQ_WRLOCK, 1); + + bucket = &my_container->buckets[doomed->my_bucket]; + AST_DLLIST_REMOVE(&bucket->list, doomed, links); + +#if defined(AST_DEVMODE) + --my_container->common.nodes; +#endif /* defined(AST_DEVMODE) */ + } + + /* + * We could have an object in the node if the container is being + * destroyed or the node had not been linked in yet. + */ + if (doomed->common.obj) { + ao2_ref(doomed->common.obj, -1); + doomed->common.obj = NULL; + } +} + +/*! + * \internal + * \brief Create a new container node. + * \since 12.0.0 + * + * \param self Container to operate upon. + * \param obj_new Object to put into the node. + * \param tag used for debugging. + * \param file Debug file name invoked from + * \param line Debug line invoked from + * \param func Debug function name invoked from + * + * \retval initialized-node on success. + * \retval NULL on error. + */ +static struct hash_bucket_node *hash_ao2_new_node(struct ao2_container_hash *self, void *obj_new, const char *tag, const char *file, int line, const char *func) +{ + struct hash_bucket_node *node; + int i; + + node = __ao2_alloc(sizeof(*node), hash_ao2_node_destructor, AO2_ALLOC_OPT_LOCK_NOLOCK); + if (!node) { + return NULL; + } + + i = abs(self->hash_fn(obj_new, OBJ_POINTER)); + i %= self->n_buckets; + + if (tag) { + __ao2_ref_debug(obj_new, +1, tag, file, line, func); + } else { + __ao2_ref(obj_new, +1); + } + node->common.obj = obj_new; + node->common.my_container = (struct ao2_container *) self; + node->my_bucket = i; + + return node; +} + +/*! + * \internal + * \brief Insert a node into this container. + * \since 12.0.0 + * + * \param self Container to operate upon. + * \param node Container node to insert into the container. + * + * \return enum ao2_container_insert value. + */ +static enum ao2_container_insert hash_ao2_insert_node(struct ao2_container_hash *self, struct hash_bucket_node *node) +{ + int cmp; + struct hash_bucket *bucket; + struct hash_bucket_node *cur; + ao2_sort_fn *sort_fn; + uint32_t options; + + bucket = &self->buckets[node->my_bucket]; + sort_fn = self->common.sort_fn; + options = self->common.options; + + if (options & AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN) { + if (sort_fn) { + AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&bucket->list, cur, links) { + cmp = sort_fn(cur->common.obj, node->common.obj, OBJ_POINTER); + if (cmp > 0) { + continue; + } + if (cmp < 0) { + AST_DLLIST_INSERT_AFTER_CURRENT(node, links); + return AO2_CONTAINER_INSERT_NODE_INSERTED; + } + switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) { + default: + case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW: + break; + case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT: + /* Reject all objects with the same key. */ + return AO2_CONTAINER_INSERT_NODE_REJECTED; + case AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT: + if (cur->common.obj == node->common.obj) { + /* Reject inserting the same object */ + return AO2_CONTAINER_INSERT_NODE_REJECTED; + } + break; + case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE: + SWAP(cur->common.obj, node->common.obj); + return AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED; + } + } + AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END; + } + AST_DLLIST_INSERT_HEAD(&bucket->list, node, links); + } else { + if (sort_fn) { + AST_DLLIST_TRAVERSE_SAFE_BEGIN(&bucket->list, cur, links) { + cmp = sort_fn(cur->common.obj, node->common.obj, OBJ_POINTER); + if (cmp < 0) { + continue; + } + if (cmp > 0) { + AST_DLLIST_INSERT_BEFORE_CURRENT(node, links); + return AO2_CONTAINER_INSERT_NODE_INSERTED; + } + switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) { + default: + case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW: + break; + case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT: + /* Reject all objects with the same key. */ + return AO2_CONTAINER_INSERT_NODE_REJECTED; + case AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT: + if (cur->common.obj == node->common.obj) { + /* Reject inserting the same object */ + return AO2_CONTAINER_INSERT_NODE_REJECTED; + } + break; + case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE: + SWAP(cur->common.obj, node->common.obj); + return AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED; + } + } + AST_DLLIST_TRAVERSE_SAFE_END; + } + AST_DLLIST_INSERT_TAIL(&bucket->list, node, links); + } + return AO2_CONTAINER_INSERT_NODE_INSERTED; +} + +/*! Traversal state to restart a hash container traversal. */ +struct hash_traversal_state { + /*! Active sort function in the traversal if not NULL. */ + ao2_sort_fn *sort_fn; + /*! Node returned in the sorted starting hash bucket if OBJ_CONTINUE flag set. (Reffed) */ + struct hash_bucket_node *first_node; + /*! Saved comparison callback arg pointer. */ + void *arg; + /*! Starting hash bucket */ + int bucket_start; + /*! Stopping hash bucket */ + int bucket_last; + /*! Saved search flags to control traversing the container. */ + enum search_flags flags; + /*! TRUE if it is a descending search */ + unsigned int descending:1; + /*! TRUE if the starting bucket needs to be rechecked because of sorting skips. */ + unsigned int recheck_starting_bucket:1; +}; + +struct hash_traversal_state_check { + /* + * If we have a division by zero compile error here then there + * is not enough room for the state. Increase AO2_TRAVERSAL_STATE_SIZE. + */ + char check[1 / (AO2_TRAVERSAL_STATE_SIZE / sizeof(struct hash_traversal_state))]; +}; + +/*! + * \internal + * \brief Find the first hash container node in a traversal. + * \since 12.0.0 + * + * \param self Container to operate upon. + * \param flags search_flags to control traversing the container + * \param arg Comparison callback arg parameter. + * \param state Traversal state to restart hash container traversal. + * + * \retval node-ptr of found node (Reffed). + * \retval NULL when no node found. + */ +static struct hash_bucket_node *hash_ao2_find_first(struct ao2_container_hash *self, enum search_flags flags, void *arg, struct hash_traversal_state *state) +{ + struct hash_bucket_node *node; + int bucket_cur; + int cmp; + + memset(state, 0, sizeof(*state)); + state->arg = arg; + state->flags = flags; + + /* Determine traversal order. */ + switch (flags & OBJ_ORDER_MASK) { + case OBJ_ORDER_DESCENDING: + state->descending = 1; + break; + case OBJ_ORDER_ASCENDING: + default: + break; + } + + /* + * If lookup by pointer or search key, run the hash and optional + * sort functions. Otherwise, traverse the whole container. + */ + if (flags & (OBJ_POINTER | OBJ_KEY)) { + /* we know hash can handle this case */ + bucket_cur = abs(self->hash_fn(arg, flags & (OBJ_POINTER | OBJ_KEY))); + bucket_cur %= self->n_buckets; + state->sort_fn = self->common.sort_fn; + } else { + /* don't know, let's scan all buckets */ + bucket_cur = -1; + state->sort_fn = (flags & OBJ_PARTIAL_KEY) ? self->common.sort_fn : NULL; + } + + if (state->descending) { + /* + * Determine the search boundaries of a descending traversal. + * + * bucket_cur downto state->bucket_last + */ + if (bucket_cur < 0) { + bucket_cur = self->n_buckets - 1; + state->bucket_last = 0; + } else { + state->bucket_last = bucket_cur; + } + if (flags & OBJ_CONTINUE) { + state->bucket_last = 0; + if (state->sort_fn) { + state->recheck_starting_bucket = 1; + } + } + state->bucket_start = bucket_cur; + + /* For each bucket */ + for (; state->bucket_last <= bucket_cur; --bucket_cur) { + /* For each node in the bucket. */ + for (node = AST_DLLIST_LAST(&self->buckets[bucket_cur].list); + node; + node = AST_DLLIST_PREV(node, links)) { + if (!node->common.obj) { + /* Node is empty */ + continue; + } + + if (state->sort_fn) { + /* Filter node through the sort_fn */ + cmp = state->sort_fn(node->common.obj, arg, + flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY)); + if (cmp > 0) { + continue; + } + if (flags & OBJ_CONTINUE) { + /* Remember first node when we wrap around. */ + __ao2_ref(node, +1); + state->first_node = node; + + /* From now on all nodes are matching */ + state->sort_fn = NULL; + } else if (cmp < 0) { + /* No more nodes in this bucket are possible to match. */ + break; + } + } + + /* We have the first traversal node */ + __ao2_ref(node, +1); + return node; + } + + /* Was this the starting bucket? */ + if (bucket_cur == state->bucket_start + && (flags & OBJ_CONTINUE) + && (flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY))) { + /* In case the bucket was empty or none of the nodes matched. */ + state->sort_fn = NULL; + } + + /* Was this the first container bucket? */ + if (bucket_cur == 0 + && (flags & OBJ_CONTINUE) + && (flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY))) { + /* Move to the end to ensure we check every bucket */ + bucket_cur = self->n_buckets; + state->bucket_last = state->bucket_start + 1; + if (state->recheck_starting_bucket) { + /* + * We have to recheck the first part of the starting bucket + * because of sorting skips. + */ + state->recheck_starting_bucket = 0; + --state->bucket_last; + } + } + } + } else { + /* + * Determine the search boundaries of an ascending traversal. + * + * bucket_cur to state->bucket_last-1 + */ + if (bucket_cur < 0) { + bucket_cur = 0; + state->bucket_last = self->n_buckets; + } else { + state->bucket_last = bucket_cur + 1; + } + if (flags & OBJ_CONTINUE) { + state->bucket_last = self->n_buckets; + if (state->sort_fn) { + state->recheck_starting_bucket = 1; + } + } + state->bucket_start = bucket_cur; + + /* For each bucket */ + for (; bucket_cur < state->bucket_last; ++bucket_cur) { + /* For each node in the bucket. */ + for (node = AST_DLLIST_FIRST(&self->buckets[bucket_cur].list); + node; + node = AST_DLLIST_NEXT(node, links)) { + if (!node->common.obj) { + /* Node is empty */ + continue; + } + + if (state->sort_fn) { + /* Filter node through the sort_fn */ + cmp = state->sort_fn(node->common.obj, arg, + flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY)); + if (cmp < 0) { + continue; + } + if (flags & OBJ_CONTINUE) { + /* Remember first node when we wrap around. */ + __ao2_ref(node, +1); + state->first_node = node; + + /* From now on all nodes are matching */ + state->sort_fn = NULL; + } else if (cmp > 0) { + /* No more nodes in this bucket are possible to match. */ + break; + } + } + + /* We have the first traversal node */ + __ao2_ref(node, +1); + return node; + } + + /* Was this the starting bucket? */ + if (bucket_cur == state->bucket_start + && (flags & OBJ_CONTINUE) + && (flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY))) { + /* In case the bucket was empty or none of the nodes matched. */ + state->sort_fn = NULL; + } + + /* Was this the last container bucket? */ + if (bucket_cur == self->n_buckets - 1 + && (flags & OBJ_CONTINUE) + && (flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY))) { + /* Move to the beginning to ensure we check every bucket */ + bucket_cur = -1; + state->bucket_last = state->bucket_start; + if (state->recheck_starting_bucket) { + /* + * We have to recheck the first part of the starting bucket + * because of sorting skips. + */ + state->recheck_starting_bucket = 0; + ++state->bucket_last; + } + } + } + } + + return NULL; +} + +/*! + * \internal + * \brief Find the next hash container node in a traversal. + * \since 12.0.0 + * + * \param self Container to operate upon. + * \param state Traversal state to restart hash container traversal. + * \param prev Previous node returned by the traversal search functions. + * The ref ownership is passed back to this function. + * + * \retval node-ptr of found node (Reffed). + * \retval NULL when no node found. + */ +static struct hash_bucket_node *hash_ao2_find_next(struct ao2_container_hash *self, struct hash_traversal_state *state, struct hash_bucket_node *prev) +{ + struct hash_bucket_node *node; + void *arg; + enum search_flags flags; + int bucket_cur; + int cmp; + + arg = state->arg; + flags = state->flags; + bucket_cur = prev->my_bucket; + node = prev; + + /* + * This function is structured the same as hash_ao2_find_first() + * intentionally. We are resuming the search loops from + * hash_ao2_find_first() in order to find the next node. The + * search loops must be resumed where hash_ao2_find_first() + * returned with the first node. + */ + if (state->descending) { + goto hash_descending_resume; + + /* For each bucket */ + for (; state->bucket_last <= bucket_cur; --bucket_cur) { + /* For each node in the bucket. */ + for (node = AST_DLLIST_LAST(&self->buckets[bucket_cur].list); + node; + node = AST_DLLIST_PREV(node, links)) { + if (node == state->first_node) { + /* We have wrapped back to the starting point. */ + __ao2_ref(prev, -1); + return NULL; + } + if (!node->common.obj) { + /* Node is empty */ + continue; + } + + if (state->sort_fn) { + /* Filter node through the sort_fn */ + cmp = state->sort_fn(node->common.obj, arg, + flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY)); + if (cmp > 0) { + continue; + } + if (cmp < 0) { + /* No more nodes in this bucket are possible to match. */ + break; + } + } + + /* We have the next traversal node */ + __ao2_ref(node, +1); + + /* + * Dereferencing the prev node may result in our next node + * object being removed by another thread. This could happen if + * the container uses RW locks and the container was read + * locked. + */ + __ao2_ref(prev, -1); + if (node->common.obj) { + return node; + } + prev = node; + +hash_descending_resume:; + } + + /* Was this the first container bucket? */ + if (bucket_cur == 0 + && (flags & OBJ_CONTINUE) + && (flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY))) { + /* Move to the end to ensure we check every bucket */ + bucket_cur = self->n_buckets; + state->bucket_last = state->bucket_start + 1; + if (state->recheck_starting_bucket) { + /* + * We have to recheck the first part of the starting bucket + * because of sorting skips. + */ + state->recheck_starting_bucket = 0; + --state->bucket_last; + } + } + } + } else { + goto hash_ascending_resume; + + /* For each bucket */ + for (; bucket_cur < state->bucket_last; ++bucket_cur) { + /* For each node in the bucket. */ + for (node = AST_DLLIST_FIRST(&self->buckets[bucket_cur].list); + node; + node = AST_DLLIST_NEXT(node, links)) { + if (node == state->first_node) { + /* We have wrapped back to the starting point. */ + __ao2_ref(prev, -1); + return NULL; + } + if (!node->common.obj) { + /* Node is empty */ + continue; + } + + if (state->sort_fn) { + /* Filter node through the sort_fn */ + cmp = state->sort_fn(node->common.obj, arg, + flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY)); + if (cmp < 0) { + continue; + } + if (cmp > 0) { + /* No more nodes in this bucket are possible to match. */ + break; + } + } + + /* We have the next traversal node */ + __ao2_ref(node, +1); + + /* + * Dereferencing the prev node may result in our next node + * object being removed by another thread. This could happen if + * the container uses RW locks and the container was read + * locked. + */ + __ao2_ref(prev, -1); + if (node->common.obj) { + return node; + } + prev = node; + +hash_ascending_resume:; + } + + /* Was this the last container bucket? */ + if (bucket_cur == self->n_buckets - 1 + && (flags & OBJ_CONTINUE) + && (flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY))) { + /* Move to the beginning to ensure we check every bucket */ + bucket_cur = -1; + state->bucket_last = state->bucket_start; + if (state->recheck_starting_bucket) { + /* + * We have to recheck the first part of the starting bucket + * because of sorting skips. + */ + state->recheck_starting_bucket = 0; + ++state->bucket_last; + } + } + } + } + + /* No more nodes in the container left to traverse. */ + __ao2_ref(prev, -1); + return NULL; +} + +/*! + * \internal + * \brief Cleanup the hash container traversal state. + * \since 12.0.0 + * + * \param state Traversal state to cleanup. + * + * \return Nothing + */ +static void hash_ao2_find_cleanup(struct hash_traversal_state *state) +{ + if (state->first_node) { + __ao2_ref(state->first_node, -1); + } +} + +/*! + * \internal + * \brief Find the next non-empty iteration node in the container. + * \since 12.0.0 + * + * \param self Container to operate upon. + * \param node Previous node returned by the iterator. + * \param flags search_flags to control iterating the container. + * Only AO2_ITERATOR_DESCENDING is useful by the method. + * + * \note The container is already locked. + * + * \retval node on success. + * \retval NULL on error or no more nodes in the container. + */ +static struct hash_bucket_node *hash_ao2_iterator_next(struct ao2_container_hash *self, struct hash_bucket_node *node, enum ao2_iterator_flags flags) +{ + int cur_bucket; + + if (flags & AO2_ITERATOR_DESCENDING) { + if (node) { + cur_bucket = node->my_bucket; + + /* Find next non-empty node. */ + for (;;) { + node = AST_DLLIST_PREV(node, links); + if (!node) { + break; + } + if (node->common.obj) { + /* Found a non-empty node. */ + return node; + } + } + } else { + /* Find first non-empty node. */ + cur_bucket = self->n_buckets; + } + + /* Find a non-empty node in the remaining buckets */ + while (0 <= --cur_bucket) { + node = AST_DLLIST_LAST(&self->buckets[cur_bucket].list); + while (node) { + if (node->common.obj) { + /* Found a non-empty node. */ + return node; + } + node = AST_DLLIST_PREV(node, links); + } + } + } else { + if (node) { + cur_bucket = node->my_bucket; + + /* Find next non-empty node. */ + for (;;) { + node = AST_DLLIST_NEXT(node, links); + if (!node) { + break; + } + if (node->common.obj) { + /* Found a non-empty node. */ + return node; + } + } + } else { + /* Find first non-empty node. */ + cur_bucket = -1; + } + + /* Find a non-empty node in the remaining buckets */ + while (++cur_bucket < self->n_buckets) { + node = AST_DLLIST_FIRST(&self->buckets[cur_bucket].list); + while (node) { + if (node->common.obj) { + /* Found a non-empty node. */ + return node; + } + node = AST_DLLIST_NEXT(node, links); + } + } + } + + /* No more nodes to visit in the container. */ + return NULL; +} + +#if defined(AST_DEVMODE) +/*! + * \internal + * \brief Increment the hash container linked object statistic. + * \since 12.0.0 + * + * \param hash Container to operate upon. + * \param hash_node Container node linking object to. + * + * \return Nothing + */ +static void hash_ao2_link_node_stat(struct ao2_container *hash, struct ao2_container_node *hash_node) +{ + struct ao2_container_hash *self = (struct ao2_container_hash *) hash; + struct hash_bucket_node *node = (struct hash_bucket_node *) hash_node; + int i = node->my_bucket; + + ++self->buckets[i].elements; + if (self->buckets[i].max_elements < self->buckets[i].elements) { + self->buckets[i].max_elements = self->buckets[i].elements; + } +} +#endif /* defined(AST_DEVMODE) */ + +#if defined(AST_DEVMODE) +/*! + * \internal + * \brief Decrement the hash container linked object statistic. + * \since 12.0.0 + * + * \param hash Container to operate upon. + * \param hash_node Container node unlinking object from. + * + * \return Nothing + */ +static void hash_ao2_unlink_node_stat(struct ao2_container *hash, struct ao2_container_node *hash_node) +{ + struct ao2_container_hash *self = (struct ao2_container_hash *) hash; + struct hash_bucket_node *node = (struct hash_bucket_node *) hash_node; + + --self->buckets[node->my_bucket].elements; +} +#endif /* defined(AST_DEVMODE) */ + +/*! + * \internal + * + * \brief Destroy this container. + * \since 12.0.0 + * + * \param self Container to operate upon. + * + * \return Nothing + */ +static void hash_ao2_destroy(struct ao2_container_hash *self) +{ + int idx; + + /* Check that the container no longer has any nodes */ + for (idx = self->n_buckets; idx--;) { + if (!AST_DLLIST_EMPTY(&self->buckets[idx].list)) { + ast_log(LOG_ERROR, "Node ref leak. Hash container still has nodes!\n"); + ast_assert(0); + break; + } + } +} + +#if defined(AST_DEVMODE) +/*! + * \internal + * \brief Display statistics of the specified container. + * \since 12.0.0 + * + * \param self Container to display statistics. + * \param fd File descriptor to send output. + * \param prnt Print output callback function to use. + * + * \note The container is already locked for reading. + * + * \return Nothing + */ +static void hash_ao2_stats(struct ao2_container_hash *self, int fd, void (*prnt)(int fd, const char *fmt, ...) __attribute__((format(printf, 2, 3)))) +{ +#define FORMAT "%10.10s %10.10s %10.10s\n" +#define FORMAT2 "%10d %10d %10d\n" + + int bucket; + int suppressed_buckets = 0; + + prnt(fd, "Number of buckets: %d\n\n", self->n_buckets); + + prnt(fd, FORMAT, "Bucket", "Objects", "Max"); + for (bucket = 0; bucket < self->n_buckets; ++bucket) { + if (self->buckets[bucket].max_elements) { + prnt(fd, FORMAT2, bucket, self->buckets[bucket].elements, + self->buckets[bucket].max_elements); + suppressed_buckets = 0; + } else if (!suppressed_buckets) { + suppressed_buckets = 1; + prnt(fd, "...\n"); + } + } + +#undef FORMAT +#undef FORMAT2 +} +#endif /* defined(AST_DEVMODE) */ + +#if defined(AST_DEVMODE) +/*! + * \internal + * \brief Perform an integrity check on the specified container. + * \since 12.0.0 + * + * \param self Container to check integrity. + * + * \note The container is already locked for reading. + * + * \retval 0 on success. + * \retval -1 on error. + */ +static int hash_ao2_integrity(struct ao2_container_hash *self) +{ + int bucket_exp; + int bucket; + int count_obj; + int count_total_obj; + int count_total_node; + void *obj_last; + struct hash_bucket_node *node; + struct hash_bucket_node *prev; + struct hash_bucket_node *next; + + count_total_obj = 0; + count_total_node = 0; + + /* For each bucket in the container. */ + for (bucket = 0; bucket < self->n_buckets; ++bucket) { + if (!AST_DLLIST_FIRST(&self->buckets[bucket].list) + && !AST_DLLIST_LAST(&self->buckets[bucket].list)) { + /* The bucket list is empty. */ + continue; + } + + count_obj = 0; + obj_last = NULL; + + /* Check bucket list links and nodes. */ + node = AST_DLLIST_LAST(&self->buckets[bucket].list); + if (!node) { + ast_log(LOG_ERROR, "Bucket %d list tail is NULL when it should not be!\n", + bucket); + return -1; + } + if (AST_DLLIST_NEXT(node, links)) { + ast_log(LOG_ERROR, "Bucket %d list tail node is not the last node!\n", + bucket); + return -1; + } + node = AST_DLLIST_FIRST(&self->buckets[bucket].list); + if (!node) { + ast_log(LOG_ERROR, "Bucket %d list head is NULL when it should not be!\n", + bucket); + return -1; + } + if (AST_DLLIST_PREV(node, links)) { + ast_log(LOG_ERROR, "Bucket %d list head node is not the first node!\n", + bucket); + return -1; + } + for (; node; node = next) { + /* Check backward link. */ + prev = AST_DLLIST_PREV(node, links); + if (prev) { + if (node != AST_DLLIST_NEXT(prev, links)) { + ast_log(LOG_ERROR, "Bucket %d list node's prev node does not link back!\n", + bucket); + return -1; + } + } else if (node != AST_DLLIST_FIRST(&self->buckets[bucket].list)) { + ast_log(LOG_ERROR, "Bucket %d backward list chain is broken!\n", + bucket); + return -1; + } + + /* Check forward link. */ + next = AST_DLLIST_NEXT(node, links); + if (next) { + if (node != AST_DLLIST_PREV(next, links)) { + ast_log(LOG_ERROR, "Bucket %d list node's next node does not link back!\n", + bucket); + return -1; + } + } else if (node != AST_DLLIST_LAST(&self->buckets[bucket].list)) { + ast_log(LOG_ERROR, "Bucket %d forward list chain is broken!\n", + bucket); + return -1; + } + + if (bucket != node->my_bucket) { + ast_log(LOG_ERROR, "Bucket %d node claims to be in bucket %d!\n", + bucket, node->my_bucket); + return -1; + } + + ++count_total_node; + if (!node->common.obj) { + /* Node is empty. */ + continue; + } + ++count_obj; + + /* Check container hash key for expected bucket. */ + bucket_exp = abs(self->hash_fn(node->common.obj, OBJ_POINTER)); + bucket_exp %= self->n_buckets; + if (bucket != bucket_exp) { + ast_log(LOG_ERROR, "Bucket %d node hashes to bucket %d!\n", + bucket, bucket_exp); + return -1; + } + + /* Check sort if configured. */ + if (self->common.sort_fn) { + if (obj_last + && self->common.sort_fn(obj_last, node->common.obj, OBJ_POINTER) > 0) { + ast_log(LOG_ERROR, "Bucket %d nodes out of sorted order!\n", + bucket); + return -1; + } + obj_last = node->common.obj; + } + } + + /* Check bucket obj count statistic. */ + if (count_obj != self->buckets[bucket].elements) { + ast_log(LOG_ERROR, "Bucket %d object count of %d does not match stat of %d!\n", + bucket, count_obj, self->buckets[bucket].elements); + return -1; + } + + /* Accumulate found object counts. */ + count_total_obj += count_obj; } + + /* Check total obj count. */ + if (count_total_obj != ao2_container_count(&self->common)) { + ast_log(LOG_ERROR, + "Total object count of %d does not match ao2_container_count() of %d!\n", + count_total_obj, ao2_container_count(&self->common)); + return -1; + } + + /* Check total node count. */ + if (count_total_node != self->common.nodes) { + ast_log(LOG_ERROR, "Total node count of %d does not match stat of %d!\n", + count_total_node, self->common.nodes); + return -1; + } + + return 0; +} +#endif /* defined(AST_DEVMODE) */ + +/*! Hash container virtual method table. */ +static const struct ao2_container_methods v_table_hash = { + .type = AO2_CONTAINER_RTTI_HASH, + .alloc_empty_clone = (ao2_container_alloc_empty_clone_fn) hash_ao2_alloc_empty_clone, + .alloc_empty_clone_debug = + (ao2_container_alloc_empty_clone_debug_fn) hash_ao2_alloc_empty_clone_debug, + .new_node = (ao2_container_new_node_fn) hash_ao2_new_node, + .insert = (ao2_container_insert_fn) hash_ao2_insert_node, + .traverse_first = (ao2_container_find_first_fn) hash_ao2_find_first, + .traverse_next = (ao2_container_find_next_fn) hash_ao2_find_next, + .traverse_cleanup = (ao2_container_find_cleanup_fn) hash_ao2_find_cleanup, + .iterator_next = (ao2_iterator_next_fn) hash_ao2_iterator_next, + .destroy = (ao2_container_destroy_fn) hash_ao2_destroy, +#if defined(AST_DEVMODE) + .stats = (ao2_container_statistics) hash_ao2_stats, + .integrity = (ao2_container_integrity) hash_ao2_integrity, +#endif /* defined(AST_DEVMODE) */ +}; + +/*! + * \brief always zero hash function + * + * it is convenient to have a hash function that always returns 0. + * This is basically used when we want to have a container that is + * a simple linked list. + * + * \returns 0 + */ +static int hash_zero(const void *user_obj, const int flags) +{ + return 0; +} + +/*! + * \brief Initialize a hash container with the desired number of buckets. + * + * \param self Container to initialize. + * \param options Container behaviour options (See enum ao2_container_opts) + * \param n_buckets Number of buckets for hash + * \param hash_fn Pointer to a function computing a hash value. + * \param sort_fn Pointer to a sort function. + * \param cmp_fn Pointer to a compare function used by ao2_find. + * + * \return A pointer to a struct container. + */ +static struct ao2_container *hash_ao2_container_init( + struct ao2_container_hash *self, unsigned int options, unsigned int n_buckets, + ao2_hash_fn *hash_fn, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn) +{ + if (!self) { + return NULL; + } + + self->common.v_table = &v_table_hash; + self->common.sort_fn = sort_fn; + self->common.cmp_fn = cmp_fn; + self->common.options = options; + self->hash_fn = hash_fn ? hash_fn : hash_zero; + self->n_buckets = n_buckets; + +#ifdef AO2_DEBUG + ast_atomic_fetchadd_int(&ao2.total_containers, 1); +#endif + + return (struct ao2_container *) self; +} + +struct ao2_container *__ao2_container_alloc_hash(unsigned int ao2_options, + unsigned int container_options, unsigned int n_buckets, ao2_hash_fn *hash_fn, + ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn) +{ + unsigned int num_buckets; + size_t container_size; + struct ao2_container_hash *self; + + num_buckets = hash_fn ? n_buckets : 1; + container_size = sizeof(struct ao2_container_hash) + num_buckets * sizeof(struct hash_bucket); + + self = __ao2_alloc(container_size, container_destruct, ao2_options); + return hash_ao2_container_init(self, container_options, num_buckets, + hash_fn, sort_fn, cmp_fn); +} + +struct ao2_container *__ao2_container_alloc_hash_debug(unsigned int ao2_options, + unsigned int container_options, unsigned int n_buckets, ao2_hash_fn *hash_fn, + ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn, + const char *tag, const char *file, int line, const char *func, int ref_debug) +{ + unsigned int num_buckets; + size_t container_size; + struct ao2_container_hash *self; + + num_buckets = hash_fn ? n_buckets : 1; + container_size = sizeof(struct ao2_container_hash) + num_buckets * sizeof(struct hash_bucket); + + self = __ao2_alloc_debug(container_size, container_destruct_debug, ao2_options, + tag, file, line, func, ref_debug); + return hash_ao2_container_init(self, container_options, num_buckets, hash_fn, + sort_fn, cmp_fn); +} + +struct ao2_container *__ao2_container_alloc_list(unsigned int ao2_options, + unsigned int container_options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn) +{ + return __ao2_container_alloc_hash(ao2_options, container_options, 1, NULL, sort_fn, + cmp_fn); +} + +struct ao2_container *__ao2_container_alloc_list_debug(unsigned int ao2_options, + unsigned int container_options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn, + const char *tag, const char *file, int line, const char *func, int ref_debug) +{ + return __ao2_container_alloc_hash_debug(ao2_options, container_options, 1, NULL, + sort_fn, cmp_fn, tag, file, line, func, ref_debug); } #ifdef AO2_DEBUG @@ -1591,7 +3061,7 @@ static char *handle_astobj2_test(struct ast_cli_entry *e, int cmd, struct ast_cl e->command = "astobj2 test"; e->usage = "Usage: astobj2 test <num>\n" " Runs astobj2 test. Creates 'num' objects,\n" - " and test iterators, callbacks and may be other stuff\n"; + " and test iterators, callbacks and maybe other stuff\n"; return NULL; case CLI_GENERATE: return NULL; @@ -1610,10 +3080,10 @@ static char *handle_astobj2_test(struct ast_cli_entry *e, int cmd, struct ast_cl handle_astobj2_stats(e, CLI_HANDLER, &fake_args); /* - * allocate a container with no default callback, and no hash function. - * No hash means everything goes in the same bucket. + * Allocate a list container. */ - c1 = ao2_t_container_alloc(100, NULL /* no callback */, NULL /* no hash */,"test"); + c1 = ao2_t_container_alloc_list(AO2_ALLOC_OPT_LOCK_MUTEX, 0, NULL /* no sort */, + NULL /* no callback */, "test"); ast_cli(a->fd, "container allocated as %p\n", c1); /* @@ -1671,7 +3141,7 @@ static char *handle_astobj2_test(struct ast_cli_entry *e, int cmd, struct ast_cl ast_cli(a->fd, "testing callbacks again\n"); ao2_t_callback(c1, 0, print_cb, a, "test callback"); - ast_verbose("now you should see an error message:\n"); + ast_verbose("now you should see an error and possible assertion failure messages:\n"); ao2_t_ref(&i, -1, ""); /* i is not a valid object so we print an error here */ ast_cli(a->fd, "destroy container\n"); @@ -1680,18 +3150,232 @@ static char *handle_astobj2_test(struct ast_cli_entry *e, int cmd, struct ast_cl handle_astobj2_stats(e, CLI_HANDLER, &fake_args); return CLI_SUCCESS; } +#endif /* AO2_DEBUG */ + +#if defined(AST_DEVMODE) +static struct ao2_container *reg_containers; + +struct ao2_reg_container { + /*! Registered container pointer. */ + struct ao2_container *registered; + /*! Name container registered under. */ + char name[1]; +}; + +struct ao2_reg_partial_key { + /*! Length of partial key match. */ + int len; + /*! Registration partial key name. */ + const char *name; +}; + +struct ao2_reg_match { + /*! The nth match to find. */ + int find_nth; + /*! Count of the matches already found. */ + int count; +}; +#endif /* defined(AST_DEVMODE) */ + +#if defined(AST_DEVMODE) +static int ao2_reg_sort_cb(const void *obj_left, const void *obj_right, int flags) +{ + const struct ao2_reg_container *reg_left = obj_left; + int cmp; + + if (flags & OBJ_KEY) { + const char *name = obj_right; + + cmp = strcasecmp(reg_left->name, name); + } else if (flags & OBJ_PARTIAL_KEY) { + const struct ao2_reg_partial_key *partial_key = obj_right; + + cmp = strncasecmp(reg_left->name, partial_key->name, partial_key->len); + } else { + const struct ao2_reg_container *reg_right = obj_right; + + cmp = strcasecmp(reg_left->name, reg_right->name); + } + return cmp; +} +#endif /* defined(AST_DEVMODE) */ + +#if defined(AST_DEVMODE) +static void ao2_reg_destructor(void *v_doomed) +{ + struct ao2_reg_container *doomed = v_doomed; + + if (doomed->registered) { + ao2_ref(doomed->registered, -1); + } +} +#endif /* defined(AST_DEVMODE) */ + +int ao2_container_register(const char *name, struct ao2_container *self) +{ + int res = 0; +#if defined(AST_DEVMODE) + struct ao2_reg_container *reg; + + reg = ao2_alloc_options(sizeof(*reg) + strlen(name), ao2_reg_destructor, + AO2_ALLOC_OPT_LOCK_NOLOCK); + if (!reg) { + return -1; + } + + /* Fill in registered entry */ + ao2_ref(self, +1); + reg->registered = self; + strcpy(reg->name, name);/* safe */ + + if (!ao2_link(reg_containers, reg)) { + res = -1; + } + + ao2_ref(reg, -1); +#endif /* defined(AST_DEVMODE) */ + return res; +} + +void ao2_container_unregister(const char *name) +{ +#if defined(AST_DEVMODE) + ao2_find(reg_containers, name, OBJ_UNLINK | OBJ_NODATA | OBJ_KEY); +#endif /* defined(AST_DEVMODE) */ +} + +#if defined(AST_DEVMODE) +static int ao2_complete_reg_cb(void *obj, void *arg, void *data, int flags) +{ + struct ao2_reg_match *which = data; + + /* ao2_reg_sort_cb() has already filtered the search to matching keys */ + return (which->find_nth < ++which->count) ? (CMP_MATCH | CMP_STOP) : 0; +} +#endif /* defined(AST_DEVMODE) */ + +#if defined(AST_DEVMODE) +static char *complete_container_names(struct ast_cli_args *a) +{ + struct ao2_reg_partial_key partial_key; + struct ao2_reg_match which; + struct ao2_reg_container *reg; + char *name; + + if (a->pos != 3) { + return NULL; + } + + partial_key.len = strlen(a->word); + partial_key.name = a->word; + which.find_nth = a->n; + which.count = 0; + reg = ao2_callback_data(reg_containers, partial_key.len ? OBJ_PARTIAL_KEY : 0, + ao2_complete_reg_cb, &partial_key, &which); + if (reg) { + name = ast_strdup(reg->name); + ao2_ref(reg, -1); + } else { + name = NULL; + } + return name; +} +#endif /* defined(AST_DEVMODE) */ + +#if defined(AST_DEVMODE) +/*! \brief Show container statistics - CLI command */ +static char *handle_cli_astobj2_container_stats(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a) +{ + const char *name; + struct ao2_reg_container *reg; + + switch (cmd) { + case CLI_INIT: + e->command = "astobj2 container stats"; + e->usage = + "Usage: astobj2 container stats <name>\n" + " Show statistics about the specified container <name>.\n"; + return NULL; + case CLI_GENERATE: + return complete_container_names(a); + } + + if (a->argc != 4) { + return CLI_SHOWUSAGE; + } + + name = a->argv[3]; + reg = ao2_find(reg_containers, name, OBJ_KEY); + if (reg) { + ao2_container_stats(reg->registered, a->fd, ast_cli); + ao2_ref(reg, -1); + } else { + ast_cli(a->fd, "Container '%s' not found.\n", name); + } + + return CLI_SUCCESS; +} +#endif /* defined(AST_DEVMODE) */ + +#if defined(AST_DEVMODE) +/*! \brief Show container check results - CLI command */ +static char *handle_cli_astobj2_container_check(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a) +{ + const char *name; + struct ao2_reg_container *reg; + + switch (cmd) { + case CLI_INIT: + e->command = "astobj2 container check"; + e->usage = + "Usage: astobj2 container check <name>\n" + " Perform a container integrity check on <name>.\n"; + return NULL; + case CLI_GENERATE: + return complete_container_names(a); + } + + if (a->argc != 4) { + return CLI_SHOWUSAGE; + } + + name = a->argv[3]; + reg = ao2_find(reg_containers, name, OBJ_KEY); + if (reg) { + ast_cli(a->fd, "Container check of '%s': %s.\n", name, + ao2_container_check(reg->registered, 0) ? "failed" : "OK"); + ao2_ref(reg, -1); + } else { + ast_cli(a->fd, "Container '%s' not found.\n", name); + } + + return CLI_SUCCESS; +} +#endif /* defined(AST_DEVMODE) */ +#if defined(AO2_DEBUG) || defined(AST_DEVMODE) static struct ast_cli_entry cli_astobj2[] = { +#if defined(AO2_DEBUG) AST_CLI_DEFINE(handle_astobj2_stats, "Print astobj2 statistics"), AST_CLI_DEFINE(handle_astobj2_test, "Test astobj2"), +#endif /* defined(AO2_DEBUG) */ +#if defined(AST_DEVMODE) + AST_CLI_DEFINE(handle_cli_astobj2_container_stats, "Show container statistics"), + AST_CLI_DEFINE(handle_cli_astobj2_container_check, "Perform a container integrity check"), +#endif /* defined(AST_DEVMODE) */ }; -#endif /* AO2_DEBUG */ +#endif /* defined(AO2_DEBUG) || defined(AST_DEVMODE) */ + int astobj2_init(void) { -#ifdef AO2_DEBUG +#if defined(AST_DEVMODE) + reg_containers = ao2_container_alloc_list(AO2_ALLOC_OPT_LOCK_RWLOCK, + AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE, ao2_reg_sort_cb, NULL); +#endif /* defined(AST_DEVMODE) */ +#if defined(AO2_DEBUG) || defined(AST_DEVMODE) ast_cli_register_multiple(cli_astobj2, ARRAY_LEN(cli_astobj2)); -#endif +#endif /* defined(AO2_DEBUG) || defined(AST_DEVMODE) */ return 0; } diff --git a/main/channel.c b/main/channel.c index 0faf165f1..d62f34239 100644 --- a/main/channel.c +++ b/main/channel.c @@ -8508,6 +8508,9 @@ void ast_channels_init(void) { channels = ao2_container_alloc(NUM_CHANNEL_BUCKETS, ast_channel_hash_cb, ast_channel_cmp_cb); + if (channels) { + ao2_container_register("channels", channels); + } ast_cli_register_multiple(cli_channel, ARRAY_LEN(cli_channel)); diff --git a/tests/test_astobj2.c b/tests/test_astobj2.c index 275c260af..95d7e753d 100644 --- a/tests/test_astobj2.c +++ b/tests/test_astobj2.c @@ -37,15 +37,59 @@ ASTERISK_FILE_VERSION(__FILE__, "$Revision$") #include "asterisk/test.h" #include "asterisk/astobj2.h" +enum test_container_type { + TEST_CONTAINER_LIST, + TEST_CONTAINER_HASH, +}; + +/*! + * \internal + * \brief Convert the container type enum to string. + * \since 12.0.0 + * + * \param type Container type value to convert to string. + * + * \return String value of container type. + */ +static const char *test_container2str(enum test_container_type type) +{ + const char *c_type; + + c_type = "Unknown"; + switch (type) { + case TEST_CONTAINER_LIST: + c_type = "List"; + break; + case TEST_CONTAINER_HASH: + c_type = "Hash"; + break; + } + return c_type; +} + struct test_obj { - int i; + /*! What to decrement when object is destroyed. */ int *destructor_count; + /*! Container object key */ + int i; + /*! Identifier for duplicate object key tests. */ + int dup_number; }; -static void test_obj_destructor(void *obj) +/*! Partial search key +/- matching range. */ +int partial_key_match_range; +/*! Special iax2 OBJ_CONTINUE test. Bucket selected. */ +int special_bucket; +/*! Special iax2 OBJ_CONTINUE test. Object number select. */ +int special_match; + +static void test_obj_destructor(void *v_obj) { - struct test_obj *test_obj = (struct test_obj *) obj; - *test_obj->destructor_count = *test_obj->destructor_count - 1; + struct test_obj *obj = (struct test_obj *) v_obj; + + if (obj->destructor_count) { + --*obj->destructor_count; + } } static int increment_cb(void *obj, void *arg, int flag) @@ -58,124 +102,140 @@ static int increment_cb(void *obj, void *arg, int flag) static int all_but_one_cb(void *obj, void *arg, int flag) { - struct test_obj *test_obj = (struct test_obj *) obj; + struct test_obj *cmp_obj = (struct test_obj *) obj; - return (test_obj->i > 1) ? CMP_MATCH : 0; + return (cmp_obj->i) ? CMP_MATCH : 0; } static int multiple_cb(void *obj, void *arg, int flag) { int *i = (int *) arg; - struct test_obj *test_obj = (struct test_obj *) obj; + struct test_obj *cmp_obj = (struct test_obj *) obj; - return (test_obj->i <= *i) ? CMP_MATCH : 0; + return (cmp_obj->i < *i) ? CMP_MATCH : 0; } static int test_cmp_cb(void *obj, void *arg, int flags) { struct test_obj *cmp_obj = (struct test_obj *) obj; - if (!arg) { - return 0; - } - if (flags & OBJ_KEY) { int *i = (int *) arg; - return (cmp_obj->i == *i) ? CMP_MATCH | CMP_STOP : 0; + + return (cmp_obj->i == *i) ? CMP_MATCH : 0; + } else if (flags & OBJ_PARTIAL_KEY) { + int *i = (int *) arg; + + return (*i - partial_key_match_range <= cmp_obj->i + && cmp_obj->i <= *i + partial_key_match_range) ? CMP_MATCH : 0; } else { - struct test_obj *test_obj = (struct test_obj *) arg; - return (cmp_obj->i == test_obj->i) ? CMP_MATCH | CMP_STOP : 0; + struct test_obj *arg_obj = (struct test_obj *) arg; + + if (!arg_obj) { + /* Never match on the special iax2 OBJ_CONTINUE test. */ + return 0; + } + + return (cmp_obj->i == arg_obj->i) ? CMP_MATCH : 0; } } static int test_hash_cb(const void *obj, const int flags) { - if (!obj) { - return 0; - } - if (flags & OBJ_KEY) { const int *i = obj; return *i; + } else if (flags & OBJ_PARTIAL_KEY) { + /* This is absolutely wrong to be called with this flag value. */ + abort(); + /* Just in case abort() doesn't work or something else super silly */ + *((int *) 0) = 0; + return 0; } else { - const struct test_obj *test_obj = obj; + const struct test_obj *hash_obj = obj; - return test_obj->i; + if (!hash_obj) { + /* + * Use the special_bucket as the bucket for the special iax2 + * OBJ_CONTINUE test. + */ + return special_bucket; + } + + return hash_obj->i; } } -static int astobj2_test_helper(int use_hash, int use_cmp, unsigned int lim, struct ast_test *test) +static int test_sort_cb(const void *obj_left, const void *obj_right, int flags) { - struct ao2_container *c1; - struct ao2_container *c2; - struct ao2_container *c3 = NULL; - struct ao2_iterator it; - struct ao2_iterator *mult_it; - struct test_obj *obj; - struct test_obj *obj2; - struct test_obj tmp_obj; - int bucket_size; - int increment = 0; - int destructor_count = 0; - int num; - int res = AST_TEST_PASS; - - /* This test needs at least 5 objects */ - if (lim < 5) { - lim = 5; - } + const struct test_obj *test_left = obj_left; - bucket_size = (ast_random() % ((lim / 4) + 1)) + 1; - c1 = ao2_t_container_alloc(bucket_size, use_hash ? test_hash_cb : NULL, use_cmp ? test_cmp_cb : NULL, "test"); - c2 = ao2_t_container_alloc(bucket_size, test_hash_cb, test_cmp_cb, "test"); + if (flags & OBJ_KEY) { + const int *i = obj_right; - if (!c1 || !c2) { - ast_test_status_update(test, "ao2_container_alloc failed.\n"); - res = AST_TEST_FAIL; - goto cleanup; - } + return test_left->i - *i; + } else if (flags & OBJ_PARTIAL_KEY) { + int *i = (int *) obj_right; - /* Create objects and link into container */ - destructor_count = lim; - for (num = 1; num <= lim; num++) { - if (!(obj = ao2_t_alloc(sizeof(struct test_obj), test_obj_destructor, "making zombies"))) { - ast_test_status_update(test, "ao2_alloc failed.\n"); - res = AST_TEST_FAIL; - goto cleanup; + if (*i - partial_key_match_range <= test_left->i + && test_left->i <= *i + partial_key_match_range) { + return 0; } - obj->destructor_count = &destructor_count; - obj->i = num; - ao2_link(c1, obj); - ao2_t_ref(obj, -1, "test"); - if (ao2_container_count(c1) != num) { - ast_test_status_update(test, "container did not link correctly\n"); - res = AST_TEST_FAIL; + + return test_left->i - *i; + } else { + const struct test_obj *test_right = obj_right; + + if (!test_right) { + /* + * Compare with special_match in the special iax2 OBJ_CONTINUE + * test. + */ + return test_left->i - special_match; } + + return test_left->i - test_right->i; } +} - ast_test_status_update(test, "Container created: random bucket size %d: number of items: %d\n", bucket_size, lim); +/*! + * \internal + * \brief Test container cloning. + * \since 12.0.0 + * + * \param res Passed in enum ast_test_result_state. + * \param orig Container to clone. + * \param test Test output controller. + * + * \return enum ast_test_result_state + */ +static int test_container_clone(int res, struct ao2_container *orig, struct ast_test *test) +{ + struct ao2_container *clone; + struct test_obj *obj; + struct test_obj *obj2; + struct ao2_iterator iter; - /* Testing ao2_container_clone */ - c3 = ao2_container_clone(c1, 0); - if (!c3) { + clone = ao2_container_clone(orig, 0); + if (!clone) { ast_test_status_update(test, "ao2_container_clone failed.\n"); - res = AST_TEST_FAIL; - goto cleanup; + return AST_TEST_FAIL; } - if (ao2_container_count(c1) != ao2_container_count(c3)) { + if (ao2_container_check(clone, 0)) { + ast_test_status_update(test, "container integrity check failed\n"); + res = AST_TEST_FAIL; + } else if (ao2_container_count(orig) != ao2_container_count(clone)) { ast_test_status_update(test, "Cloned container does not have the same number of objects.\n"); res = AST_TEST_FAIL; } else { - it = ao2_iterator_init(c1, 0); - for (; (obj = ao2_t_iterator_next(&it, "test orig")); ao2_t_ref(obj, -1, "test orig")) { + iter = ao2_iterator_init(orig, 0); + for (; (obj = ao2_t_iterator_next(&iter, "test orig")); ao2_t_ref(obj, -1, "test orig")) { /* * Unlink the matching object from the cloned container to make * the next search faster. This is a big speed optimization! - * It reduces the container with 100000 objects test time from - * 18 seconds to 200 ms. */ - obj2 = ao2_t_callback(c3, OBJ_POINTER | OBJ_UNLINK, ao2_match_by_addr, obj, + obj2 = ao2_t_callback(clone, OBJ_POINTER | OBJ_UNLINK, ao2_match_by_addr, obj, "test clone"); if (obj2) { ao2_t_ref(obj2, -1, "test clone"); @@ -185,98 +245,366 @@ static int astobj2_test_helper(int use_hash, int use_cmp, unsigned int lim, stru "Orig container has an object %p not in the clone container.\n", obj); res = AST_TEST_FAIL; } - ao2_iterator_destroy(&it); - if (ao2_container_count(c3)) { + ao2_iterator_destroy(&iter); + if (ao2_container_count(clone)) { ast_test_status_update(test, "Cloned container still has objects.\n"); res = AST_TEST_FAIL; } + if (ao2_container_check(clone, 0)) { + ast_test_status_update(test, "container integrity check failed\n"); + res = AST_TEST_FAIL; + } } - ao2_t_ref(c3, -1, "bye c3"); - c3 = NULL; + ao2_t_ref(clone, -1, "bye clone"); + + return res; +} + +/*! + * \internal + * \brief Test ao2_find with no flags. + * \since 12.0.0 + * + * \param res Passed in enum ast_test_result_state. + * \param look_in Container to search. + * \param limit Container contains objects 0 - (limit - 1). + * \param test Test output controller. + * + * \return enum ast_test_result_state + */ +static int test_ao2_find_w_no_flags(int res, struct ao2_container *look_in, int limit, struct ast_test *test) +{ + int i; + int num; + struct test_obj tmp_obj = { 0, }; + struct test_obj *obj; + + for (num = 100; num--;) { + i = ast_random() % limit; /* find a random object */ - /* Testing ao2_find with no flags */ - num = 100; - for (; num; num--) { - int i = (ast_random() % ((lim / 2)) + 1); /* find a random object */ tmp_obj.i = i; - if (!(obj = ao2_find(c1, &tmp_obj, 0))) { - res = AST_TEST_FAIL; + obj = ao2_find(look_in, &tmp_obj, 0); + if (!obj) { ast_test_status_update(test, "COULD NOT FIND:%d, ao2_find() with no flags failed.\n", i); + res = AST_TEST_FAIL; } else { - /* a correct match will only take place when the custom cmp function is used */ - if (use_cmp && obj->i != i) { - ast_test_status_update(test, "object %d does not match object %d\n", obj->i, tmp_obj.i); + if (obj->i != i) { + ast_test_status_update(test, "object %d does not match %d\n", obj->i, i); res = AST_TEST_FAIL; } ao2_t_ref(obj, -1, "test"); } } - /* Testing ao2_find with OBJ_POINTER */ - num = 75; - for (; num; num--) { - int i = (ast_random() % ((lim / 2)) + 1); /* find a random object */ + return res; +} + +/*! + * \internal + * \brief Test ao2_find with OBJ_POINTER. + * \since 12.0.0 + * + * \param res Passed in enum ast_test_result_state. + * \param look_in Container to search. + * \param limit Container contains objects 0 - (limit - 1). + * \param test Test output controller. + * + * \return enum ast_test_result_state + */ +static int test_ao2_find_w_OBJ_POINTER(int res, struct ao2_container *look_in, int limit, struct ast_test *test) +{ + int i; + int num; + struct test_obj tmp_obj = { 0, }; + struct test_obj *obj; + + for (num = 75; num--;) { + i = ast_random() % limit; /* find a random object */ + tmp_obj.i = i; - if (!(obj = ao2_find(c1, &tmp_obj, OBJ_POINTER))) { - res = AST_TEST_FAIL; + obj = ao2_find(look_in, &tmp_obj, OBJ_POINTER); + if (!obj) { ast_test_status_update(test, "COULD NOT FIND:%d, ao2_find() with OBJ_POINTER flag failed.\n", i); + res = AST_TEST_FAIL; } else { - /* a correct match will only take place when the custom cmp function is used */ - if (use_cmp && obj->i != i) { - ast_test_status_update(test, "object %d does not match object %d\n", obj->i, tmp_obj.i); + if (obj->i != i) { + ast_test_status_update(test, "object %d does not match %d\n", obj->i, i); res = AST_TEST_FAIL; } ao2_t_ref(obj, -1, "test"); } } - /* Testing ao2_find with OBJ_KEY */ - num = 75; - for (; num; num--) { - int i = (ast_random() % ((lim / 2)) + 1); /* find a random object */ - if (!(obj = ao2_find(c1, &i, OBJ_KEY))) { - res = AST_TEST_FAIL; + return res; +} + +/*! + * \internal + * \brief Test ao2_find with OBJ_KEY. + * \since 12.0.0 + * + * \param res Passed in enum ast_test_result_state. + * \param look_in Container to search. + * \param limit Container contains objects 0 - (limit - 1). + * \param test Test output controller. + * + * \return enum ast_test_result_state + */ +static int test_ao2_find_w_OBJ_KEY(int res, struct ao2_container *look_in, int limit, struct ast_test *test) +{ + int i; + int num; + struct test_obj *obj; + + for (num = 75; num--;) { + i = ast_random() % limit; /* find a random object */ + + obj = ao2_find(look_in, &i, OBJ_KEY); + if (!obj) { ast_test_status_update(test, "COULD NOT FIND:%d, ao2_find() with OBJ_KEY flag failed.\n", i); + res = AST_TEST_FAIL; } else { - /* a correct match will only take place when the custom cmp function is used */ - if (use_cmp && obj->i != i) { - ast_test_status_update(test, "object %d does not match object %d\n", obj->i, tmp_obj.i); + if (obj->i != i) { + ast_test_status_update(test, "object %d does not match %d\n", obj->i, i); res = AST_TEST_FAIL; } ao2_t_ref(obj, -1, "test"); } } - /* Testing ao2_find with OBJ_POINTER | OBJ_UNLINK | OBJ_CONTINUE. + return res; +} + +/*! + * \internal + * \brief Test ao2_find with OBJ_PARTIAL_KEY. + * \since 12.0.0 + * + * \param res Passed in enum ast_test_result_state. + * \param look_in Container to search. + * \param limit Container contains objects 0 - (limit - 1). + * \param test Test output controller. + * + * \return enum ast_test_result_state + */ +static int test_ao2_find_w_OBJ_PARTIAL_KEY(int res, struct ao2_container *look_in, int limit, struct ast_test *test) +{ + int i; + int num; + struct test_obj *obj; + + /* Set partial match to find exactly. */ + partial_key_match_range = 0; + + for (num = 100; num--;) { + i = ast_random() % limit; /* find a random object */ + + obj = ao2_find(look_in, &i, OBJ_PARTIAL_KEY); + if (!obj) { + ast_test_status_update(test, "COULD NOT FIND:%d, ao2_find() with OBJ_PARTIAL_KEY flag failed.\n", i); + res = AST_TEST_FAIL; + } else { + if (obj->i != i) { + ast_test_status_update(test, "object %d does not match %d\n", obj->i, i); + res = AST_TEST_FAIL; + } + ao2_t_ref(obj, -1, "test"); + } + } + + return res; +} + +static int astobj2_test_1_helper(int tst_num, enum test_container_type type, int use_sort, unsigned int lim, struct ast_test *test) +{ + const char *c_type; + struct ao2_container *c1; + struct ao2_container *c2; + struct ao2_iterator it; + struct ao2_iterator *mult_it; + struct test_obj *obj; + ao2_callback_fn *cmp_fn; + int n_buckets; + int increment = 0; + int destructor_count = 0; + int count; + int num; + int res = AST_TEST_PASS; + + c_type = test_container2str(type); + ast_test_status_update(test, "Test %d, %s containers (%s).\n", + tst_num, c_type, use_sort ? "sorted" : "non-sorted"); + + /* Need at least 12 objects for the special iax2 OBJ_CONTINUE test. */ + if (lim < 12) { + lim = 12; + } + + c1 = NULL; + switch (type) { + case TEST_CONTAINER_LIST: + /* Lists just have one bucket. */ + n_buckets = 1; + c1 = ao2_t_container_alloc_list(AO2_ALLOC_OPT_LOCK_MUTEX, 0, + use_sort ? test_sort_cb : NULL, test_cmp_cb, "test"); + break; + case TEST_CONTAINER_HASH: + n_buckets = (ast_random() % ((lim / 4) + 1)) + 1; + if (n_buckets < 6) { + /* Need at least 6 buckets for the special iax2 OBJ_CONTINUE test. */ + n_buckets = 6; + } + c1 = ao2_t_container_alloc_hash(AO2_ALLOC_OPT_LOCK_MUTEX, 0, n_buckets, + test_hash_cb, use_sort ? test_sort_cb : NULL, test_cmp_cb, "test"); + break; + } + c2 = ao2_t_container_alloc(1, NULL, NULL, "test"); + + if (!c1 || !c2) { + ast_test_status_update(test, "ao2_container_alloc failed.\n"); + res = AST_TEST_FAIL; + goto cleanup; + } + + /* Create objects and link into container */ + destructor_count = lim; + for (num = 0; num < lim; ++num) { + if (!(obj = ao2_t_alloc(sizeof(struct test_obj), test_obj_destructor, "making zombies"))) { + ast_test_status_update(test, "ao2_alloc failed.\n"); + res = AST_TEST_FAIL; + goto cleanup; + } + obj->destructor_count = &destructor_count; + obj->i = num; + ao2_link(c1, obj); + ao2_t_ref(obj, -1, "test"); + if (ao2_container_count(c1) != num + 1) { + ast_test_status_update(test, "container did not link correctly\n"); + res = AST_TEST_FAIL; + } + } + if (ao2_container_check(c1, 0)) { + ast_test_status_update(test, "container integrity check failed\n"); + res = AST_TEST_FAIL; + goto cleanup; + } + + ast_test_status_update(test, "%s container created: buckets: %d, items: %d\n", + c_type, n_buckets, lim); + + /* Testing ao2_container_clone */ + res = test_container_clone(res, c1, test); + + /* Testing ao2_find with no flags */ + res = test_ao2_find_w_no_flags(res, c1, lim, test); + + /* Testing ao2_find with OBJ_POINTER */ + res = test_ao2_find_w_OBJ_POINTER(res, c1, lim, test); + + /* Testing ao2_find with OBJ_KEY */ + res = test_ao2_find_w_OBJ_KEY(res, c1, lim, test); + + /* Testing ao2_find with OBJ_PARTIAL_KEY */ + res = test_ao2_find_w_OBJ_PARTIAL_KEY(res, c1, lim, test); + + /* + * Testing ao2_find with OBJ_POINTER | OBJ_UNLINK | OBJ_CONTINUE. * In this test items are unlinked from c1 and placed in c2. Then * unlinked from c2 and placed back into c1. * * For this module and set of custom hash/cmp functions, an object * should only be found if the astobj2 default cmp function is used. - * This test is designed to mimic the chan_iax.c call number use case. */ - num = lim < 25 ? lim : 25; - for (; num; num--) { - if (!(obj = ao2_find(c1, NULL, OBJ_POINTER | OBJ_UNLINK | OBJ_CONTINUE))) { - if (!use_cmp) { - ast_test_status_update(test, "ao2_find with OBJ_POINTER | OBJ_UNLINK | OBJ_CONTINUE failed with default hash function.\n"); - res = AST_TEST_FAIL; + * This test is designed to mimic the chan_iax.c call number use case. + * + * Must test the custom cmp_cb case first since it should never + * find and thus unlink anything for this test. + */ + for (cmp_fn = test_cmp_cb; ; cmp_fn = NULL) { + num = lim; + for (count = 0; num && count < 100; ++count) { + --num; + + /* This special manipulation is needed for sorted hash buckets. */ + special_bucket = num; + switch (count) { + case 0: + /* Beyond end of bucket list. */ + special_match = lim; + break; + case 1: + /* At end of bucket list. */ + special_match = num; + break; + case 2: + /* In between in middle of bucket list. */ + special_match = num - 1; + break; + case 3: + /* Beginning of bucket list. */ + special_match = num % n_buckets; + break; + case 4: + /* Before bucket list. */ + special_match = -1; + break; + default: + /* Empty bucket list. (If possible to empty it.) */ + special_match = -1; + special_bucket = lim - 1; + break; } - } else { - if (use_cmp) { - ast_test_status_update(test, "ao2_find with OBJ_POINTER | OBJ_UNLINK | OBJ_CONTINUE failed with custom hash function.\n"); - res = AST_TEST_FAIL; + + /* ao2_find is just a shortcut notation for ao2_callback(). */ + obj = ao2_callback(c1, OBJ_POINTER | OBJ_UNLINK | OBJ_CONTINUE, cmp_fn, NULL); + if (!obj) { + if (!cmp_fn) { + ast_test_status_update(test, + "ao2_find with OBJ_POINTER | OBJ_UNLINK | OBJ_CONTINUE failed with default cmp_cb.\n"); + res = AST_TEST_FAIL; + } + } else { + if (cmp_fn) { + ast_test_status_update(test, + "ao2_find with OBJ_POINTER | OBJ_UNLINK | OBJ_CONTINUE failed with custom cmp_cb.\n"); + res = AST_TEST_FAIL; + } + ao2_link(c2, obj); + ao2_t_ref(obj, -1, "test"); } - ao2_link(c2, obj); + } + if (ao2_container_check(c1, 0)) { + ast_test_status_update(test, "container integrity check failed\n"); + res = AST_TEST_FAIL; + goto cleanup; + } + if (ao2_container_check(c2, 0)) { + ast_test_status_update(test, "container integrity check failed\n"); + res = AST_TEST_FAIL; + goto cleanup; + } + it = ao2_iterator_init(c2, 0); + while ((obj = ao2_t_iterator_next(&it, "test"))) { + ao2_t_unlink(c2, obj, "test"); + ao2_t_link(c1, obj, "test"); ao2_t_ref(obj, -1, "test"); } + ao2_iterator_destroy(&it); + if (ao2_container_check(c1, 0)) { + ast_test_status_update(test, "container integrity check failed\n"); + res = AST_TEST_FAIL; + goto cleanup; + } + if (ao2_container_check(c2, 0)) { + ast_test_status_update(test, "container integrity check failed\n"); + res = AST_TEST_FAIL; + goto cleanup; + } + + if (!cmp_fn) { + /* Completed testing with custom cmp_cb and default cmp_cb */ + break; + } } - it = ao2_iterator_init(c2, 0); - while ((obj = ao2_t_iterator_next(&it, "test"))) { - ao2_t_unlink(c2, obj, "test"); - ao2_t_link(c1, obj, "test"); - ao2_t_ref(obj, -1, "test"); - } - ao2_iterator_destroy(&it); /* Test Callback with no flags. */ increment = 0; @@ -294,10 +622,10 @@ static int astobj2_test_helper(int use_hash, int use_cmp, unsigned int lim, stru res = AST_TEST_FAIL; } - /* Test OBJ_MULTIPLE with OBJ_UNLINK*/ + /* Test OBJ_MULTIPLE with OBJ_UNLINK, add items back afterwards */ num = lim < 25 ? lim : 25; if (!(mult_it = ao2_t_callback(c1, OBJ_MULTIPLE | OBJ_UNLINK, multiple_cb, &num, "test multiple"))) { - ast_test_status_update(test, "OBJ_MULTIPLE iwth OBJ_UNLINK test failed.\n"); + ast_test_status_update(test, "OBJ_MULTIPLE with OBJ_UNLINK test failed.\n"); res = AST_TEST_FAIL; } else { /* make sure num items unlinked is as expected */ @@ -305,6 +633,11 @@ static int astobj2_test_helper(int use_hash, int use_cmp, unsigned int lim, stru ast_test_status_update(test, "OBJ_MULTIPLE | OBJ_UNLINK test failed, did not unlink correct number of objects.\n"); res = AST_TEST_FAIL; } + if (ao2_container_check(c1, 0)) { + ast_test_status_update(test, "container integrity check failed\n"); + res = AST_TEST_FAIL; + goto cleanup; + } /* link what was unlinked back into c1 */ while ((obj = ao2_t_iterator_next(mult_it, "test"))) { @@ -312,10 +645,15 @@ static int astobj2_test_helper(int use_hash, int use_cmp, unsigned int lim, stru ao2_t_ref(obj, -1, "test"); /* remove ref from iterator */ } ao2_iterator_destroy(mult_it); + if (ao2_container_check(c1, 0)) { + ast_test_status_update(test, "container integrity check failed\n"); + res = AST_TEST_FAIL; + goto cleanup; + } } - /* Test OBJ_MULTIPLE without unlink, add items back afterwards */ - num = lim < 25 ? lim : 25; + /* Test OBJ_MULTIPLE without unlink and iterate the returned container */ + num = 5; if (!(mult_it = ao2_t_callback(c1, OBJ_MULTIPLE, multiple_cb, &num, "test multiple"))) { ast_test_status_update(test, "OBJ_MULTIPLE without OBJ_UNLINK test failed.\n"); res = AST_TEST_FAIL; @@ -327,7 +665,7 @@ static int astobj2_test_helper(int use_hash, int use_cmp, unsigned int lim, stru } /* Test OBJ_MULTIPLE without unlink and no iterating */ - num = lim < 5 ? lim : 5; + num = 5; if (!(mult_it = ao2_t_callback(c1, OBJ_MULTIPLE, multiple_cb, &num, "test multiple"))) { ast_test_status_update(test, "OBJ_MULTIPLE with no OBJ_UNLINK and no iterating failed.\n"); res = AST_TEST_FAIL; @@ -343,11 +681,18 @@ static int astobj2_test_helper(int use_hash, int use_cmp, unsigned int lim, stru /* Testing iterator. Unlink a single object and break. do not add item back */ it = ao2_iterator_init(c1, 0); - num = (lim / 4) + 1; + num = ast_random() % lim; /* remove a random object */ + if (!num) { + /* + * Well we cannot remove object zero because of test with + * all_but_one_cb later. + */ + num = 1; + } while ((obj = ao2_t_iterator_next(&it, "test"))) { if (obj->i == num) { - ao2_t_ref(obj, -1, "test"); ao2_t_unlink(c1, obj, "test"); + ao2_t_ref(obj, -1, "test"); break; } ao2_t_ref(obj, -1, "test"); @@ -359,6 +704,11 @@ static int astobj2_test_helper(int use_hash, int use_cmp, unsigned int lim, stru ast_test_status_update(test, "unlink during iterator failed. Number %d was not removed.\n", num); res = AST_TEST_FAIL; } + if (ao2_container_check(c1, 0)) { + ast_test_status_update(test, "container integrity check failed\n"); + res = AST_TEST_FAIL; + goto cleanup; + } /* Test unlink all with OBJ_MULTIPLE, leave a single object for the container to destroy */ ao2_t_callback(c1, OBJ_MULTIPLE | OBJ_UNLINK | OBJ_NODATA, all_but_one_cb, NULL, "test multiple"); @@ -367,6 +717,10 @@ static int astobj2_test_helper(int use_hash, int use_cmp, unsigned int lim, stru ast_test_status_update(test, "OBJ_MULTIPLE | OBJ_UNLINK | OBJ_NODATA failed. destructor count %d\n", destructor_count); res = AST_TEST_FAIL; } + if (ao2_container_check(c1, 0)) { + ast_test_status_update(test, "container integrity check failed\n"); + res = AST_TEST_FAIL; + } cleanup: /* destroy containers */ @@ -376,9 +730,6 @@ cleanup: if (c2) { ao2_t_ref(c2, -1, "bye c2"); } - if (c3) { - ao2_t_ref(c3, -1, "bye c3"); - } if (destructor_count > 0) { ast_test_status_update(test, "all destructors were not called, destructor count is %d\n", destructor_count); @@ -399,7 +750,7 @@ AST_TEST_DEFINE(astobj2_test_1) case TEST_INIT: info->name = "astobj2_test1"; info->category = "/main/astobj2/"; - info->summary = "astobj2 test using ao2 objects, containers, callbacks, and iterators"; + info->summary = "Test ao2 objects, containers, callbacks, and iterators"; info->description = "Builds ao2_containers with various item numbers, bucket sizes, cmp and hash " "functions. Runs a series of tests to manipulate the container using callbacks " @@ -409,28 +760,20 @@ AST_TEST_DEFINE(astobj2_test_1) break; } - - /* Test 1, 500 items with custom hash and cmp functions */ - ast_test_status_update(test, "Test 1, astobj2 test with 500 items.\n"); - if ((res = astobj2_test_helper(1, 1, 500, test)) == AST_TEST_FAIL) { + /* Test number, container_type, use_sort, number of objects. */ + if ((res = astobj2_test_1_helper(1, TEST_CONTAINER_LIST, 0, 50, test)) == AST_TEST_FAIL) { return res; } - /* Test 2, 1000 items with custom hash and default cmp functions */ - ast_test_status_update(test, "Test 2, astobj2 test with 1000 items.\n"); - if ((res = astobj2_test_helper(1, 0, 1000, test)) == AST_TEST_FAIL) { + if ((res = astobj2_test_1_helper(2, TEST_CONTAINER_LIST, 1, 50, test)) == AST_TEST_FAIL) { return res; } - /* Test 3, 10000 items with default hash and custom cmp functions */ - ast_test_status_update(test, "Test 3, astobj2 test with 10000 items.\n"); - if ((res = astobj2_test_helper(0, 1, 10000, test)) == AST_TEST_FAIL) { + if ((res = astobj2_test_1_helper(3, TEST_CONTAINER_HASH, 0, 1000, test)) == AST_TEST_FAIL) { return res; } - /* Test 4, 100000 items with default hash and cmp functions */ - ast_test_status_update(test, "Test 4, astobj2 test with 100000 items.\n"); - if ((res = astobj2_test_helper(0, 0, 100000, test)) == AST_TEST_FAIL) { + if ((res = astobj2_test_1_helper(4, TEST_CONTAINER_HASH, 1, 1000, test)) == AST_TEST_FAIL) { return res; } @@ -484,6 +827,11 @@ AST_TEST_DEFINE(astobj2_test_2) res = AST_TEST_FAIL; } } + if (ao2_container_check(c, 0)) { + ast_test_status_update(test, "container integrity check failed\n"); + res = AST_TEST_FAIL; + goto cleanup; + } /* * Iteration take 1. Just make sure we see all NUM_OBJS objects. @@ -698,11 +1046,929 @@ cleanup: return res; } +/*! + * \internal + * \brief Make a nonsorted container for astobj2 testing. + * \since 12.0.0 + * + * \param type Container type to create. + * \param options Container options + * + * \retval container on success. + * \retval NULL on error. + */ +static struct ao2_container *test_make_nonsorted(enum test_container_type type, int options) +{ + struct ao2_container *container; + + container = NULL; + switch (type) { + case TEST_CONTAINER_LIST: + container = ao2_container_alloc_list(AO2_ALLOC_OPT_LOCK_MUTEX, options, + NULL, test_cmp_cb); + break; + case TEST_CONTAINER_HASH: + container = ao2_container_alloc_hash(AO2_ALLOC_OPT_LOCK_MUTEX, options, 5, + test_hash_cb, NULL, test_cmp_cb); + break; + } + + return container; +} + +/*! + * \internal + * \brief Make a sorted container for astobj2 testing. + * \since 12.0.0 + * + * \param type Container type to create. + * \param options Container options + * + * \retval container on success. + * \retval NULL on error. + */ +static struct ao2_container *test_make_sorted(enum test_container_type type, int options) +{ + struct ao2_container *container; + + container = NULL; + switch (type) { + case TEST_CONTAINER_LIST: + container = ao2_t_container_alloc_list(AO2_ALLOC_OPT_LOCK_MUTEX, options, + test_sort_cb, test_cmp_cb, "test"); + break; + case TEST_CONTAINER_HASH: + container = ao2_t_container_alloc_hash(AO2_ALLOC_OPT_LOCK_MUTEX, options, 5, + test_hash_cb, test_sort_cb, test_cmp_cb, "test"); + break; + } + + return container; +} + +/*! + * \internal + * \brief Insert the given test vector into the given container. + * \since 12.0.0 + * + * \note The given test vector must not have any duplicates. + * + * \param container Container to insert the test vector. + * \param destroy_counter What to increment when the object is destroyed. + * \param vector Test vector to insert. + * \param count Number of objects in the vector. + * \param prefix Test output prefix string. + * \param test Test output controller. + * + * \retval 0 on success. + * \retval -1 on error. + */ +static int insert_test_vector(struct ao2_container *container, int *destroy_counter, const int *vector, int count, const char *prefix, struct ast_test *test) +{ + int idx; + struct test_obj *obj; + + for (idx = 0; idx < count; ++idx) { + obj = ao2_alloc(sizeof(struct test_obj), test_obj_destructor); + if (!obj) { + ast_test_status_update(test, "%s: ao2_alloc failed.\n", prefix); + return -1; + } + if (destroy_counter) { + /* This object ultimately needs to be destroyed. */ + ++*destroy_counter; + } + obj->destructor_count = destroy_counter; + obj->i = vector[idx]; + ao2_link(container, obj); + ao2_t_ref(obj, -1, "test"); + + if (ao2_container_count(container) != idx + 1) { + ast_test_status_update(test, + "%s: Unexpected container count. Expected:%d Got:%d\n", + prefix, idx + 1, ao2_container_count(container)); + return -1; + } + } + if (ao2_container_check(container, 0)) { + ast_test_status_update(test, "%s: Container integrity check failed\n", prefix); + return -1; + } + + return 0; +} + +/*! + * \internal + * \brief Insert duplicates of number into the given container. + * \since 12.0.0 + * + * \note The given container must not already have the number in it. + * + * \param container Container to insert the duplicates. + * \param destroy_counter What to increment when the object is destroyed. + * \param number Number of object to duplicate. + * \param prefix Test output prefix string. + * \param test Test output controller. + * + * \retval 0 on success. + * \retval -1 on error. + */ +static int insert_test_duplicates(struct ao2_container *container, int *destroy_counter, int number, const char *prefix, struct ast_test *test) +{ + int count; + struct test_obj *obj; + struct test_obj *obj_dup; + + /* Check if object already exists in the container. */ + obj = ao2_find(container, &number, OBJ_KEY); + if (obj) { + ast_test_status_update(test, "%s: Object %d already exists.\n", prefix, number); + ao2_t_ref(obj, -1, "test"); + return -1; + } + + /* Add three duplicate keyed objects. */ + obj_dup = NULL; + for (count = 0; count < 4; ++count) { + obj = ao2_alloc(sizeof(struct test_obj), test_obj_destructor); + if (!obj) { + ast_test_status_update(test, "%s: ao2_alloc failed.\n", prefix); + if (obj_dup) { + ao2_t_ref(obj_dup, -1, "test"); + } + return -1; + } + if (destroy_counter) { + /* This object ultimately needs to be destroyed. */ + ++*destroy_counter; + } + obj->destructor_count = destroy_counter; + obj->i = number; + obj->dup_number = count; + ao2_link(container, obj); + + if (count == 2) { + /* Duplicate this object. */ + obj_dup = obj; + } else { + ao2_t_ref(obj, -1, "test"); + } + } + + /* Add the duplicate object. */ + ao2_link(container, obj_dup); + ao2_t_ref(obj_dup, -1, "test"); + + if (ao2_container_check(container, 0)) { + ast_test_status_update(test, "%s: Container integrity check failed\n", prefix); + return -1; + } + + return 0; +} + +/*! + * \internal + * \brief Iterate over the container and compare the objects with the given vector. + * \since 12.0.0 + * + * \param res Passed in enum ast_test_result_state. + * \param container Container to iterate. + * \param flags Flags controlling the iteration. + * \param vector Expected vector to find. + * \param count Number of objects in the vector. + * \param prefix Test output prefix string. + * \param test Test output controller. + * + * \return enum ast_test_result_state + */ +static int test_ao2_iteration(int res, struct ao2_container *container, + enum ao2_iterator_flags flags, + const int *vector, int count, const char *prefix, struct ast_test *test) +{ + struct ao2_iterator iter; + struct test_obj *obj; + int idx; + + if (ao2_container_count(container) != count) { + ast_test_status_update(test, "%s: Container count doesn't match vector count.\n", + prefix); + res = AST_TEST_FAIL; + } + + iter = ao2_iterator_init(container, flags); + + /* Check iterated objects against the given vector. */ + for (idx = 0; idx < count; ++idx) { + obj = ao2_iterator_next(&iter); + if (!obj) { + ast_test_status_update(test, "%s: Too few objects found.\n", prefix); + res = AST_TEST_FAIL; + break; + } + if (vector[idx] != obj->i) { + ast_test_status_update(test, "%s: Object %d != vector[%d] %d.\n", + prefix, obj->i, idx, vector[idx]); + res = AST_TEST_FAIL; + } + ao2_ref(obj, -1); /* remove ref from iterator */ + } + obj = ao2_iterator_next(&iter); + if (obj) { + ast_test_status_update(test, "%s: Too many objects found. Object %d\n", + prefix, obj->i); + ao2_ref(obj, -1); /* remove ref from iterator */ + res = AST_TEST_FAIL; + } + + ao2_iterator_destroy(&iter); + + return res; +} + +/*! + * \internal + * \brief Run an ao2_callback() and compare the returned vector with the given vector. + * \since 12.0.0 + * + * \param res Passed in enum ast_test_result_state. + * \param container Container to traverse. + * \param flags Callback flags controlling the traversal. + * \param cmp_fn Compare function to select objects. + * \param arg Optional argument. + * \param vector Expected vector to find. + * \param count Number of objects in the vector. + * \param prefix Test output prefix string. + * \param test Test output controller. + * + * \return enum ast_test_result_state + */ +static int test_ao2_callback_traversal(int res, struct ao2_container *container, + enum search_flags flags, ao2_callback_fn *cmp_fn, void *arg, + const int *vector, int count, const char *prefix, struct ast_test *test) +{ + struct ao2_iterator *mult_iter; + struct test_obj *obj; + int idx; + + mult_iter = ao2_callback(container, flags | OBJ_MULTIPLE, cmp_fn, arg); + if (!mult_iter) { + ast_test_status_update(test, "%s: Did not return iterator.\n", prefix); + return AST_TEST_FAIL; + } + + /* Check matching objects against the given vector. */ + for (idx = 0; idx < count; ++idx) { + obj = ao2_iterator_next(mult_iter); + if (!obj) { + ast_test_status_update(test, "%s: Too few objects found.\n", prefix); + res = AST_TEST_FAIL; + break; + } + if (vector[idx] != obj->i) { + ast_test_status_update(test, "%s: Object %d != vector[%d] %d.\n", + prefix, obj->i, idx, vector[idx]); + res = AST_TEST_FAIL; + } + ao2_ref(obj, -1); /* remove ref from iterator */ + } + obj = ao2_iterator_next(mult_iter); + if (obj) { + ast_test_status_update(test, "%s: Too many objects found. Object %d\n", + prefix, obj->i); + ao2_ref(obj, -1); /* remove ref from iterator */ + res = AST_TEST_FAIL; + } + ao2_iterator_destroy(mult_iter); + + return res; +} + +/*! + * \internal + * \brief Run an ao2_find() for duplicates and compare the returned vector with the given vector. + * \since 12.0.0 + * + * \param res Passed in enum ast_test_result_state. + * \param container Container to traverse. + * \param flags Callback flags controlling the traversal. + * \param number Number of object to find all duplicates. + * \param vector Expected vector to find. + * \param count Number of objects in the vector. + * \param prefix Test output prefix string. + * \param test Test output controller. + * + * \return enum ast_test_result_state + */ +static int test_expected_duplicates(int res, struct ao2_container *container, + enum search_flags flags, int number, + const int *vector, int count, const char *prefix, struct ast_test *test) +{ + struct ao2_iterator *mult_iter; + struct test_obj *obj; + int idx; + + mult_iter = ao2_find(container, &number, flags | OBJ_MULTIPLE | OBJ_KEY); + if (!mult_iter) { + ast_test_status_update(test, "%s: Did not return iterator.\n", prefix); + return AST_TEST_FAIL; + } + + /* Check matching objects against the given vector. */ + for (idx = 0; idx < count; ++idx) { + obj = ao2_iterator_next(mult_iter); + if (!obj) { + ast_test_status_update(test, "%s: Too few objects found.\n", prefix); + res = AST_TEST_FAIL; + break; + } + if (number != obj->i) { + ast_test_status_update(test, "%s: Object %d != %d.\n", + prefix, obj->i, number); + res = AST_TEST_FAIL; + } + if (vector[idx] != obj->dup_number) { + ast_test_status_update(test, "%s: Object dup id %d != vector[%d] %d.\n", + prefix, obj->dup_number, idx, vector[idx]); + res = AST_TEST_FAIL; + } + ao2_ref(obj, -1); /* remove ref from iterator */ + } + obj = ao2_iterator_next(mult_iter); + if (obj) { + ast_test_status_update(test, + "%s: Too many objects found. Object %d, dup id %d\n", + prefix, obj->i, obj->dup_number); + ao2_ref(obj, -1); /* remove ref from iterator */ + res = AST_TEST_FAIL; + } + ao2_iterator_destroy(mult_iter); + + return res; +} + +/*! + * \internal + * \brief Test nonsorted container traversal. + * \since 12.0.0 + * + * \param res Passed in enum ast_test_result_state. + * \param tst_num Test number. + * \param type Container type to test. + * \param test Test output controller. + * + * \return enum ast_test_result_state + */ +static int test_traversal_nonsorted(int res, int tst_num, enum test_container_type type, struct ast_test *test) +{ + struct ao2_container *c1; + struct ao2_container *c2 = NULL; + int partial; + int destructor_count = 0; + + /*! Container object insertion vector. */ + static const int test_initial[] = { + 1, 0, 2, 6, 4, 7, 5, 3, 9, 8 + }; + + /*! Container object insertion vector reversed. */ + static const int test_reverse[] = { + 8, 9, 3, 5, 7, 4, 6, 2, 0, 1 + }; + static const int test_list_partial_forward[] = { + 6, 7, 5 + }; + static const int test_list_partial_backward[] = { + 5, 7, 6 + }; + + /* The hash orders assume that there are 5 buckets. */ + static const int test_hash_end_forward[] = { + 0, 5, 1, 6, 2, 7, 3, 8, 4, 9 + }; + static const int test_hash_end_backward[] = { + 9, 4, 8, 3, 7, 2, 6, 1, 5, 0 + }; + static const int test_hash_begin_forward[] = { + 5, 0, 6, 1, 7, 2, 8, 3, 9, 4 + }; + static const int test_hash_begin_backward[] = { + 4, 9, 3, 8, 2, 7, 1, 6, 0, 5 + }; + static const int test_hash_partial_forward[] = { + 5, 6, 7 + }; + static const int test_hash_partial_backward[] = { + 7, 6, 5 + }; + + ast_test_status_update(test, "Test %d, %s containers.\n", + tst_num, test_container2str(type)); + + /* Create container that inserts objects at the end. */ + c1 = test_make_nonsorted(type, 0); + if (!c1) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + if (insert_test_vector(c1, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c1", test)) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + + /* Create container that inserts objects at the beginning. */ + c2 = test_make_nonsorted(type, AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN); + if (!c2) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + if (insert_test_vector(c2, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c2", test)) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + + /* Check container iteration directions */ + switch (type) { + case TEST_CONTAINER_LIST: + res = test_ao2_iteration(res, c1, 0, + test_initial, ARRAY_LEN(test_initial), + "Iteration (ascending, insert end)", test); + res = test_ao2_iteration(res, c1, AO2_ITERATOR_DESCENDING, + test_reverse, ARRAY_LEN(test_reverse), + "Iteration (descending, insert end)", test); + + res = test_ao2_iteration(res, c2, 0, + test_reverse, ARRAY_LEN(test_reverse), + "Iteration (ascending, insert begin)", test); + res = test_ao2_iteration(res, c2, AO2_ITERATOR_DESCENDING, + test_initial, ARRAY_LEN(test_initial), + "Iteration (descending, insert begin)", test); + break; + case TEST_CONTAINER_HASH: + res = test_ao2_iteration(res, c1, 0, + test_hash_end_forward, ARRAY_LEN(test_hash_end_forward), + "Iteration (ascending, insert end)", test); + res = test_ao2_iteration(res, c1, AO2_ITERATOR_DESCENDING, + test_hash_end_backward, ARRAY_LEN(test_hash_end_backward), + "Iteration (descending, insert end)", test); + + res = test_ao2_iteration(res, c2, 0, + test_hash_begin_forward, ARRAY_LEN(test_hash_begin_forward), + "Iteration (ascending, insert begin)", test); + res = test_ao2_iteration(res, c2, AO2_ITERATOR_DESCENDING, + test_hash_begin_backward, ARRAY_LEN(test_hash_begin_backward), + "Iteration (descending, insert begin)", test); + break; + } + + /* Check container traversal directions */ + switch (type) { + case TEST_CONTAINER_LIST: + res = test_ao2_callback_traversal(res, c1, OBJ_ORDER_ASCENDING, NULL, NULL, + test_initial, ARRAY_LEN(test_initial), + "Traversal (ascending, insert end)", test); + res = test_ao2_callback_traversal(res, c1, OBJ_ORDER_DESCENDING, NULL, NULL, + test_reverse, ARRAY_LEN(test_reverse), + "Traversal (descending, insert end)", test); + + res = test_ao2_callback_traversal(res, c2, OBJ_ORDER_ASCENDING, NULL, NULL, + test_reverse, ARRAY_LEN(test_reverse), + "Traversal (ascending, insert begin)", test); + res = test_ao2_callback_traversal(res, c2, OBJ_ORDER_DESCENDING, NULL, NULL, + test_initial, ARRAY_LEN(test_initial), + "Traversal (descending, insert begin)", test); + break; + case TEST_CONTAINER_HASH: + res = test_ao2_callback_traversal(res, c1, OBJ_ORDER_ASCENDING, NULL, NULL, + test_hash_end_forward, ARRAY_LEN(test_hash_end_forward), + "Traversal (ascending, insert end)", test); + res = test_ao2_callback_traversal(res, c1, OBJ_ORDER_DESCENDING, NULL, NULL, + test_hash_end_backward, ARRAY_LEN(test_hash_end_backward), + "Traversal (descending, insert end)", test); + + res = test_ao2_callback_traversal(res, c2, OBJ_ORDER_ASCENDING, NULL, NULL, + test_hash_begin_forward, ARRAY_LEN(test_hash_begin_forward), + "Traversal (ascending, insert begin)", test); + res = test_ao2_callback_traversal(res, c2, OBJ_ORDER_DESCENDING, NULL, NULL, + test_hash_begin_backward, ARRAY_LEN(test_hash_begin_backward), + "Traversal (descending, insert begin)", test); + break; + } + + /* Check traversal with OBJ_PARTIAL_KEY search range. */ + partial = 6; + partial_key_match_range = 1; + switch (type) { + case TEST_CONTAINER_LIST: + res = test_ao2_callback_traversal(res, c1, OBJ_PARTIAL_KEY | OBJ_ORDER_ASCENDING, + test_cmp_cb, &partial, + test_list_partial_forward, ARRAY_LEN(test_list_partial_forward), + "Traversal OBJ_PARTIAL_KEY (ascending)", test); + res = test_ao2_callback_traversal(res, c1, OBJ_PARTIAL_KEY | OBJ_ORDER_DESCENDING, + test_cmp_cb, &partial, + test_list_partial_backward, ARRAY_LEN(test_list_partial_backward), + "Traversal OBJ_PARTIAL_KEY (descending)", test); + break; + case TEST_CONTAINER_HASH: + res = test_ao2_callback_traversal(res, c1, OBJ_PARTIAL_KEY | OBJ_ORDER_ASCENDING, + test_cmp_cb, &partial, + test_hash_partial_forward, ARRAY_LEN(test_hash_partial_forward), + "Traversal OBJ_PARTIAL_KEY (ascending)", test); + res = test_ao2_callback_traversal(res, c1, OBJ_PARTIAL_KEY | OBJ_ORDER_DESCENDING, + test_cmp_cb, &partial, + test_hash_partial_backward, ARRAY_LEN(test_hash_partial_backward), + "Traversal OBJ_PARTIAL_KEY (descending)", test); + break; + } + +test_cleanup: + /* destroy containers */ + if (c1) { + ao2_t_ref(c1, -1, "bye c1"); + } + if (c2) { + ao2_t_ref(c2, -1, "bye c2"); + } + + if (destructor_count > 0) { + ast_test_status_update(test, + "all destructors were not called, destructor count is %d\n", + destructor_count); + res = AST_TEST_FAIL; + } else if (destructor_count < 0) { + ast_test_status_update(test, + "Destructor was called too many times, destructor count is %d\n", + destructor_count); + res = AST_TEST_FAIL; + } + + return res; +} + +/*! + * \internal + * \brief Test sorted container traversal. + * \since 12.0.0 + * + * \param res Passed in enum ast_test_result_state. + * \param tst_num Test number. + * \param type Container type to test. + * \param test Test output controller. + * + * \return enum ast_test_result_state + */ +static int test_traversal_sorted(int res, int tst_num, enum test_container_type type, struct ast_test *test) +{ + struct ao2_container *c1; + struct ao2_container *c2 = NULL; + int partial; + int destructor_count = 0; + int duplicate_number = 100; + + /*! Container object insertion vector. */ + static const int test_initial[] = { + 1, 0, 2, 6, 4, 7, 5, 3, 9, 8 + }; + + /*! Container forward traversal/iteration. */ + static const int test_forward[] = { + 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 + }; + /*! Container backward traversal/iteration. */ + static const int test_backward[] = { + 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 + }; + + static const int test_partial_forward[] = { + 5, 6, 7 + }; + static const int test_partial_backward[] = { + 7, 6, 5 + }; + + /* The hash orders assume that there are 5 buckets. */ + static const int test_hash_forward[] = { + 0, 5, 1, 6, 2, 7, 3, 8, 4, 9 + }; + static const int test_hash_backward[] = { + 9, 4, 8, 3, 7, 2, 6, 1, 5, 0 + }; + static const int test_hash_partial_forward[] = { + 5, 6, 7 + }; + static const int test_hash_partial_backward[] = { + 7, 6, 5 + }; + + /* Duplicate identifier order */ + static const int test_dup_allow_forward[] = { + 0, 1, 2, 3, 2 + }; + static const int test_dup_allow_backward[] = { + 2, 3, 2, 1, 0 + }; + static const int test_dup_reject[] = { + 0 + }; + static const int test_dup_obj_reject_forward[] = { + 0, 1, 2, 3 + }; + static const int test_dup_obj_reject_backward[] = { + 3, 2, 1, 0 + }; + static const int test_dup_replace[] = { + 2 + }; + + ast_test_status_update(test, "Test %d, %s containers.\n", + tst_num, test_container2str(type)); + + /* Create container that inserts duplicate objects after matching objects. */ + c1 = test_make_sorted(type, AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW); + if (!c1) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + if (insert_test_vector(c1, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c1(DUPS_ALLOW)", test)) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + + /* Create container that inserts duplicate objects before matching objects. */ + c2 = test_make_sorted(type, AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN | AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW); + if (!c2) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + if (insert_test_vector(c2, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c2(DUPS_ALLOW)", test)) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + + /* Check container iteration directions */ + switch (type) { + case TEST_CONTAINER_LIST: + res = test_ao2_iteration(res, c1, 0, + test_forward, ARRAY_LEN(test_forward), + "Iteration (ascending)", test); + res = test_ao2_iteration(res, c1, AO2_ITERATOR_DESCENDING, + test_backward, ARRAY_LEN(test_backward), + "Iteration (descending)", test); + break; + case TEST_CONTAINER_HASH: + res = test_ao2_iteration(res, c1, 0, + test_hash_forward, ARRAY_LEN(test_hash_forward), + "Iteration (ascending)", test); + res = test_ao2_iteration(res, c1, AO2_ITERATOR_DESCENDING, + test_hash_backward, ARRAY_LEN(test_hash_backward), + "Iteration (descending)", test); + break; + } + + /* Check container traversal directions */ + switch (type) { + case TEST_CONTAINER_LIST: + res = test_ao2_callback_traversal(res, c1, OBJ_ORDER_ASCENDING, NULL, NULL, + test_forward, ARRAY_LEN(test_forward), + "Traversal (ascending)", test); + res = test_ao2_callback_traversal(res, c1, OBJ_ORDER_DESCENDING, NULL, NULL, + test_backward, ARRAY_LEN(test_backward), + "Traversal (descending)", test); + break; + case TEST_CONTAINER_HASH: + res = test_ao2_callback_traversal(res, c1, OBJ_ORDER_ASCENDING, NULL, NULL, + test_hash_forward, ARRAY_LEN(test_hash_forward), + "Traversal (ascending, insert end)", test); + res = test_ao2_callback_traversal(res, c1, OBJ_ORDER_DESCENDING, NULL, NULL, + test_hash_backward, ARRAY_LEN(test_hash_backward), + "Traversal (descending)", test); + break; + } + + /* Check traversal with OBJ_PARTIAL_KEY search range. */ + partial = 6; + partial_key_match_range = 1; + switch (type) { + case TEST_CONTAINER_LIST: + res = test_ao2_callback_traversal(res, c1, OBJ_PARTIAL_KEY | OBJ_ORDER_ASCENDING, + test_cmp_cb, &partial, + test_partial_forward, ARRAY_LEN(test_partial_forward), + "Traversal OBJ_PARTIAL_KEY (ascending)", test); + res = test_ao2_callback_traversal(res, c1, OBJ_PARTIAL_KEY | OBJ_ORDER_DESCENDING, + test_cmp_cb, &partial, + test_partial_backward, ARRAY_LEN(test_partial_backward), + "Traversal OBJ_PARTIAL_KEY (descending)", test); + break; + case TEST_CONTAINER_HASH: + res = test_ao2_callback_traversal(res, c1, OBJ_PARTIAL_KEY | OBJ_ORDER_ASCENDING, + test_cmp_cb, &partial, + test_hash_partial_forward, ARRAY_LEN(test_hash_partial_forward), + "Traversal OBJ_PARTIAL_KEY (ascending)", test); + res = test_ao2_callback_traversal(res, c1, OBJ_PARTIAL_KEY | OBJ_ORDER_DESCENDING, + test_cmp_cb, &partial, + test_hash_partial_backward, ARRAY_LEN(test_hash_partial_backward), + "Traversal OBJ_PARTIAL_KEY (descending)", test); + break; + } + + /* Add duplicates to initial containers that allow duplicates */ + if (insert_test_duplicates(c1, &destructor_count, duplicate_number, "c1(DUPS_ALLOW)", test)) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + if (insert_test_duplicates(c2, &destructor_count, duplicate_number, "c2(DUPS_ALLOW)", test)) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + + /* Check duplicates in containers that allow duplicates. */ + res = test_expected_duplicates(res, c1, OBJ_ORDER_ASCENDING, duplicate_number, + test_dup_allow_forward, ARRAY_LEN(test_dup_allow_forward), + "Duplicates (ascending, DUPS_ALLOW)", test); + res = test_expected_duplicates(res, c1, OBJ_ORDER_DESCENDING, duplicate_number, + test_dup_allow_backward, ARRAY_LEN(test_dup_allow_backward), + "Duplicates (descending, DUPS_ALLOW)", test); + + ao2_t_ref(c1, -1, "bye c1"); + c1 = NULL; + ao2_t_ref(c2, -1, "bye c2"); + c2 = NULL; + + /* Create containers that reject duplicate keyed objects. */ + c1 = test_make_sorted(type, AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT); + if (!c1) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + if (insert_test_vector(c1, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c1(DUPS_REJECT)", test)) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + if (insert_test_duplicates(c1, &destructor_count, duplicate_number, "c1(DUPS_REJECT)", test)) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + c2 = test_make_sorted(type, AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN | AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT); + if (!c2) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + if (insert_test_vector(c2, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c2(DUPS_REJECT)", test)) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + if (insert_test_duplicates(c2, &destructor_count, duplicate_number, "c2(DUPS_REJECT)", test)) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + + /* Check duplicates in containers that reject duplicate keyed objects. */ + res = test_expected_duplicates(res, c1, OBJ_ORDER_ASCENDING, duplicate_number, + test_dup_reject, ARRAY_LEN(test_dup_reject), + "Duplicates (ascending, DUPS_REJECT)", test); + res = test_expected_duplicates(res, c1, OBJ_ORDER_DESCENDING, duplicate_number, + test_dup_reject, ARRAY_LEN(test_dup_reject), + "Duplicates (descending, DUPS_REJECT)", test); + + ao2_t_ref(c1, -1, "bye c1"); + c1 = NULL; + ao2_t_ref(c2, -1, "bye c2"); + c2 = NULL; + + /* Create containers that reject duplicate objects. */ + c1 = test_make_sorted(type, AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT); + if (!c1) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + if (insert_test_vector(c1, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c1(DUPS_OBJ_REJECT)", test)) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + if (insert_test_duplicates(c1, &destructor_count, duplicate_number, "c1(DUPS_OBJ_REJECT)", test)) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + c2 = test_make_sorted(type, AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN | AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT); + if (!c2) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + if (insert_test_vector(c2, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c2(DUPS_OBJ_REJECT)", test)) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + if (insert_test_duplicates(c2, &destructor_count, duplicate_number, "c2(DUPS_OBJ_REJECT)", test)) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + + /* Check duplicates in containers that reject duplicate objects. */ + res = test_expected_duplicates(res, c1, OBJ_ORDER_ASCENDING, duplicate_number, + test_dup_obj_reject_forward, ARRAY_LEN(test_dup_obj_reject_forward), + "Duplicates (ascending, DUPS_OBJ_REJECT)", test); + res = test_expected_duplicates(res, c1, OBJ_ORDER_DESCENDING, duplicate_number, + test_dup_obj_reject_backward, ARRAY_LEN(test_dup_obj_reject_backward), + "Duplicates (descending, DUPS_OBJ_REJECT)", test); + + ao2_t_ref(c1, -1, "bye c1"); + c1 = NULL; + ao2_t_ref(c2, -1, "bye c2"); + c2 = NULL; + + /* Create container that replaces duplicate keyed objects. */ + c1 = test_make_sorted(type, AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE); + if (!c1) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + if (insert_test_vector(c1, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c1(DUPS_REJECT)", test)) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + if (insert_test_duplicates(c1, &destructor_count, duplicate_number, "c1(DUPS_REJECT)", test)) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + c2 = test_make_sorted(type, AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN | AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE); + if (!c2) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + if (insert_test_vector(c2, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c2(DUPS_REPLACE)", test)) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + if (insert_test_duplicates(c2, &destructor_count, duplicate_number, "c2(DUPS_REPLACE)", test)) { + res = AST_TEST_FAIL; + goto test_cleanup; + } + + /* Check duplicates in containers that replaces duplicate keyed objects. */ + res = test_expected_duplicates(res, c1, OBJ_ORDER_ASCENDING, duplicate_number, + test_dup_replace, ARRAY_LEN(test_dup_replace), + "Duplicates (ascending, DUPS_REPLACE)", test); + res = test_expected_duplicates(res, c1, OBJ_ORDER_DESCENDING, duplicate_number, + test_dup_replace, ARRAY_LEN(test_dup_replace), + "Duplicates (descending, DUPS_REPLACE)", test); + +test_cleanup: + /* destroy containers */ + if (c1) { + ao2_t_ref(c1, -1, "bye c1"); + } + if (c2) { + ao2_t_ref(c2, -1, "bye c2"); + } + + if (destructor_count > 0) { + ast_test_status_update(test, + "all destructors were not called, destructor count is %d\n", + destructor_count); + res = AST_TEST_FAIL; + } else if (destructor_count < 0) { + ast_test_status_update(test, + "Destructor was called too many times, destructor count is %d\n", + destructor_count); + res = AST_TEST_FAIL; + } + + return res; +} + +AST_TEST_DEFINE(astobj2_test_4) +{ + int res = AST_TEST_PASS; + + switch (cmd) { + case TEST_INIT: + info->name = "astobj2_test4"; + info->category = "/main/astobj2/"; + info->summary = "Test container traversal/iteration"; + info->description = + "This test is to see if the container traversal/iteration works " + "as intended for each supported container type."; + return AST_TEST_NOT_RUN; + case TEST_EXECUTE: + break; + } + + res = test_traversal_nonsorted(res, 1, TEST_CONTAINER_LIST, test); + res = test_traversal_nonsorted(res, 2, TEST_CONTAINER_HASH, test); + + res = test_traversal_sorted(res, 3, TEST_CONTAINER_LIST, test); + res = test_traversal_sorted(res, 4, TEST_CONTAINER_HASH, test); + + return res; +} + static int unload_module(void) { AST_TEST_UNREGISTER(astobj2_test_1); AST_TEST_UNREGISTER(astobj2_test_2); AST_TEST_UNREGISTER(astobj2_test_3); + AST_TEST_UNREGISTER(astobj2_test_4); return 0; } @@ -711,6 +1977,7 @@ static int load_module(void) AST_TEST_REGISTER(astobj2_test_1); AST_TEST_REGISTER(astobj2_test_2); AST_TEST_REGISTER(astobj2_test_3); + AST_TEST_REGISTER(astobj2_test_4); return AST_MODULE_LOAD_SUCCESS; } |