Changeset 6099


Ignore:
Timestamp:
Nov 6, 2019 6:17:53 AM (12 days ago)
Author:
riza
Message:

Close #2249: Use sorted linked list for timer implementation.

Location:
pjproject/trunk/pjlib
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • pjproject/trunk/pjlib/include/pj/config.h

    r6058 r6099  
    544544 
    545545/** 
    546  * Enable timer heap debugging facility. When this is enabled, application 
    547  * can call pj_timer_heap_dump() to show the contents of the timer heap 
     546 * Enable timer debugging facility. When this is enabled, application 
     547 * can call pj_timer_heap_dump() to show the contents of the timer 
    548548 * along with the source location where the timer entries were scheduled. 
    549549 * See https://trac.pjsip.org/repos/ticket/1527 for more info. 
     
    557557 
    558558/** 
    559  * If enabled, the timer heap will keep internal copies of the timer entries. 
    560  * This will increase the robustness and stability of the timer heap (against 
     559 * If enabled, the timer will keep internal copies of the timer entries. 
     560 * This will increase the robustness and stability of the timer (against 
    561561 * accidental modification or premature deallocation of the timer entries) and 
    562562 * makes it easier to troubleshoot any timer related issues, with the overhead 
     
    571571 * Default: 1 (enabled) 
    572572 */ 
    573 #ifndef PJ_TIMER_HEAP_USE_COPY 
    574 #  define PJ_TIMER_HEAP_USE_COPY    1 
    575 #endif 
    576  
     573#ifndef PJ_TIMER_USE_COPY 
     574#  define PJ_TIMER_USE_COPY    1 
     575#endif 
     576 
     577 
     578/** 
     579 * If enabled, the timer use sorted linked list instead of binary heap tree 
     580 * structure. Note that using sorted linked list is intended for debugging 
     581 * purposes and will hamper performance significantly when scheduling large 
     582 * number of entries. 
     583 * 
     584 * Default: 0 (Use binary heap tree) 
     585 */ 
     586#ifndef PJ_TIMER_USE_LINKED_LIST 
     587#  define PJ_TIMER_USE_LINKED_LIST    0 
     588#endif 
    577589 
    578590/** 
  • pjproject/trunk/pjlib/include/pj/timer.h

    r6058 r6099  
    2626#include <pj/types.h> 
    2727#include <pj/lock.h> 
     28 
     29#if PJ_TIMER_USE_LINKED_LIST 
     30#  include <pj/list.h> 
     31#endif 
    2832 
    2933PJ_BEGIN_DECL 
     
    8993typedef struct pj_timer_entry 
    9094{ 
     95#if !PJ_TIMER_USE_COPY && PJ_TIMER_USE_LINKED_LIST 
     96    /** 
     97    * Standard list members. 
     98    */ 
     99    PJ_DECL_LIST_MEMBER(struct pj_timer_entry); 
     100#endif 
     101 
    91102    /**  
    92103     * User data to be associated with this entry.  
     
    114125    pj_timer_id_t _timer_id; 
    115126 
    116 #if !PJ_TIMER_HEAP_USE_COPY 
     127#if !PJ_TIMER_USE_COPY 
    117128    /**  
    118129     * The future time when the timer expires, which the value is updated 
  • pjproject/trunk/pjlib/src/pj/timer.c

    r6067 r6099  
    5151 * the timer heap will simply remove the destroyed entry (and print log) 
    5252 * and resume normally. 
    53  * This setting only works if PJ_TIMER_HEAP_USE_COPY is enabled. 
     53 * This setting only works if PJ_TIMER_USE_COPY is enabled. 
    5454 */ 
    55 #define ASSERT_IF_ENTRY_DESTROYED (PJ_TIMER_HEAP_USE_COPY? 0: 0) 
     55#define ASSERT_IF_ENTRY_DESTROYED (PJ_TIMER_USE_COPY? 0: 0) 
    5656 
    5757 
     
    6363}; 
    6464 
    65 #if PJ_TIMER_HEAP_USE_COPY 
     65#if PJ_TIMER_USE_COPY 
    6666 
    6767/* Duplicate/copy of the timer entry. */ 
    6868typedef struct pj_timer_entry_dup 
    6969{ 
     70#if PJ_TIMER_USE_LINKED_LIST 
     71    /** 
     72    * Standard list members. 
     73    */ 
     74    PJ_DECL_LIST_MEMBER(struct pj_timer_entry_dup); 
     75#endif 
     76 
    7077    /** 
    7178     * The duplicate copy. 
     
    141148     */ 
    142149    pj_timer_entry_dup **heap; 
     150 
     151#if PJ_TIMER_USE_LINKED_LIST 
     152    /** 
     153    * If timer heap uses linked list, then this will represent the head of 
     154    * the list. 
     155    */ 
     156    pj_timer_entry_dup head_list; 
     157#endif 
    143158 
    144159    /** 
     
    289304{ 
    290305    pj_timer_entry_dup *removed_node = ht->heap[slot]; 
    291      
     306 
    292307    // Return this timer id to the freelist. 
    293308    push_freelist( ht, GET_FIELD(removed_node, _timer_id) ); 
     
    321336    GET_FIELD(removed_node, _timer_id) = -1; 
    322337 
     338#if !PJ_TIMER_USE_LINKED_LIST 
    323339    // Only try to reheapify if we're not deleting the last entry. 
    324340     
     
    344360        } 
    345361    } 
    346      
     362#else 
     363    pj_list_erase(removed_node); 
     364#endif 
     365 
    347366    return removed_node; 
    348367} 
     
    352371    // All the containers will double in size from max_size_ 
    353372    size_t new_size = ht->max_size * 2; 
     373#if PJ_TIMER_USE_COPY 
    354374    pj_timer_entry_dup *new_timer_dups = 0; 
     375#endif 
    355376    pj_timer_id_t *new_timer_ids; 
    356377    pj_size_t i; 
    357378    pj_timer_entry_dup **new_heap = 0; 
     379 
     380#if PJ_TIMER_USE_LINKED_LIST 
     381    pj_timer_entry_dup *tmp_dup = NULL; 
     382    pj_timer_entry_dup *new_dup; 
     383#endif 
    358384     
    359385    PJ_LOG(6,(THIS_FILE, "Growing heap size from %d to %d", 
     
    366392        return PJ_ENOMEM; 
    367393     
    368 #if PJ_TIMER_HEAP_USE_COPY 
     394#if PJ_TIMER_USE_COPY 
    369395    // Grow the array of timer copies. 
    370396     
     
    387413    memcpy(new_heap, ht->heap, ht->max_size * sizeof(pj_timer_entry *)); 
    388414#endif 
     415 
     416#if PJ_TIMER_USE_LINKED_LIST 
     417    tmp_dup = ht->head_list.next; 
     418    pj_list_init(&ht->head_list); 
     419    for (; tmp_dup != &ht->head_list; tmp_dup = tmp_dup->next) 
     420    { 
     421        int slot = ht->timer_ids[GET_FIELD(tmp_dup, _timer_id)]; 
     422        new_dup = new_heap[slot]; 
     423        pj_list_push_back(&ht->head_list, new_dup); 
     424    } 
     425#endif 
     426 
    389427    ht->heap = new_heap; 
    390428     
     
    417455    pj_timer_entry_dup *timer_copy; 
    418456 
     457#if PJ_TIMER_USE_LINKED_LIST 
     458    pj_timer_entry_dup *tmp_node = NULL; 
     459#endif 
     460 
    419461    if (ht->cur_size + 2 >= ht->max_size) { 
    420462        pj_status_t status = grow_heap(ht); 
     
    424466 
    425467    timer_copy = GET_TIMER(ht, new_node); 
    426 #if PJ_TIMER_HEAP_USE_COPY     
     468#if PJ_TIMER_USE_COPY 
    427469    // Create a duplicate of the timer entry. 
    428470    pj_bzero(timer_copy, sizeof(*timer_copy)); 
     
    430472    timer_copy->entry = new_node; 
    431473#endif 
     474 
     475#if PJ_TIMER_USE_LINKED_LIST 
     476    pj_list_init(timer_copy); 
     477#endif 
     478 
    432479    timer_copy->_timer_value = *future_time; 
    433480 
    434     reheap_up( ht, timer_copy, ht->cur_size, HEAP_PARENT(ht->cur_size)); 
     481#if !PJ_TIMER_USE_LINKED_LIST 
     482    reheap_up(ht, timer_copy, ht->cur_size, HEAP_PARENT(ht->cur_size)); 
     483#else 
     484    if (ht->cur_size == 0) { 
     485        pj_list_push_back(&ht->head_list, timer_copy); 
     486    } else if (PJ_TIME_VAL_GTE(*future_time, 
     487                               ht->head_list.prev->_timer_value)) 
     488    { 
     489        /* Insert the max value to the end of the list. */ 
     490        pj_list_insert_before(&ht->head_list, timer_copy); 
     491    } else { 
     492        tmp_node = ht->head_list.next; 
     493        while (tmp_node->next != &ht->head_list && 
     494               PJ_TIME_VAL_GT(*future_time, tmp_node->_timer_value)) 
     495        { 
     496            tmp_node = tmp_node->next; 
     497        } 
     498        if (PJ_TIME_VAL_LT(*future_time, tmp_node->_timer_value)) { 
     499            pj_list_insert_before(tmp_node, timer_copy); 
     500        } else { 
     501            pj_list_insert_after(tmp_node, timer_copy); 
     502        } 
     503    } 
     504    copy_node(ht, new_node->_timer_id-1, timer_copy); 
     505#endif 
    435506    ht->cur_size++; 
    436507 
     
    547618        return PJ_ENOMEM; 
    548619 
    549 #if PJ_TIMER_HEAP_USE_COPY 
     620#if PJ_TIMER_USE_COPY 
    550621    // Create the timer entry copies array. 
    551622    ht->timer_dups = (pj_timer_entry_dup*) 
     
    567638        ht->timer_ids[i] = -((pj_timer_id_t) (i + 1)); 
    568639 
     640#if PJ_TIMER_USE_LINKED_LIST 
     641    pj_list_init(&ht->head_list); 
     642#endif 
     643 
    569644    *p_heap = ht; 
    570645    return PJ_SUCCESS; 
     
    610685    entry->user_data = user_data; 
    611686    entry->cb = cb; 
    612 #if !PJ_TIMER_HEAP_USE_COPY 
     687#if !PJ_TIMER_USE_COPY 
    613688    entry->_grp_lock = NULL; 
    614689#endif 
     
    772847{ 
    773848    pj_time_val now; 
     849    pj_time_val min_time_node = {0,0}; 
    774850    unsigned count; 
     851    pj_timer_id_t slot = 0; 
    775852 
    776853    PJ_ASSERT_RETURN(ht, 0); 
     
    786863    pj_gettickcount(&now); 
    787864 
     865    if (ht->cur_size) { 
     866#if PJ_TIMER_USE_LINKED_LIST 
     867        slot = ht->timer_ids[GET_FIELD(ht->head_list.next, _timer_id)]; 
     868#endif 
     869        min_time_node = ht->heap[slot]->_timer_value; 
     870    } 
     871 
    788872    while ( ht->cur_size &&  
    789             PJ_TIME_VAL_LTE(ht->heap[0]->_timer_value, now) && 
     873            PJ_TIME_VAL_LTE(min_time_node, now) && 
    790874            count < ht->max_entries_per_poll )  
    791875    { 
    792         pj_timer_entry_dup *node = remove_node(ht, 0); 
     876        pj_timer_entry_dup *node = remove_node(ht, slot); 
    793877        pj_timer_entry *entry = GET_ENTRY(node); 
    794878        /* Avoid re-use of this timer until the callback is done. */ 
     
    835919        /* Now, the timer is really free for re-use. */ 
    836920        ///push_freelist(ht, node_timer_id); 
     921 
     922        if (ht->cur_size) { 
     923#if PJ_TIMER_USE_LINKED_LIST 
     924            slot = ht->timer_ids[GET_FIELD(ht->head_list.next, _timer_id)]; 
     925#endif 
     926            min_time_node = ht->heap[slot]->_timer_value; 
     927        } 
    837928    } 
    838929    if (ht->cur_size && next_delay) { 
     
    880971 
    881972    if (ht->cur_size) { 
     973#if PJ_TIMER_USE_LINKED_LIST 
     974        pj_timer_entry_dup *tmp_dup; 
     975#else 
    882976        unsigned i; 
     977#endif 
    883978        pj_time_val now; 
    884979 
     
    889984        pj_gettickcount(&now); 
    890985 
    891         for (i=0; i<(unsigned)ht->cur_size; ++i) { 
     986#if !PJ_TIMER_USE_LINKED_LIST 
     987        for (i=0; i<(unsigned)ht->cur_size; ++i) 
     988        { 
    892989            pj_timer_entry_dup *e = ht->heap[i]; 
     990#else 
     991        for (tmp_dup = ht->head_list.next; tmp_dup != &ht->head_list; 
     992             tmp_dup = tmp_dup->next) 
     993        { 
     994            pj_timer_entry_dup *e = tmp_dup; 
     995#endif 
     996 
    893997            pj_time_val delta; 
    894998 
  • pjproject/trunk/pjlib/src/pjlib-test/timer.c

    r6059 r6099  
    208208 */ 
    209209#define RANDOMIZED_TEST 1 
    210 #define SIMULATE_CRASH  PJ_TIMER_HEAP_USE_COPY 
     210#define SIMULATE_CRASH  PJ_TIMER_USE_COPY 
    211211 
    212212#if RANDOMIZED_TEST 
     
    231231#define ST_ENTRY_GROUP_LOCK_COUNT   1 
    232232 
     233#define BT_ENTRY_COUNT 100000 
     234#define BT_ENTRY_SHOW_START 100 
     235#define BT_ENTRY_SHOW_MULT 10 
     236#define BT_REPEAT_RANDOM_TEST 4 
     237#define BT_REPEAT_INC_TEST 4 
    233238 
    234239struct thread_param 
     
    269274static void dummy_callback(pj_timer_heap_t *ht, pj_timer_entry *e) 
    270275{ 
     276    PJ_UNUSED_ARG(ht); 
    271277    PJ_LOG(4,("test", "dummy callback called %p %p", e, e->user_data)); 
    272278} 
     
    747753} 
    748754 
     755static int get_random_delay() 
     756{ 
     757    return pj_rand() % BT_ENTRY_COUNT; 
     758} 
     759 
     760static int get_next_delay(int delay) 
     761{ 
     762    return ++delay; 
     763} 
     764 
     765typedef enum BENCH_TEST_TYPE { 
     766    RANDOM_SCH = 0, 
     767    RANDOM_CAN = 1, 
     768    INCREMENT_SCH = 2, 
     769    INCREMENT_CAN = 3 
     770} BENCH_TEST_TYPE; 
     771 
     772static char *get_test_name(BENCH_TEST_TYPE test_type) { 
     773    switch (test_type) { 
     774    case RANDOM_SCH: 
     775    case INCREMENT_SCH: 
     776        return "schedule"; 
     777    case RANDOM_CAN: 
     778    case INCREMENT_CAN: 
     779        return "cancel"; 
     780    } 
     781    return "undefined"; 
     782} 
     783 
     784static void *get_format_num(unsigned n, char *out) 
     785{ 
     786    int c; 
     787    char buf[64]; 
     788    char *p; 
     789 
     790    pj_ansi_snprintf(buf, 64, "%d", n); 
     791    c = 2 - pj_ansi_strlen(buf) % 3; 
     792    for (p = buf; *p != 0; ++p) { 
     793       *out++ = *p; 
     794       if (c == 1) { 
     795           *out++ = ','; 
     796       } 
     797       c = (c + 1) % 3; 
     798    } 
     799    *--out = 0; 
     800    return out; 
     801} 
     802 
     803static void print_bench(BENCH_TEST_TYPE test_type, pj_timestamp time_freq, 
     804                        pj_timestamp time_start, int start_idx, int end_idx) 
     805{ 
     806    char start_idx_str[64]; 
     807    char end_idx_str[64]; 
     808    char num_req_str[64]; 
     809    unsigned num_req; 
     810    pj_timestamp t2; 
     811 
     812    pj_get_timestamp(&t2); 
     813    pj_sub_timestamp(&t2, &time_start); 
     814 
     815    num_req = (unsigned)(time_freq.u64 * (end_idx-start_idx) / t2.u64); 
     816    if (test_type == RANDOM_CAN || test_type == INCREMENT_CAN) { 
     817        start_idx = BT_ENTRY_COUNT - start_idx; 
     818        end_idx = BT_ENTRY_COUNT - end_idx; 
     819    } 
     820    get_format_num(start_idx, start_idx_str); 
     821    get_format_num(end_idx, end_idx_str); 
     822    get_format_num(num_req, num_req_str); 
     823 
     824    PJ_LOG(3, (THIS_FILE, "    Entries %s-%s: %s %s ent/sec", 
     825               start_idx_str, end_idx_str, get_test_name(test_type), 
     826               num_req_str)); 
     827} 
     828 
     829static int bench_test(pj_timer_heap_t *timer, 
     830                      pj_timer_entry *entries, 
     831                      pj_timestamp freq, 
     832                      BENCH_TEST_TYPE test_type) 
     833{ 
     834    pj_timestamp t1, t2; 
     835    unsigned mult = BT_ENTRY_SHOW_START; 
     836    int i, j; 
     837 
     838    pj_get_timestamp(&t1); 
     839    t2.u64 = 0; 
     840    /*Schedule random entry.*/ 
     841    for (i=0, j=0; j < BT_ENTRY_COUNT; ++j) { 
     842        pj_time_val delay = { 0 }; 
     843        pj_status_t status; 
     844 
     845        switch (test_type) { 
     846        case RANDOM_SCH: 
     847            delay.msec = get_random_delay(); 
     848            break; 
     849        case INCREMENT_SCH: 
     850            delay.msec = get_next_delay(delay.msec); 
     851            break; 
     852        } 
     853 
     854        if (test_type == RANDOM_SCH || test_type == INCREMENT_SCH) { 
     855            pj_timer_entry_init(&entries[j], 0, NULL, &dummy_callback); 
     856 
     857            status = pj_timer_heap_schedule(timer, &entries[j], &delay); 
     858            if (status != PJ_SUCCESS) { 
     859                app_perror("...error: unable to schedule timer entry", status); 
     860                return -50; 
     861            } 
     862        } else if (test_type == RANDOM_CAN || test_type == INCREMENT_CAN) { 
     863            unsigned num_ent = pj_timer_heap_cancel(timer, &entries[j]); 
     864            if (num_ent == 0) { 
     865                PJ_LOG(3, ("test", "...error: unable to cancel timer entry")); 
     866                return -60; 
     867            } 
     868        } else { 
     869            return -70; 
     870        } 
     871 
     872        if (j && (j % mult) == 0) { 
     873            print_bench(test_type, freq, t1, i, j); 
     874 
     875            i = j+1; 
     876            pj_get_timestamp(&t1); 
     877            mult *= BT_ENTRY_SHOW_MULT; 
     878        } 
     879    } 
     880    if (j > 0 && ((j-1) % mult != 0)) { 
     881        print_bench(test_type, freq, t1, i, j); 
     882    } 
     883    return 0; 
     884} 
     885 
     886static int timer_bench_test(void) 
     887{ 
     888    pj_pool_t *pool = NULL; 
     889    pj_timer_heap_t *timer = NULL; 
     890    pj_status_t status; 
     891    int err=0; 
     892    pj_timer_entry *entries = NULL; 
     893    pj_timestamp freq; 
     894    int i; 
     895 
     896    PJ_LOG(3,("test", "...Benchmark test")); 
     897 
     898    status = pj_get_timestamp_freq(&freq); 
     899    if (status != PJ_SUCCESS) { 
     900        PJ_LOG(3,("test", "...error: unable to get timestamp freq")); 
     901        err = -10; 
     902        goto on_return; 
     903    } 
     904 
     905    pool = pj_pool_create( mem, NULL, 128, 128, NULL); 
     906    if (!pool) { 
     907        PJ_LOG(3,("test", "...error: unable to create pool")); 
     908        err = -20; 
     909        goto on_return; 
     910    } 
     911 
     912    /* Create timer heap.*/ 
     913    status = pj_timer_heap_create(pool, BT_ENTRY_COUNT/64, &timer); 
     914    if (status != PJ_SUCCESS) { 
     915        app_perror("...error: unable to create timer heap", status); 
     916        err = -30; 
     917        goto on_return; 
     918    } 
     919 
     920    /* Create and schedule timer entries */ 
     921    entries = (pj_timer_entry*)pj_pool_calloc(pool, BT_ENTRY_COUNT, 
     922                                              sizeof(*entries)); 
     923    if (!entries) { 
     924        err = -40; 
     925        goto on_return; 
     926    } 
     927 
     928    PJ_LOG(3,("test", "....random scheduling/cancelling test..")); 
     929    for (i = 0; i < BT_REPEAT_RANDOM_TEST; ++i) { 
     930        PJ_LOG(3,("test", "    test %d of %d..", i+1, BT_REPEAT_RANDOM_TEST)); 
     931        err = bench_test(timer, entries, freq, RANDOM_SCH); 
     932        if (err < 0) 
     933            goto on_return; 
     934 
     935        err = bench_test(timer, entries, freq, RANDOM_CAN); 
     936        if (err < 0) 
     937            goto on_return; 
     938    } 
     939 
     940    PJ_LOG(3,("test", "....increment scheduling/cancelling test..")); 
     941    for (i = 0; i < BT_REPEAT_INC_TEST; ++i) { 
     942        PJ_LOG(3,("test", "    test %d of %d..", i+1, BT_REPEAT_INC_TEST)); 
     943        err = bench_test(timer, entries, freq, INCREMENT_SCH); 
     944        if (err < 0) 
     945            goto on_return; 
     946 
     947        err = bench_test(timer, entries, freq, INCREMENT_CAN); 
     948        if (err < 0) 
     949            goto on_return; 
     950    } 
     951 on_return: 
     952    PJ_LOG(3,("test", "...Cleaning up resources")); 
     953    if (pool) 
     954        pj_pool_safe_release(&pool); 
     955    return err; 
     956} 
     957 
    749958int timer_test() 
    750959{ 
     
    756965 
    757966    rc = timer_stress_test(); 
     967    if (rc != 0) 
     968        return rc; 
     969 
     970    rc = timer_bench_test(); 
    758971    if (rc != 0) 
    759972        return rc; 
Note: See TracChangeset for help on using the changeset viewer.