test_performance.c File Reference

Performance Experimentation Tests. More...

#include "asterisk.h"
#include "asterisk/module.h"
#include "asterisk/cli.h"
#include "asterisk/time.h"
#include "asterisk/astobj2.h"
#include "asterisk/vector.h"
#include "asterisk/utils.h"
#include "asterisk/strings.h"
#include "asterisk/hashtab.h"
#include "asterisk/linkedlists.h"
#include <stdlib.h>

Include dependency graph for test_performance.c:

Go to the source code of this file.

Data Structures
struct	list_node
	A node in the linked list for string lookups. More...

Macros
#define	DEFAULT_DURATION_SEC   10
	The default duration of the performance test in seconds.
#define	DEFAULT_KEY_COUNT   250
	The default number of keys to generate for performance tests.
#define	RANDOM_STRING_ATTEMPTS   100
	The number of attempts for random strings before we give up.
#define	TEST_KEY_LENGTH   32
	The length of each test key.

Functions
static void	__reg_module (void)
static void	__unreg_module (void)
struct ast_module *	AST_MODULE_SELF_SYM (void)
static void	free_random_strings (struct ast_vector_string *vec)
	Frees the memory used by a vector of random strings.
static struct ast_vector_string *	generate_random_strings (int count)
	Generates a vector of random strings to use as keys.
