Ignore:
Timestamp:
Sep 3, 2019 2:10:45 AM (4 years ago)
Author:
ming
Message:

Fixed #2225: Timer heap refactoring

File:
1 edited

Legend:

Unmodified
Added
Removed

  • pjproject/trunk/pjlib/src/pj/timer.c

    r5971 r6058  
    4747#define DEFAULT_MAX_TIMED_OUT_PER_POLL  (64) 
    4848 
     49/* Enable this to raise assertion in order to catch bug of timer entry 
     50 * which has been deallocated without being cancelled. If disabled, 
     51 * the timer heap will simply remove the destroyed entry (and print log) 
     52 * and resume normally. 
     53 * This setting only works if PJ_TIMER_HEAP_USE_COPY is enabled. 
     54 */ 
     55#define ASSERT_IF_ENTRY_DESTROYED (PJ_TIMER_HEAP_USE_COPY? 0: 0) 
     56 
     57 
    4958enum 
    5059{ 
    … …  
    5463}; 
    5564 
     65#if PJ_TIMER_HEAP_USE_COPY 
     66 
     67/* Duplicate/copy of the timer entry. */ 
     68typedef struct pj_timer_entry_dup 
     69{ 
     70    /** 
     71     * The duplicate copy. 
     72     */ 
     73    pj_timer_entry  dup;                 
     74     
     75    /** 
     76     * Pointer of the original timer entry. 
     77     */ 
     78    pj_timer_entry *entry; 
     79 
     80    /**  
     81     * The future time when the timer expires, which the value is updated 
     82     * by timer heap when the timer is scheduled. 
     83     */ 
     84    pj_time_val     _timer_value; 
     85 
     86    /** 
     87     * Internal: the group lock used by this entry, set when 
     88     * pj_timer_heap_schedule_w_lock() is used. 
     89     */ 
     90    pj_grp_lock_t  *_grp_lock; 
     91 
     92#if PJ_TIMER_DEBUG 
     93    const char     *src_file; 
     94    int             src_line; 
     95#endif 
     96 
     97} pj_timer_entry_dup; 
     98 
     99#define GET_TIMER(ht, node) &ht->timer_dups[node->_timer_id] 
     100#define GET_ENTRY(node) node->entry 
     101#define GET_FIELD(node, _timer_id) node->dup._timer_id 
     102 
     103#else 
     104 
     105typedef pj_timer_entry pj_timer_entry_dup; 
     106 
     107#define GET_TIMER(ht, node) node 
     108#define GET_ENTRY(node) node 
     109#define GET_FIELD(node, _timer_id) node->_timer_id 
     110 
     111#endif 
    56112 
    57113/** 
    … …  
    84140     * array. 
    85141     */ 
    86     pj_timer_entry **heap; 
     142    pj_timer_entry_dup **heap; 
    87143 
    88144    /** 
    … …  
    97153     */ 
    98154    pj_timer_id_t *timer_ids; 
     155     
     156    /** 
     157     * An array of timer entry copies. 
     158     */ 
     159    pj_timer_entry_dup *timer_dups; 
    99160 
    100161    /** 
    … …  
    127188 
    128189static void copy_node( pj_timer_heap_t *ht, pj_size_t slot,  
    129                        pj_timer_entry *moved_node ) 
     190                       pj_timer_entry_dup *moved_node ) 
    130191{ 
    131192    PJ_CHECK_STACK(); 
    … …  
    135196     
    136197    // Update the corresponding slot in the parallel <timer_ids_> array. 
    137     ht->timer_ids[moved_node->_timer_id] = (int)slot; 
     198    ht->timer_ids[GET_FIELD(moved_node, _timer_id)] = (int)slot; 
    138199} 
    139200 
    … …  
    165226 
    166227 
    167 static void reheap_down(pj_timer_heap_t *ht, pj_timer_entry *moved_node, 
     228static void reheap_down(pj_timer_heap_t *ht, pj_timer_entry_dup *moved_node, 
    168229                        size_t slot, size_t child) 
    169230{ 
    … …  
    175236    { 
    176237        // Choose the smaller of the two children. 
    177         if (child + 1 < ht->cur_size 
    178             && PJ_TIME_VAL_LT(ht->heap[child + 1]->_timer_value, ht->heap[child]->_timer_value)) 
     238        if (child + 1 < ht->cur_size && 
     239            PJ_TIME_VAL_LT(ht->heap[child + 1]->_timer_value, 
     240                           ht->heap[child]->_timer_value)) 
     241        { 
    179242            child++; 
     243        } 
    180244         
    181245        // Perform a <copy> if the child has a larger timeout value than 
    182246        // the <moved_node>. 
    183         if (PJ_TIME_VAL_LT(ht->heap[child]->_timer_value, moved_node->_timer_value)) 
     247        if (PJ_TIME_VAL_LT(ht->heap[child]->_timer_value, 
     248                           moved_node->_timer_value)) 
    184249        { 
    185250            copy_node( ht, slot, ht->heap[child]); 
    … …  
    195260} 
    196261 
    197 static void reheap_up( pj_timer_heap_t *ht, pj_timer_entry *moved_node, 
     262static void reheap_up( pj_timer_heap_t *ht, pj_timer_entry_dup *moved_node, 
    198263                       size_t slot, size_t parent) 
    199264{ 
    … …  
    204269        // If the parent node is greater than the <moved_node> we need 
    205270        // to copy it down. 
    206         if (PJ_TIME_VAL_LT(moved_node->_timer_value, ht->heap[parent]->_timer_value)) 
     271        if (PJ_TIME_VAL_LT(moved_node->_timer_value, 
     272                           ht->heap[parent]->_timer_value)) 
    207273        { 
    208274            copy_node(ht, slot, ht->heap[parent]); 
    … …  
    220286 
    221287 
    222 static pj_timer_entry * remove_node( pj_timer_heap_t *ht, size_t slot) 
    223 { 
    224     pj_timer_entry *removed_node = ht->heap[slot]; 
     288static pj_timer_entry_dup * remove_node( pj_timer_heap_t *ht, size_t slot) 
     289{ 
     290    pj_timer_entry_dup *removed_node = ht->heap[slot]; 
    225291     
    226292    // Return this timer id to the freelist. 
    227     push_freelist( ht, removed_node->_timer_id ); 
     293    push_freelist( ht, GET_FIELD(removed_node, _timer_id) ); 
    228294     
    229295    // Decrement the size of the heap by one since we're removing the 
    … …  
    232298     
    233299    // Set the ID 
    234     removed_node->_timer_id = -1; 
     300    if (GET_FIELD(removed_node, _timer_id) != 
     301        GET_ENTRY(removed_node)->_timer_id) 
     302    { 
     303            PJ_LOG(3,(THIS_FILE, "Bug! Trying to remove entry %p from %s " 
     304                                 "line %d, which has been deallocated " 
     305                                 "without being cancelled", 
     306                                 GET_ENTRY(removed_node), 
     307#if PJ_TIMER_DEBUG 
     308                                 removed_node->src_file, 
     309                                 removed_node->src_line)); 
     310#else 
     311                                 "N/A", 0)); 
     312#endif 
     313#if ASSERT_IF_ENTRY_DESTROYED 
     314        pj_assert(removed_node->dup._timer_id==removed_node->entry->_timer_id); 
     315#endif 
     316    } 
     317    GET_ENTRY(removed_node)->_timer_id = -1; 
     318    GET_FIELD(removed_node, _timer_id) = -1; 
    235319 
    236320    // Only try to reheapify if we're not deleting the last entry. 
    … …  
    239323    { 
    240324        pj_size_t parent; 
    241         pj_timer_entry *moved_node = ht->heap[ht->cur_size]; 
     325        pj_timer_entry_dup *moved_node = ht->heap[ht->cur_size]; 
    242326         
    243327        // Move the end node to the location being removed and update 
    … …  
    249333        parent = HEAP_PARENT (slot); 
    250334         
    251         if (PJ_TIME_VAL_GTE(moved_node->_timer_value, ht->heap[parent]->_timer_value)) 
     335        if (PJ_TIME_VAL_GTE(moved_node->_timer_value, 
     336                            ht->heap[parent]->_timer_value)) 
     337        { 
    252338            reheap_down( ht, moved_node, slot, HEAP_LEFT(slot)); 
    253         else 
     339        } else { 
    254340            reheap_up( ht, moved_node, slot, parent); 
     341        } 
    255342    } 
    256343     
    … …  
    258345} 
    259346 
    260 static void grow_heap(pj_timer_heap_t *ht) 
     347static pj_status_t grow_heap(pj_timer_heap_t *ht) 
    261348{ 
    262349    // All the containers will double in size from max_size_ 
    263350    size_t new_size = ht->max_size * 2; 
     351    pj_timer_entry_dup *new_timer_dups = 0; 
    264352    pj_timer_id_t *new_timer_ids; 
    265353    pj_size_t i; 
    266354     
     355    PJ_LOG(6,(THIS_FILE, "Growing heap size from %d to %d", 
     356                         ht->max_size, new_size)); 
     357     
    267358    // First grow the heap itself. 
    268359     
    269     pj_timer_entry **new_heap = 0; 
    270      
    271     new_heap = (pj_timer_entry**)  
    272                pj_pool_alloc(ht->pool, sizeof(pj_timer_entry*) * new_size); 
    273     memcpy(new_heap, ht->heap, ht->max_size * sizeof(pj_timer_entry*)); 
    274     //delete [] this->heap_; 
     360    pj_timer_entry_dup **new_heap = 0; 
     361     
     362    new_heap = (pj_timer_entry_dup**)  
     363               pj_pool_calloc(ht->pool, new_size, sizeof(pj_timer_entry_dup*)); 
     364    if (!new_heap) 
     365        return PJ_ENOMEM; 
     366     
     367#if PJ_TIMER_HEAP_USE_COPY 
     368    // Grow the array of timer copies. 
     369     
     370    new_timer_dups = (pj_timer_entry_dup*)  
     371                     pj_pool_alloc(ht->pool, 
     372                                   sizeof(pj_timer_entry_dup) * new_size); 
     373    if (!new_timer_dups) 
     374        return PJ_ENOMEM; 
     375 
     376    memcpy(new_timer_dups, ht->timer_dups, 
     377           ht->max_size * sizeof(pj_timer_entry_dup)); 
     378    for (i = 0; i < ht->cur_size; i++) { 
     379        int idx = ht->heap[i] - ht->timer_dups; 
     380        // Point to the address in the new array 
     381        pj_assert(idx >= 0 && idx < ht->max_size); 
     382        new_heap[i] = &new_timer_dups[idx]; 
     383    } 
     384    ht->timer_dups = new_timer_dups; 
     385#else 
     386    memcpy(new_heap, ht->heap, ht->max_size * sizeof(pj_timer_entry *)); 
     387#endif 
    275388    ht->heap = new_heap; 
    276389     
    … …  
    280393    new_timer_ids = (pj_timer_id_t*) 
    281394                    pj_pool_alloc(ht->pool, new_size * sizeof(pj_timer_id_t)); 
    282      
     395    if (!new_timer_ids) 
     396        return PJ_ENOMEM; 
     397 
    283398    memcpy( new_timer_ids, ht->timer_ids, ht->max_size * sizeof(pj_timer_id_t)); 
    284399     
    … …  
    291406     
    292407    ht->max_size = new_size; 
    293 } 
    294  
    295 static void insert_node(pj_timer_heap_t *ht, pj_timer_entry *new_node) 
    296 { 
    297     if (ht->cur_size + 2 >= ht->max_size) 
    298         grow_heap(ht); 
    299      
    300     reheap_up( ht, new_node, ht->cur_size, HEAP_PARENT(ht->cur_size)); 
     408     
     409    return PJ_SUCCESS; 
     410} 
     411 
     412static pj_status_t insert_node(pj_timer_heap_t *ht, 
     413                               pj_timer_entry *new_node, 
     414                               const pj_time_val *future_time) 
     415{ 
     416    pj_timer_entry_dup *timer_copy; 
     417 
     418    if (ht->cur_size + 2 >= ht->max_size) { 
     419        pj_status_t status = grow_heap(ht); 
     420        if (status != PJ_SUCCESS) 
     421            return status; 
     422    } 
     423 
     424    timer_copy = GET_TIMER(ht, new_node); 
     425#if PJ_TIMER_HEAP_USE_COPY     
     426    // Create a duplicate of the timer entry. 
     427    pj_bzero(timer_copy, sizeof(*timer_copy)); 
     428    pj_memcpy(&timer_copy->dup, new_node, sizeof(*new_node)); 
     429    timer_copy->entry = new_node; 
     430#endif 
     431    timer_copy->_timer_value = *future_time; 
     432 
     433    reheap_up( ht, timer_copy, ht->cur_size, HEAP_PARENT(ht->cur_size)); 
    301434    ht->cur_size++; 
     435 
     436    return PJ_SUCCESS; 
    302437} 
    303438 
    … …  
    312447        // Set the entry 
    313448        entry->_timer_id = pop_freelist(ht); 
    314         entry->_timer_value = *future_time; 
    315         insert_node( ht, entry); 
    316         return 0; 
     449 
     450        return insert_node( ht, entry, future_time ); 
    317451    } 
    318452    else 
    … …  
    325459                   unsigned flags) 
    326460{ 
    327   long timer_node_slot; 
    328  
    329   PJ_CHECK_STACK(); 
    330  
    331   // Check to see if the timer_id is out of range 
    332   if (entry->_timer_id < 0 || (pj_size_t)entry->_timer_id > ht->max_size) { 
    333     entry->_timer_id = -1; 
    334     return 0; 
    335   } 
    336  
    337   timer_node_slot = ht->timer_ids[entry->_timer_id]; 
    338  
    339   if (timer_node_slot < 0) { // Check to see if timer_id is still valid. 
    340     entry->_timer_id = -1; 
    341     return 0; 
    342   } 
    343  
    344   if (entry != ht->heap[timer_node_slot]) 
    345     { 
    346       if ((flags & F_DONT_ASSERT) == 0) 
    347           pj_assert(entry == ht->heap[timer_node_slot]); 
    348       entry->_timer_id = -1; 
    349       return 0; 
    350     } 
    351   else 
    352     { 
    353       remove_node( ht, timer_node_slot); 
    354  
    355       if ((flags & F_DONT_CALL) == 0) 
    356         // Call the close hook. 
    357         (*ht->callback)(ht, entry); 
    358       return 1; 
     461    long timer_node_slot; 
     462 
     463    PJ_CHECK_STACK(); 
     464 
     465    // Check to see if the timer_id is out of range 
     466    if (entry->_timer_id < 0 || (pj_size_t)entry->_timer_id > ht->max_size) { 
     467        entry->_timer_id = -1; 
     468        return 0; 
     469    } 
     470 
     471    timer_node_slot = ht->timer_ids[entry->_timer_id]; 
     472 
     473    if (timer_node_slot < 0) { // Check to see if timer_id is still valid. 
     474        entry->_timer_id = -1; 
     475        return 0; 
     476    } 
     477 
     478    if (entry != GET_ENTRY(ht->heap[timer_node_slot])) { 
     479        if ((flags & F_DONT_ASSERT) == 0) 
     480            pj_assert(entry == GET_ENTRY(ht->heap[timer_node_slot])); 
     481        entry->_timer_id = -1; 
     482        return 0; 
     483    } else { 
     484        remove_node( ht, timer_node_slot); 
     485 
     486        if ((flags & F_DONT_CALL) == 0) { 
     487            // Call the close hook. 
     488            (*ht->callback)(ht, entry); 
     489        } 
     490        return 1; 
    359491    } 
    360492} 
    … …  
    369501           sizeof(pj_timer_heap_t) +  
    370502           /* size of each entry: */ 
    371            (count+2) * (sizeof(pj_timer_entry*)+sizeof(pj_timer_id_t)) + 
     503           (count+2) * (sizeof(pj_timer_entry_dup*)+sizeof(pj_timer_id_t)+ 
     504           sizeof(pj_timer_entry_dup)) + 
    372505           /* lock, pool etc: */ 
    373506           132; 
    … …  
    392525 
    393526    /* Allocate timer heap data structure from the pool */ 
    394     ht = PJ_POOL_ALLOC_T(pool, pj_timer_heap_t); 
     527    ht = PJ_POOL_ZALLOC_T(pool, pj_timer_heap_t); 
    395528    if (!ht) 
    396529        return PJ_ENOMEM; 
    … …  
    408541 
    409542    // Create the heap array. 
    410     ht->heap = (pj_timer_entry**) 
    411                pj_pool_alloc(pool, sizeof(pj_timer_entry*) * size); 
     543    ht->heap = (pj_timer_entry_dup**) 
     544               pj_pool_calloc(pool, size, sizeof(pj_timer_entry_dup*)); 
    412545    if (!ht->heap) 
    413546        return PJ_ENOMEM; 
     547 
     548#if PJ_TIMER_HEAP_USE_COPY 
     549    // Create the timer entry copies array. 
     550    ht->timer_dups = (pj_timer_entry_dup*) 
     551                     pj_pool_alloc(pool, sizeof(pj_timer_entry_dup) * size); 
     552    if (!ht->timer_dups) 
     553        return PJ_ENOMEM; 
     554#endif 
    414555 
    415556    // Create the parallel 
    … …  
    468609    entry->user_data = user_data; 
    469610    entry->cb = cb; 
     611#if !PJ_TIMER_HEAP_USE_COPY 
    470612    entry->_grp_lock = NULL; 
     613#endif 
    471614 
    472615    return entry; 
    … …  
    505648    //PJ_ASSERT_RETURN(entry->_timer_id < 1, PJ_EINVALIDOP); 
    506649 
    507 #if PJ_TIMER_DEBUG 
    508     entry->src_file = src_file; 
    509     entry->src_line = src_line; 
    510 #endif 
    511650    pj_gettickcount(&expires); 
    512651    PJ_TIME_VAL_ADD(expires, *delay); 
    … …  
    517656    if (pj_timer_entry_running(entry)) { 
    518657        unlock_timer_heap(ht); 
    519         PJ_LOG(3,(THIS_FILE, "Bug! Rescheduling outstanding entry (%p)", 
     658        PJ_LOG(3,(THIS_FILE, "Warning! Rescheduling outstanding entry (%p)", 
    520659                  entry)); 
    521660        return PJ_EINVALIDOP; 
    … …  
    524663    status = schedule_entry(ht, entry, &expires); 
    525664    if (status == PJ_SUCCESS) { 
     665        pj_timer_entry_dup *timer_copy = GET_TIMER(ht, entry); 
     666 
    526667        if (set_id) 
    527             entry->id = id_val; 
    528         entry->_grp_lock = grp_lock; 
    529         if (entry->_grp_lock) { 
    530             pj_grp_lock_add_ref(entry->_grp_lock); 
     668            GET_FIELD(timer_copy, id) = entry->id = id_val; 
     669        timer_copy->_grp_lock = grp_lock; 
     670        if (timer_copy->_grp_lock) { 
     671            pj_grp_lock_add_ref(timer_copy->_grp_lock); 
    531672        } 
     673#if PJ_TIMER_DEBUG 
     674        timer_copy->src_file = src_file; 
     675        timer_copy->src_line = src_line; 
     676#endif 
    532677    } 
    533678    unlock_timer_heap(ht); 
    … …  
    584729                        int id_val) 
    585730{ 
     731    pj_timer_entry_dup *timer_copy; 
     732    pj_grp_lock_t *grp_lock; 
    586733    int count; 
    587734 
    … …  
    589736 
    590737    lock_timer_heap(ht); 
     738    timer_copy = GET_TIMER(ht, entry); 
     739    grp_lock = timer_copy->_grp_lock; 
     740 
    591741    count = cancel(ht, entry, flags | F_DONT_CALL); 
    592742    if (count > 0) { 
    … …  
    595745            entry->id = id_val; 
    596746        } 
    597         if (entry->_grp_lock) { 
    598             pj_grp_lock_t *grp_lock = entry->_grp_lock; 
    599             entry->_grp_lock = NULL; 
     747        if (grp_lock) { 
    600748            pj_grp_lock_dec_ref(grp_lock); 
    601749        } 
    … …  
    641789            count < ht->max_entries_per_poll )  
    642790    { 
    643         pj_timer_entry *node = remove_node(ht, 0); 
     791        pj_timer_entry_dup *node = remove_node(ht, 0); 
     792        pj_timer_entry *entry = GET_ENTRY(node); 
    644793        /* Avoid re-use of this timer until the callback is done. */ 
    645794        ///Not necessary, even causes problem (see also #2176). 
    646795        ///pj_timer_id_t node_timer_id = pop_freelist(ht); 
    647796        pj_grp_lock_t *grp_lock; 
     797        pj_bool_t valid = PJ_TRUE; 
    648798 
    649799        ++count; 
    … …  
    651801        grp_lock = node->_grp_lock; 
    652802        node->_grp_lock = NULL; 
     803        if (GET_FIELD(node, cb) != entry->cb || 
     804            GET_FIELD(node, user_data) != entry->user_data) 
     805        { 
     806            valid = PJ_FALSE; 
     807            PJ_LOG(3,(THIS_FILE, "Bug! Polling entry %p from %s line %d has " 
     808                                 "been deallocated without being cancelled", 
     809                                 GET_ENTRY(node), 
     810#if PJ_TIMER_DEBUG 
     811                                 node->src_file, node->src_line)); 
     812#else 
     813                                 "N/A", 0)); 
     814#endif 
     815#if ASSERT_IF_ENTRY_DESTROYED 
     816            pj_assert(node->dup.cb == entry->cb); 
     817            pj_assert(node->dup.user_data == entry->user_data); 
     818#endif 
     819        } 
    653820 
    654821        unlock_timer_heap(ht); 
    … …  
    656823        PJ_RACE_ME(5); 
    657824 
    658         if (node->cb) 
    659             (*node->cb)(ht, node); 
    660  
    661         if (grp_lock) 
     825        if (valid && entry->cb) 
     826            (*entry->cb)(ht, entry); 
     827 
     828        if (valid && grp_lock) 
    662829            pj_grp_lock_dec_ref(grp_lock); 
    663830 
    … …  
    720887 
    721888        for (i=0; i<(unsigned)ht->cur_size; ++i) { 
    722             pj_timer_entry *e = ht->heap[i]; 
     889            pj_timer_entry_dup *e = ht->heap[i]; 
    723890            pj_time_val delta; 
    724891 
    … …  
    731898 
    732899            PJ_LOG(3,(THIS_FILE, "    %d\t%d\t%d.%03d\t%s:%d", 
    733                       e->_timer_id, e->id, 
     900                      GET_FIELD(e, _timer_id), GET_FIELD(e, id), 
    734901                      (int)delta.sec, (int)delta.msec, 
    735902                      e->src_file, e->src_line)); 
Note: See TracChangeset for help on using the changeset viewer.