static char *	handle_cli_ao2_string_hash (struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
	Handles the CLI command for testing ao2_container hash string lookups.
static char *	handle_cli_ao2_string_list (struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
	Handles the CLI command for testing ao2_container list string lookups.
static char *	handle_cli_ao2_string_rbtree (struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
	Handles the CLI command for testing ao2_container rbtree string lookups.
static char *	handle_cli_container_key_lookup_all (struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
	Handles the CLI command for running all container key lookup performance tests.
static char *	handle_cli_hashtab_string (struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
	Handles the CLI command for testing hashtab string lookups.
static char *	handle_cli_list_string (struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
	Handle the 'performance test list_string' command.
static char *	handle_cli_vector_bsearch_lookup (struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
	Handles the CLI command for testing vector string binary search lookups.
static char *	handle_cli_vector_linear_lookup (struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
	Handles the CLI command for testing vector string linear search lookups.
static void	hashtab_free_string (void *obj)
	Frees a string object placed into a hashtab.
static int	load_module (void)
	Loads the performance testing module.
static int	next_prime (int n)
	Finds the next prime number greater than or equal to n.
static int	rbtree_str_cmp (void *lhs, void *rhs, int flags)
	Compares two strings for finding in the RBTree.
static int	rbtree_str_sort (const void *lhs, const void *rhs, int flags)
	Compares two strings for sorting in the RBTree.
static int	unload_module (void)
	Unloads the performance testing module.
static int	vector_string_cmp (const void *_a, const void *_b)
	Compares two strings for sorting.

Variables
static struct ast_module_info	__mod_info = { .name = AST_MODULE, .flags = AST_MODFLAG_LOAD_ORDER , .description = "Performance Test Experimentation Module" , .key = ASTERISK_GPL_KEY , .buildopt_sum = AST_BUILDOPT_SUM, .load = load_module, .unload = unload_module, .load_pri = AST_MODPRI_DEFAULT, .support_level = AST_MODULE_SUPPORT_CORE, }
static const struct ast_module_info *	ast_module_info = &__mod_info
static struct ast_cli_entry	cli_performance []
	The CLI commands for performance experimentation testing.

Detailed Description

Performance Experimentation Tests.

Author

Joshua Colp jcolp.nosp@m.@san.nosp@m.goma..nosp@m.com

Definition in file test_performance.c.

Macro Definition Documentation

DEFAULT_DURATION_SEC

#define DEFAULT_DURATION_SEC   10

The default duration of the performance test in seconds.

Definition at line 49 of file test_performance.c.

DEFAULT_KEY_COUNT

#define DEFAULT_KEY_COUNT   250

The default number of keys to generate for performance tests.

Definition at line 46 of file test_performance.c.

RANDOM_STRING_ATTEMPTS

#define RANDOM_STRING_ATTEMPTS   100

The number of attempts for random strings before we give up.

Definition at line 55 of file test_performance.c.

TEST_KEY_LENGTH

#define TEST_KEY_LENGTH   32

The length of each test key.

Definition at line 52 of file test_performance.c.

Function Documentation

__reg_module()

static void __reg_module ( void  )

static

Definition at line 1013 of file test_performance.c.

__unreg_module()

static void __unreg_module ( void  )

static

Definition at line 1013 of file test_performance.c.

AST_MODULE_SELF_SYM()

struct ast_module * AST_MODULE_SELF_SYM

(

void

)

Definition at line 1013 of file test_performance.c.

free_random_strings()

static void free_random_strings ( struct ast_vector_string *  vec )

static

Frees the memory used by a vector of random strings.

The following tests cover the most common usage of containers in Asterisk - a key lookup based on a string which then resolves to an underlying object. The CLI commands assume that the underlying container implementations are working properly and return the requested object. These tests also only test single threaded performance. They do not test concurrent access or thread safety.

Parameters

vec	The vector of random strings to free

Definition at line 69 of file test_performance.c.

{
    AST_VECTOR_RESET(vec, ast_free);
    AST_VECTOR_FREE(vec);
    ast_free(vec);
}

References ast_free, AST_VECTOR_FREE, and AST_VECTOR_RESET.

Referenced by generate_random_strings(), handle_cli_ao2_string_hash(), handle_cli_ao2_string_list(), handle_cli_ao2_string_rbtree(), handle_cli_hashtab_string(), handle_cli_list_string(), handle_cli_vector_bsearch_lookup(), and handle_cli_vector_linear_lookup().

generate_random_strings()

static struct ast_vector_string * generate_random_strings ( int  count )

static

Generates a vector of random strings to use as keys.

Parameters

count

The number of strings to generate

Returns

A vector of random strings, or NULL on failure

Definition at line 81 of file test_performance.c.

{
    struct ast_vector_string *vec;
    struct ao2_container *seen;
    int i;
 
    vec = ast_malloc(sizeof(*vec));
    if (!vec) {
        return NULL;
    }
 
    /* Preallocate the vector to avoid reallocations during insertion */
    if (AST_VECTOR_INIT(vec, count)) {
        ast_free(vec);
        return NULL;
    }
 
    /*
     * To eliminate collissions keep track of seen strings and retry if a collision occurs,
     * since this is just for keeping track of seen we don't care about optimizing the bucket
     * size of the container.
     */
    seen = ast_str_container_alloc_options(AO2_ALLOC_OPT_LOCK_NOLOCK, count);
    if (!seen) {
        free_random_strings(vec);
        return NULL;
    }
 
    for (i = 0; i < count; i++) {
        char buf[TEST_KEY_LENGTH];
        unsigned int attempts = 0;
        char *dup;
 
        /* Generate a random string and retry if it collides with a previously seen string */
        while (1) {
            char *existing;
 
            ast_generate_random_string(buf, sizeof(buf));
 
            existing = ao2_find(seen, buf, OBJ_SEARCH_KEY);
            /* We don't care about the existing string, just that it's not NULL */
            ao2_cleanup(existing);
            if (!existing) {
                break;
            }
 
            /* To prevent infinite loops in case of collisions, limit the number of attempts */
            attempts++;
            if (attempts > RANDOM_STRING_ATTEMPTS) {
                ao2_ref(seen, -1);
                free_random_strings(vec);
                return NULL;
            }
        }
 
        /* The vector takes pointers to strings, so we need to duplicate the buffer */
        dup = ast_strdup(buf);
        if (!dup) {
            ao2_ref(seen, -1);
            free_random_strings(vec);
            return NULL;
        }
 
        ast_str_container_add(seen, dup);
 
        /* This can't fail as the AST_VECTOR_INIT ensured enough space */
        AST_VECTOR_APPEND(vec, dup);
    }
 
    ao2_ref(seen, -1);
 
    return vec;
}

References AO2_ALLOC_OPT_LOCK_NOLOCK, ao2_cleanup, ao2_find, ao2_ref, ast_free, ast_generate_random_string(), ast_malloc, ast_str_container_add(), ast_str_container_alloc_options(), ast_strdup, AST_VECTOR_APPEND, AST_VECTOR_INIT, buf, free_random_strings(), NULL, OBJ_SEARCH_KEY, RANDOM_STRING_ATTEMPTS, and TEST_KEY_LENGTH.

Referenced by handle_cli_ao2_string_hash(), handle_cli_ao2_string_list(), handle_cli_ao2_string_rbtree(), handle_cli_hashtab_string(), handle_cli_list_string(), handle_cli_vector_bsearch_lookup(), and handle_cli_vector_linear_lookup().

handle_cli_ao2_string_hash()

static char * handle_cli_ao2_string_hash ( struct ast_cli_entry *  e, int  cmd, struct ast_cli_args *  a  )

static

Handles the CLI command for testing ao2_container hash string lookups.

Parameters

e	The CLI entry
cmd	The command to execute
a	The CLI arguments

Returns

NULL on success, or an error message on failure

Definition at line 203 of file test_performance.c.

{
    struct ao2_container *container;
    struct ast_vector_string *strings;
    struct timeval start;
    unsigned int count = 0;
    int key_count = DEFAULT_KEY_COUNT;
    int duration_sec = DEFAULT_DURATION_SEC;
    int duration_ms;
    int buckets = 0;
    int i;
 
    switch (cmd) {
    case CLI_INIT:
        e->command = "performance test ao2_string_hash";
        e->usage =
            "Usage: performance test ao2_string_hash [<num_keys>] [<duration_sec>] [<buckets>]\n"
            "       Test the performance of ao2_container hash string key lookups.\n";
        return NULL;
    case CLI_GENERATE:
        return NULL;
    }
 
    if (a->argc > 3) {
        if (sscanf(a->argv[3], "%30d", &key_count) <= 0 || key_count <= 0) {
            ast_cli(a->fd, "Invalid value for num_keys: '%s'\n", a->argv[3]);
            return CLI_FAILURE;
        }
    }
    if (a->argc > 4) {
        if (sscanf(a->argv[4], "%30d", &duration_sec) <= 0 || duration_sec <= 0) {
            ast_cli(a->fd, "Invalid value for duration_sec: '%s'\n", a->argv[4]);
            return CLI_FAILURE;
        }
    }
    if (a->argc > 5) {
        if (sscanf(a->argv[5], "%30d", &buckets) <= 0 || buckets <= 0) {
            ast_cli(a->fd, "Invalid value for buckets: '%s'\n", a->argv[5]);
            return CLI_FAILURE;
        }
    }
    duration_ms = duration_sec * 1000;
    if (!buckets) {
        buckets = next_prime(key_count);
    }
 
    strings = generate_random_strings(key_count);
    if (!strings) {
        ast_cli(a->fd, "Failed to generate random strings\n");
        return CLI_FAILURE;
    }
 
    container = ast_str_container_alloc_options(AO2_ALLOC_OPT_LOCK_NOLOCK, buckets);
    if (!container) {
        ast_cli(a->fd, "Failed to allocate ao2 container\n");
        free_random_strings(strings);
        return CLI_FAILURE;
    }
 
    for (i = 0; i < AST_VECTOR_SIZE(strings); i++) {
        if (ast_str_container_add(container, AST_VECTOR_GET(strings, i))) {
            ast_cli(a->fd, "Failed to add string to container\n");
            ao2_ref(container, -1);
            free_random_strings(strings);
            return CLI_FAILURE;
        }
    }
 
    ast_cli(a->fd, "Beginning ao2_string_hash performance test (%d keys, %d seconds, buckets %d)\n",
        key_count, duration_sec, buckets);
 
    start = ast_tvnow();
    for (;;) {
        int idx = ast_random() % AST_VECTOR_SIZE(strings);
 
        ao2_cleanup(ao2_find(container, AST_VECTOR_GET(strings, idx), OBJ_SEARCH_KEY));
        count++;
 
        if (ast_tvdiff_ms(ast_tvnow(), start) >= duration_ms) {
            break;
        }
    }
 
    ast_cli(a->fd, "ao2_string_hash: %u lookups in %d seconds (%u lookups/sec)\n", count, duration_sec, count / duration_sec);
 
    ao2_ref(container, -1);
    free_random_strings(strings);
 
    return CLI_SUCCESS;
}

References a, AO2_ALLOC_OPT_LOCK_NOLOCK, ao2_cleanup, ao2_find, ao2_ref, ast_cli(), ast_random(), ast_str_container_add(), ast_str_container_alloc_options(), ast_tvdiff_ms(), ast_tvnow(), AST_VECTOR_GET, AST_VECTOR_SIZE, CLI_FAILURE, CLI_GENERATE, CLI_INIT, CLI_SUCCESS, ast_cli_entry::command, container, DEFAULT_DURATION_SEC, DEFAULT_KEY_COUNT, free_random_strings(), generate_random_strings(), next_prime(), NULL, OBJ_SEARCH_KEY, and ast_cli_entry::usage.

Referenced by handle_cli_container_key_lookup_all().

handle_cli_ao2_string_list()

static char * handle_cli_ao2_string_list ( struct ast_cli_entry *  e, int  cmd, struct ast_cli_args *  a  )

static

Handles the CLI command for testing ao2_container list string lookups.

Parameters

e	The CLI entry
cmd	The command to execute
a	The CLI arguments

Returns

NULL on success, or an error message on failure

Definition at line 431 of file test_performance.c.

{
    struct ao2_container *container;
    struct ast_vector_string *strings;
    struct timeval start;
    unsigned int count = 0;
    int key_count = DEFAULT_KEY_COUNT;
    int duration_sec = DEFAULT_DURATION_SEC;
    int duration_ms;
    int i;
 
    switch (cmd) {
    case CLI_INIT:
        e->command = "performance test ao2_string_list";
        e->usage =
            "Usage: performance test ao2_string_list [<num_keys>] [<duration_sec>]\n"
            "       Test the performance of ao2_container list string key lookups.\n";
        return NULL;
    case CLI_GENERATE:
        return NULL;
    }
 
    if (a->argc > 3) {
        if (sscanf(a->argv[3], "%30d", &key_count) <= 0 || key_count <= 0) {
            ast_cli(a->fd, "Invalid value for num_keys: '%s'\n", a->argv[3]);
            return CLI_FAILURE;
        }
    }
    if (a->argc > 4) {
        if (sscanf(a->argv[4], "%30d", &duration_sec) <= 0 || duration_sec <= 0) {
            ast_cli(a->fd, "Invalid value for duration_sec: '%s'\n", a->argv[4]);
            return CLI_FAILURE;
        }
    }
    duration_ms = duration_sec * 1000;
 
    strings = generate_random_strings(key_count);
    if (!strings) {
        ast_cli(a->fd, "Failed to generate random strings\n");
        return CLI_FAILURE;
    }
 
    container = ao2_container_alloc_list(AO2_ALLOC_OPT_LOCK_NOLOCK, 0, rbtree_str_sort, rbtree_str_cmp);
    if (!container) {
        ast_cli(a->fd, "Failed to allocate ao2 list container\n");
        free_random_strings(strings);
        return CLI_FAILURE;
    }
 
    for (i = 0; i < AST_VECTOR_SIZE(strings); i++) {
        const char *key = AST_VECTOR_GET(strings, i);
        char *obj = ao2_alloc_options(strlen(key) + 1, NULL, AO2_ALLOC_OPT_LOCK_NOLOCK);
 
        if (!obj) {
            ast_cli(a->fd, "Failed to allocate object for string\n");
            ao2_ref(container, -1);
            free_random_strings(strings);
            return CLI_FAILURE;
        }
        strcpy(obj, key);
        ao2_link(container, obj);
        ao2_ref(obj, -1);
    }
 
    ast_cli(a->fd, "Beginning ao2_string_list performance test (%d keys, %d seconds)\n",
        key_count, duration_sec);
 
    start = ast_tvnow();
    for (;;) {
        int idx = ast_random() % AST_VECTOR_SIZE(strings);
 
        ao2_cleanup(ao2_find(container, AST_VECTOR_GET(strings, idx), OBJ_SEARCH_KEY));
        count++;
 
        if (ast_tvdiff_ms(ast_tvnow(), start) >= duration_ms) {
            break;
        }
    }
 
    ast_cli(a->fd, "ao2_string_list: %u lookups in %d seconds (%u lookups/sec)\n", count, duration_sec, count / duration_sec);
 
    ao2_ref(container, -1);
    free_random_strings(strings);
 
    return CLI_SUCCESS;
}

References a, AO2_ALLOC_OPT_LOCK_NOLOCK, ao2_alloc_options, ao2_cleanup, ao2_container_alloc_list, ao2_find, ao2_link, ao2_ref, ast_cli(), ast_random(), ast_tvdiff_ms(), ast_tvnow(), AST_VECTOR_GET, AST_VECTOR_SIZE, CLI_FAILURE, CLI_GENERATE, CLI_INIT, CLI_SUCCESS, ast_cli_entry::command, container, DEFAULT_DURATION_SEC, DEFAULT_KEY_COUNT, free_random_strings(), generate_random_strings(), NULL, OBJ_SEARCH_KEY, rbtree_str_cmp(), rbtree_str_sort(), and ast_cli_entry::usage.

Referenced by handle_cli_container_key_lookup_all().

handle_cli_ao2_string_rbtree()

static char * handle_cli_ao2_string_rbtree ( struct ast_cli_entry *  e, int  cmd, struct ast_cli_args *  a  )

static

Handles the CLI command for testing ao2_container rbtree string lookups.

Parameters

e	The CLI entry
cmd	The command to execute
a	The CLI arguments

Returns

NULL on success, or an error message on failure

Definition at line 337 of file test_performance.c.

{
    struct ao2_container *container;
    struct ast_vector_string *strings;
    struct timeval start;
    unsigned int count = 0;
    int key_count = DEFAULT_KEY_COUNT;
    int duration_sec = DEFAULT_DURATION_SEC;
    int duration_ms;
    int i;
 
    switch (cmd) {
    case CLI_INIT:
        e->command = "performance test ao2_string_rbtree";
        e->usage =
            "Usage: performance test ao2_string_rbtree [<num_keys>] [<duration_sec>]\n"
            "       Test the performance of ao2_container rbtree string key lookups.\n";
        return NULL;
    case CLI_GENERATE:
        return NULL;
    }
 
    if (a->argc > 3) {
        if (sscanf(a->argv[3], "%30d", &key_count) <= 0 || key_count <= 0) {
            ast_cli(a->fd, "Invalid value for num_keys: '%s'\n", a->argv[3]);
            return CLI_FAILURE;
        }
    }
    if (a->argc > 4) {
        if (sscanf(a->argv[4], "%30d", &duration_sec) <= 0 || duration_sec <= 0) {
            ast_cli(a->fd, "Invalid value for duration_sec: '%s'\n", a->argv[4]);
            return CLI_FAILURE;
        }
    }
    duration_ms = duration_sec * 1000;
 
    strings = generate_random_strings(key_count);
    if (!strings) {
        ast_cli(a->fd, "Failed to generate random strings\n");
        return CLI_FAILURE;
    }
 
    container = ao2_container_alloc_rbtree(AO2_ALLOC_OPT_LOCK_NOLOCK, 0, rbtree_str_sort, rbtree_str_cmp);
    if (!container) {
        ast_cli(a->fd, "Failed to allocate ao2 rbtree container\n");
        free_random_strings(strings);
        return CLI_FAILURE;
    }
 
    for (i = 0; i < AST_VECTOR_SIZE(strings); i++) {
        const char *key = AST_VECTOR_GET(strings, i);
        char *obj = ao2_alloc_options(strlen(key) + 1, NULL, AO2_ALLOC_OPT_LOCK_NOLOCK);
 
        if (!obj) {
            ast_cli(a->fd, "Failed to allocate object for string\n");
            ao2_ref(container, -1);
            free_random_strings(strings);
            return CLI_FAILURE;
        }
        strcpy(obj, key);
        ao2_link(container, obj);
        ao2_ref(obj, -1);
    }
 
    ast_cli(a->fd, "Beginning ao2_string_rbtree performance test (%d keys, %d seconds)\n",
        key_count, duration_sec);
 
    start = ast_tvnow();
    for (;;) {
        int idx = ast_random() % AST_VECTOR_SIZE(strings);
 
        ao2_cleanup(ao2_find(container, AST_VECTOR_GET(strings, idx), OBJ_SEARCH_KEY));
        count++;
 
        if (ast_tvdiff_ms(ast_tvnow(), start) >= duration_ms) {
            break;
        }
    }
 
    ast_cli(a->fd, "ao2_string_rbtree: %u lookups in %d seconds (%u lookups/sec)\n", count, duration_sec, count / duration_sec);
 
    ao2_ref(container, -1);
    free_random_strings(strings);
 
    return CLI_SUCCESS;
}

References a, AO2_ALLOC_OPT_LOCK_NOLOCK, ao2_alloc_options, ao2_cleanup, ao2_container_alloc_rbtree, ao2_find, ao2_link, ao2_ref, ast_cli(), ast_random(), ast_tvdiff_ms(), ast_tvnow(), AST_VECTOR_GET, AST_VECTOR_SIZE, CLI_FAILURE, CLI_GENERATE, CLI_INIT, CLI_SUCCESS, ast_cli_entry::command, container, DEFAULT_DURATION_SEC, DEFAULT_KEY_COUNT, free_random_strings(), generate_random_strings(), NULL, OBJ_SEARCH_KEY, rbtree_str_cmp(), rbtree_str_sort(), and ast_cli_entry::usage.

Referenced by handle_cli_container_key_lookup_all().

handle_cli_container_key_lookup_all()

static char * handle_cli_container_key_lookup_all ( struct ast_cli_entry *  e, int  cmd, struct ast_cli_args *  a  )

static

Handles the CLI command for running all container key lookup performance tests.

Parameters

e	The CLI entry
cmd	The command to execute
a	The CLI arguments

Returns

NULL on success, or an error message on failure

Definition at line 948 of file test_performance.c.

{
    switch (cmd) {
    case CLI_INIT:
        e->command = "performance test container_key_lookup_all";
        e->usage =
            "Usage: performance test container_key_lookup_all [<num_keys>] [<duration_sec>] [<buckets>]\n"
            "       Run all performance tests.\n";
        return NULL;
    case CLI_GENERATE:
        return NULL;
    }
 
    /*
     * We don't care if any of these fail because each will output a message if this occurs,
     * as well we just pass in the arguments unaltered as none of the tests examine the
     * full command and they also follow the same format as this CLI command -
     * "performance test <name> <arguments>" so there is no weird difference in where the
     * arguments they care about are.
     */
    handle_cli_ao2_string_hash(e, cmd, a);
    handle_cli_ao2_string_rbtree(e, cmd, a);
    handle_cli_ao2_string_list(e, cmd, a);
    handle_cli_hashtab_string(e, cmd, a);
    handle_cli_list_string(e, cmd, a);
    handle_cli_vector_bsearch_lookup(e, cmd, a);
    handle_cli_vector_linear_lookup(e, cmd, a);
 
    return CLI_SUCCESS;
}

References a, CLI_GENERATE, CLI_INIT, CLI_SUCCESS, ast_cli_entry::command, handle_cli_ao2_string_hash(), handle_cli_ao2_string_list(), handle_cli_ao2_string_rbtree(), handle_cli_hashtab_string(), handle_cli_list_string(), handle_cli_vector_bsearch_lookup(), handle_cli_vector_linear_lookup(), NULL, and ast_cli_entry::usage.

handle_cli_hashtab_string()

static char * handle_cli_hashtab_string ( struct ast_cli_entry *  e, int  cmd, struct ast_cli_args *  a  )

static

Handles the CLI command for testing hashtab string lookups.

Parameters

e	The CLI entry
cmd	The command to execute
a	The CLI arguments

Returns

NULL on success, or an error message on failure

Definition at line 534 of file test_performance.c.

{
    struct ast_hashtab *tab;
    struct ast_vector_string *strings;
    struct timeval start;
    unsigned int count = 0;
    int key_count = DEFAULT_KEY_COUNT;
    int duration_sec = DEFAULT_DURATION_SEC;
    int duration_ms;
    int buckets = 0;
    int i;
 
    switch (cmd) {
    case CLI_INIT:
        e->command = "performance test hashtab_string";
        e->usage =
            "Usage: performance test hashtab_string [<num_keys>] [<duration_sec>] [<buckets>]\n"
            "       Test the performance of hashtab string lookups.\n";
        return NULL;
    case CLI_GENERATE:
        return NULL;
    }
 
    if (a->argc > 3) {
        if (sscanf(a->argv[3], "%30d", &key_count) <= 0 || key_count <= 0) {
            ast_cli(a->fd, "Invalid value for num_keys: '%s'\n", a->argv[3]);
            return CLI_FAILURE;
        }
    }
    if (a->argc > 4) {
        if (sscanf(a->argv[4], "%30d", &duration_sec) <= 0 || duration_sec <= 0) {
            ast_cli(a->fd, "Invalid value for duration_sec: '%s'\n", a->argv[4]);
            return CLI_FAILURE;
        }
    }
    if (a->argc > 5) {
        if (sscanf(a->argv[5], "%30d", &buckets) <= 0 || buckets <= 0) {
            ast_cli(a->fd, "Invalid value for buckets: '%s'\n", a->argv[5]);
            return CLI_FAILURE;
        }
    }
    duration_ms = duration_sec * 1000;
    if (!buckets) {
        buckets = next_prime(key_count);
    }
 
    strings = generate_random_strings(key_count);
    if (!strings) {
        ast_cli(a->fd, "Failed to generate random strings\n");
        return CLI_FAILURE;
    }
 
    tab = ast_hashtab_create(buckets, ast_hashtab_compare_strings, NULL, NULL, ast_hashtab_hash_string, 0);
    if (!tab) {
        ast_cli(a->fd, "Failed to allocate hashtab\n");
        free_random_strings(strings);
        return CLI_FAILURE;
    }
 
    for (i = 0; i < AST_VECTOR_SIZE(strings); i++) {
        char *dup = ast_strdup(AST_VECTOR_GET(strings, i));
 
        if (!dup || !ast_hashtab_insert_immediate(tab, dup)) {
            ast_cli(a->fd, "Failed to insert string into hashtab\n");
            ast_free(dup);
            ast_hashtab_destroy(tab, hashtab_free_string);
            free_random_strings(strings);
            return CLI_FAILURE;
        }
    }
 
    ast_cli(a->fd, "Beginning hashtab_string performance test (%d keys, %d seconds, buckets %d)\n",
        key_count, duration_sec, buckets);
 
    start = ast_tvnow();
    for (;;) {
        int idx = ast_random() % AST_VECTOR_SIZE(strings);
 
        ast_hashtab_lookup(tab, AST_VECTOR_GET(strings, idx));
        count++;
 
        if (ast_tvdiff_ms(ast_tvnow(), start) >= duration_ms) {
            break;
        }
    }
 
    ast_cli(a->fd, "hashtab_string: %u lookups in %d seconds (%u lookups/sec)\n", count, duration_sec, count / duration_sec);
 
    ast_hashtab_destroy(tab, hashtab_free_string);
    free_random_strings(strings);
 
    return CLI_SUCCESS;
}

References a, ast_cli(), ast_free, ast_hashtab_compare_strings(), ast_hashtab_create, ast_hashtab_destroy(), ast_hashtab_hash_string(), ast_hashtab_insert_immediate, ast_hashtab_lookup(), ast_random(), ast_strdup, ast_tvdiff_ms(), ast_tvnow(), AST_VECTOR_GET, AST_VECTOR_SIZE, CLI_FAILURE, CLI_GENERATE, CLI_INIT, CLI_SUCCESS, ast_cli_entry::command, DEFAULT_DURATION_SEC, DEFAULT_KEY_COUNT, free_random_strings(), generate_random_strings(), hashtab_free_string(), next_prime(), NULL, and ast_cli_entry::usage.

Referenced by handle_cli_container_key_lookup_all().

handle_cli_list_string()

static char * handle_cli_list_string ( struct ast_cli_entry *  e, int  cmd, struct ast_cli_args *  a  )

static

Handle the 'performance test list_string' command.

Parameters

e	The CLI entry
cmd	The command to execute
a	The CLI arguments

Returns

CLI_SUCCESS on success, CLI_FAILURE on error

Definition at line 643 of file test_performance.c.

{
    AST_LIST_HEAD_NOLOCK(list_head, list_node) head;
    struct ast_vector_string *strings;
    struct list_node *node;
    struct timeval start;
    unsigned int count = 0;
    int key_count = DEFAULT_KEY_COUNT;
    int duration_sec = DEFAULT_DURATION_SEC;
    int duration_ms;
    int i;
 
    switch (cmd) {
    case CLI_INIT:
        e->command = "performance test list_string";
        e->usage =
            "Usage: performance test list_string [<num_keys>] [<duration_sec>]\n"
            "       Test the performance of linked list string key lookups.\n";
        return NULL;
    case CLI_GENERATE:
        return NULL;
    }
 
    if (a->argc > 3) {
        if (sscanf(a->argv[3], "%30d", &key_count) <= 0 || key_count <= 0) {
            ast_cli(a->fd, "Invalid value for num_keys: '%s'\n", a->argv[3]);
            return CLI_FAILURE;
        }
    }
    if (a->argc > 4) {
        if (sscanf(a->argv[4], "%30d", &duration_sec) <= 0 || duration_sec <= 0) {
            ast_cli(a->fd, "Invalid value for duration_sec: '%s'\n", a->argv[4]);
            return CLI_FAILURE;
        }
    }
    duration_ms = duration_sec * 1000;
 
    strings = generate_random_strings(key_count);
    if (!strings) {
        ast_cli(a->fd, "Failed to generate random strings\n");
        return CLI_FAILURE;
    }
 
    AST_LIST_HEAD_INIT_NOLOCK(&head);
 
    for (i = 0; i < AST_VECTOR_SIZE(strings); i++) {
        node = ast_calloc(1, sizeof(*node));
        if (!node) {
            ast_cli(a->fd, "Failed to allocate list node\n");
            goto cleanup;
        }
 
        node->str = ast_strdup(AST_VECTOR_GET(strings, i));
        if (!node->str) {
            ast_free(node);
            ast_cli(a->fd, "Failed to duplicate list node string\n");
            goto cleanup;
        }
 
        AST_LIST_INSERT_TAIL(&head, node, list);
    }
 
    ast_cli(a->fd, "Beginning list_string performance test (%d keys, %d seconds)\n",
        key_count, duration_sec);
 
    start = ast_tvnow();
    for (;;) {
        int idx = ast_random() % AST_VECTOR_SIZE(strings);
 
        AST_LIST_TRAVERSE(&head, node, list) {
            if (!strcmp(node->str, AST_VECTOR_GET(strings, idx))) {
                break;
            }
        }
        count++;
 
        if (ast_tvdiff_ms(ast_tvnow(), start) >= duration_ms) {
            break;
        }
    }
 
    ast_cli(a->fd, "list_string: %u lookups in %d seconds (%u lookups/sec)\n", count, duration_sec, count / duration_sec);
 
cleanup:
    while ((node = AST_LIST_REMOVE_HEAD(&head, list))) {
        ast_free(node->str);
        ast_free(node);
    }
 
    free_random_strings(strings);
 
    return CLI_SUCCESS;
}

References a, ast_calloc, ast_cli(), ast_free, AST_LIST_HEAD_INIT_NOLOCK, AST_LIST_HEAD_NOLOCK, AST_LIST_INSERT_TAIL, AST_LIST_REMOVE_HEAD, AST_LIST_TRAVERSE, ast_random(), ast_strdup, ast_tvdiff_ms(), ast_tvnow(), AST_VECTOR_GET, AST_VECTOR_SIZE, cleanup(), CLI_FAILURE, CLI_GENERATE, CLI_INIT, CLI_SUCCESS, ast_cli_entry::command, DEFAULT_DURATION_SEC, DEFAULT_KEY_COUNT, free_random_strings(), generate_random_strings(), NULL, and ast_cli_entry::usage.

Referenced by handle_cli_container_key_lookup_all().

handle_cli_vector_bsearch_lookup()

static char * handle_cli_vector_bsearch_lookup ( struct ast_cli_entry *  e, int  cmd, struct ast_cli_args *  a  )

static

Handles the CLI command for testing vector string binary search lookups.

Parameters

e	The CLI entry
cmd	The command to execute
a	The CLI arguments

Returns

NULL on success, or an error message on failure

Definition at line 744 of file test_performance.c.

{
    struct ast_vector_string *strings;
    struct ast_vector_string vec;
    struct timeval start;
    unsigned int count = 0;
    int key_count = DEFAULT_KEY_COUNT;
    int duration_sec = DEFAULT_DURATION_SEC;
    int duration_ms;
    int i;
 
    switch (cmd) {
    case CLI_INIT:
        e->command = "performance test vector_string_bsearch";
        e->usage =
            "Usage: performance test vector_string_bsearch [<num_keys>] [<duration_sec>]\n"
            "       Test the performance of vector string key binary search lookups.\n";
        return NULL;
    case CLI_GENERATE:
        return NULL;
    }
 
    if (a->argc > 3) {
        if (sscanf(a->argv[3], "%30d", &key_count) <= 0 || key_count <= 0) {
            ast_cli(a->fd, "Invalid value for num_keys: '%s'\n", a->argv[3]);
            return CLI_FAILURE;
        }
    }
    if (a->argc > 4) {
        if (sscanf(a->argv[4], "%30d", &duration_sec) <= 0 || duration_sec <= 0) {
            ast_cli(a->fd, "Invalid value for duration_sec: '%s'\n", a->argv[4]);
            return CLI_FAILURE;
        }
    }
    duration_ms = duration_sec * 1000;
 
    strings = generate_random_strings(key_count);
    if (!strings) {
        ast_cli(a->fd, "Failed to generate random strings\n");
        return CLI_FAILURE;
    }
 
    if (AST_VECTOR_INIT(&vec, key_count)) {
        ast_cli(a->fd, "Failed to initialize vector\n");
        free_random_strings(strings);
        return CLI_FAILURE;
    }
 
    for (i = 0; i < AST_VECTOR_SIZE(strings); i++) {
        char *dup = ast_strdup(AST_VECTOR_GET(strings, i));
 
        if (!dup) {
            ast_cli(a->fd, "Failed to add string to vector\n");
            AST_VECTOR_RESET(&vec, ast_free);
            AST_VECTOR_FREE(&vec);
            free_random_strings(strings);
            return CLI_FAILURE;
        }
 
        /* This can't fail as we're appending to a vector that we know is large enough */
        AST_VECTOR_APPEND(&vec, dup);
    }
 
    AST_VECTOR_SORT(&vec, vector_string_cmp);
 
    ast_cli(a->fd, "Beginning vector_string_bsearch performance test (%d keys, %d seconds)\n",
        key_count, duration_sec);
 
    start = ast_tvnow();
    for (;;) {
        int idx = ast_random() % AST_VECTOR_SIZE(strings);
        const char **key;
 
        /*
         * Unlike the other tests this actually stores the result in a variable and uses it
         * for determining if the count should be increased. This is done to ensure the compiler
         * doesn't pull some funny business and optimize away the bsearch call.
         */
        key = AST_VECTOR_BSEARCH(&vec, AST_VECTOR_GET(strings, idx), vector_string_cmp);
        if (key) {
            count++;
        }
 
        if (ast_tvdiff_ms(ast_tvnow(), start) >= duration_ms) {
            break;
        }
    }
 
    ast_cli(a->fd, "vector_string_bsearch: %u lookups in %d seconds (%u lookups/sec)\n", count, duration_sec, count / duration_sec);
 
    AST_VECTOR_RESET(&vec, ast_free);
    AST_VECTOR_FREE(&vec);
    free_random_strings(strings);
 
    return CLI_SUCCESS;
}

References a, ast_cli(), ast_free, ast_random(), ast_strdup, ast_tvdiff_ms(), ast_tvnow(), AST_VECTOR_APPEND, AST_VECTOR_BSEARCH, AST_VECTOR_FREE, AST_VECTOR_GET, AST_VECTOR_INIT, AST_VECTOR_RESET, AST_VECTOR_SIZE, AST_VECTOR_SORT, CLI_FAILURE, CLI_GENERATE, CLI_INIT, CLI_SUCCESS, ast_cli_entry::command, DEFAULT_DURATION_SEC, DEFAULT_KEY_COUNT, free_random_strings(), generate_random_strings(), NULL, ast_cli_entry::usage, and vector_string_cmp().

Referenced by handle_cli_container_key_lookup_all().

handle_cli_vector_linear_lookup()

static char * handle_cli_vector_linear_lookup ( struct ast_cli_entry *  e, int  cmd, struct ast_cli_args *  a  )

static

Handles the CLI command for testing vector string linear search lookups.

Parameters

e	The CLI entry
cmd	The command to execute
a	The CLI arguments

Returns

NULL on success, or an error message on failure

Definition at line 848 of file test_performance.c.

{
    struct ast_vector_string *strings;
    struct ast_vector_string vec;
    struct timeval start;
    unsigned int count = 0;
    const char *target;
    int key_count = DEFAULT_KEY_COUNT;
    int duration_sec = DEFAULT_DURATION_SEC;
    int duration_ms;
    int i;
 
    switch (cmd) {
    case CLI_INIT:
        e->command = "performance test vector_string_linear";
        e->usage =
            "Usage: performance test vector_string_linear [<num_keys>] [<duration_sec>]\n"
            "       Test the performance of vector string linear search lookups.\n";
        return NULL;
    case CLI_GENERATE:
        return NULL;
    }
 
    if (a->argc > 3) {
        if (sscanf(a->argv[3], "%30d", &key_count) <= 0 || key_count <= 0) {
            ast_cli(a->fd, "Invalid value for num_keys: '%s'\n", a->argv[3]);
            return CLI_FAILURE;
        }
    }
    if (a->argc > 4) {
        if (sscanf(a->argv[4], "%30d", &duration_sec) <= 0 || duration_sec <= 0) {
            ast_cli(a->fd, "Invalid value for duration_sec: '%s'\n", a->argv[4]);
            return CLI_FAILURE;
        }
    }
    duration_ms = duration_sec * 1000;
 
    strings = generate_random_strings(key_count);
    if (!strings) {
        ast_cli(a->fd, "Failed to generate random strings\n");
        return CLI_FAILURE;
    }
 
    if (AST_VECTOR_INIT(&vec, key_count)) {
        ast_cli(a->fd, "Failed to initialize vector\n");
        free_random_strings(strings);
        return CLI_FAILURE;
    }
 
    for (i = 0; i < AST_VECTOR_SIZE(strings); i++) {
        char *dup = ast_strdup(AST_VECTOR_GET(strings, i));
 
        if (!dup) {
            ast_cli(a->fd, "Failed to add string to vector\n");
            AST_VECTOR_RESET(&vec, ast_free);
            AST_VECTOR_FREE(&vec);
            free_random_strings(strings);
            return CLI_FAILURE;
        }
 
        /* This can't fail as we're appending to a vector that we know is large enough */
        AST_VECTOR_APPEND(&vec, dup);
    }
 
    ast_cli(a->fd, "Beginning vector_string_linear performance test (%d keys, %d seconds)\n",
        key_count, duration_sec);
 
    start = ast_tvnow();
    for (;;) {
        int idx = ast_random() % AST_VECTOR_SIZE(strings);
 
        target = AST_VECTOR_GET(strings, idx);
        for (i = 0; i < AST_VECTOR_SIZE(&vec); i++) {
            if (!strcmp(AST_VECTOR_GET(&vec, i), target)) {
                break;
            }
        }
        count++;
 
        if (ast_tvdiff_ms(ast_tvnow(), start) >= duration_ms) {
            break;
        }
    }
 
    ast_cli(a->fd, "vector_string_linear: %u lookups in %d seconds (%u lookups/sec)\n", count, duration_sec, count / duration_sec);
 
    AST_VECTOR_RESET(&vec, ast_free);
    AST_VECTOR_FREE(&vec);
    free_random_strings(strings);
 
    return CLI_SUCCESS;
}

References a, ast_cli(), ast_free, ast_random(), ast_strdup, ast_tvdiff_ms(), ast_tvnow(), AST_VECTOR_APPEND, AST_VECTOR_FREE, AST_VECTOR_GET, AST_VECTOR_INIT, AST_VECTOR_RESET, AST_VECTOR_SIZE, CLI_FAILURE, CLI_GENERATE, CLI_INIT, CLI_SUCCESS, ast_cli_entry::command, DEFAULT_DURATION_SEC, DEFAULT_KEY_COUNT, free_random_strings(), generate_random_strings(), NULL, and ast_cli_entry::usage.

Referenced by handle_cli_container_key_lookup_all().

hashtab_free_string()

static void hashtab_free_string ( void *  obj )

static

Frees a string object placed into a hashtab.

Parameters

obj	The string object to free

Definition at line 522 of file test_performance.c.

{
    ast_free(obj);
}

References ast_free.

Referenced by handle_cli_hashtab_string().

load_module()

static int load_module ( void  )

static

Loads the performance testing module.

Returns

AST_MODULE_LOAD_SUCCESS on success

Definition at line 1007 of file test_performance.c.

{
    ast_cli_register_multiple(cli_performance, ARRAY_LEN(cli_performance));
    return AST_MODULE_LOAD_SUCCESS;
}

References ARRAY_LEN, ast_cli_register_multiple, AST_MODULE_LOAD_SUCCESS, and cli_performance.

next_prime()

static int next_prime ( int  n )

static

Finds the next prime number greater than or equal to n.

Parameters

n	The number to find the next prime for

Returns

The next prime number

Definition at line 173 of file test_performance.c.

{
    /*
     * The lowest prime number is 2. It's also the only even prime number, that fact
     * is of absolutely no relevance to this module but I put it here just for fun
     */
    if (n <= 2) {
        return 2;
    }
 
    /* If it's divisible by 2, increment to the next odd number so we can find the next prime easier */
    if (n % 2 == 0) {
        n++;
    }
 
    /* Loop until we find a prime number */
    while (!ast_is_prime(n)) {
        n += 2;
    }
 
    return n;
}

References ast_is_prime().

Referenced by handle_cli_ao2_string_hash(), and handle_cli_hashtab_string().

rbtree_str_cmp()

static int rbtree_str_cmp ( void *  lhs, void *  rhs, int  flags  )

static

Compares two strings for finding in the RBTree.

Parameters

lhs	The first string to compare
rhs	The second string to compare
flags	The search flags

Returns

The result of the comparison

Definition at line 317 of file test_performance.c.

{
    int cmp = 0;
 
    if ((flags & OBJ_SEARCH_MASK) == OBJ_SEARCH_PARTIAL_KEY) {
        cmp = strncmp(lhs, rhs, strlen(rhs));
    } else {
        cmp = strcmp(lhs, rhs);
    }
 
    return cmp ? 0 : CMP_MATCH;
}

References CMP_MATCH, OBJ_SEARCH_MASK, and OBJ_SEARCH_PARTIAL_KEY.

Referenced by handle_cli_ao2_string_list(), and handle_cli_ao2_string_rbtree().

rbtree_str_sort()

static int rbtree_str_sort ( const void *  lhs, const void *  rhs, int  flags  )

static

Compares two strings for sorting in the RBTree.

Parameters

lhs	The first string to compare
rhs	The second string to compare
flags	The search flags

Returns

The result of the comparison

Definition at line 301 of file test_performance.c.

{
    if ((flags & OBJ_SEARCH_MASK) == OBJ_SEARCH_PARTIAL_KEY) {
        return strncmp(lhs, rhs, strlen(rhs));
    } else {
        return strcmp(lhs, rhs);
    }
}

References OBJ_SEARCH_MASK, and OBJ_SEARCH_PARTIAL_KEY.

Referenced by handle_cli_ao2_string_list(), and handle_cli_ao2_string_rbtree().

unload_module()

static int unload_module ( void  )

static

Unloads the performance testing module.

Returns

0 on success

Definition at line 997 of file test_performance.c.

{
    ast_cli_unregister_multiple(cli_performance, ARRAY_LEN(cli_performance));
    return 0;
}

References ARRAY_LEN, ast_cli_unregister_multiple(), and cli_performance.

vector_string_cmp()

static int vector_string_cmp ( const void *  _a, const void *  _b  )

static

Compares two strings for sorting.

Parameters

a	The first string to compare
b	The second string to compare

Returns

The result of the comparison

Definition at line 161 of file test_performance.c.

{
    const char *a = *(const char **)_a;
    const char *b = *(const char **)_b;
    return strcmp(a, b);
}

References a, and b.

Referenced by handle_cli_vector_bsearch_lookup().

Variable Documentation

__mod_info

struct ast_module_info __mod_info = { .name = AST_MODULE, .flags = AST_MODFLAG_LOAD_ORDER , .description = "Performance Test Experimentation Module" , .key = ASTERISK_GPL_KEY , .buildopt_sum = AST_BUILDOPT_SUM, .load = load_module, .unload = unload_module, .load_pri = AST_MODPRI_DEFAULT, .support_level = AST_MODULE_SUPPORT_CORE, }

static

Definition at line 1013 of file test_performance.c.

ast_module_info

const struct ast_module_info* ast_module_info = &__mod_info

static

Definition at line 1013 of file test_performance.c.

cli_performance

struct ast_cli_entry cli_performance[]

static

The CLI commands for performance experimentation testing.

Definition at line 982 of file test_performance.c.

                                                {
    AST_CLI_DEFINE(handle_cli_container_key_lookup_all, "Run all performance tests"),
    AST_CLI_DEFINE(handle_cli_ao2_string_hash, "Test the performance of ao2_container hash string lookups"),
    AST_CLI_DEFINE(handle_cli_ao2_string_rbtree, "Test the performance of ao2_container rbtree string lookups"),
    AST_CLI_DEFINE(handle_cli_ao2_string_list, "Test the performance of ao2_container list string lookups"),
    AST_CLI_DEFINE(handle_cli_hashtab_string, "Test the performance of hashtab string lookups"),
    AST_CLI_DEFINE(handle_cli_list_string, "Test the performance of linked list string lookups"),
    AST_CLI_DEFINE(handle_cli_vector_bsearch_lookup, "Test the performance of vector string binary search lookups"),
    AST_CLI_DEFINE(handle_cli_vector_linear_lookup, "Test the performance of vector string linear search lookups"),
};

Referenced by load_module(), and unload_module().