diff options
| -rw-r--r-- | Changelog-Trunk.txt | 5 | ||||
| -rw-r--r-- | src/common/timer.c | 379 | ||||
| -rw-r--r-- | src/common/timer.h | 2 | ||||
| -rw-r--r-- | src/map/atcommand.c | 4 | ||||
| -rw-r--r-- | src/map/npc.c | 6 | ||||
| -rw-r--r-- | src/map/skill.c | 2 | ||||
| -rw-r--r-- | src/map/unit.c | 6 |
7 files changed, 247 insertions, 157 deletions
diff --git a/Changelog-Trunk.txt b/Changelog-Trunk.txt index 06581e7a4..6130be0fb 100644 --- a/Changelog-Trunk.txt +++ b/Changelog-Trunk.txt @@ -3,6 +3,11 @@ Date Added AS OF SVN REV. 5091, WE ARE NOW USING TRUNK. ALL UNTESTED BUGFIXES/FEATURES GO INTO TRUNK. IF YOU HAVE A WORKING AND TESTED BUGFIX PUT IT INTO STABLE AS WELL AS TRUNK. +2008/07/09 + * Added const to the return value of get_timer. + * Added a maximum timer interval. Avoids server shutdowns being delayed + for ~10 seconds under some circumstances on windows. + * Replaced the fake timer heap (ordered array) with a binary min heap. [FlavioJS] 2008/07/07 * First attempt at implementing the official walk speed system - separated speed modifiers into bonuses, penalties and other statuses diff --git a/src/common/timer.c b/src/common/timer.c index 2252a3da8..cf594ef6d 100644 --- a/src/common/timer.c +++ b/src/common/timer.c @@ -22,26 +22,27 @@ // If the server can't handle processing thousands of monsters // or many connected clients, please increase TIMER_MIN_INTERVAL. #define TIMER_MIN_INTERVAL 50 +#define TIMER_MAX_INTERVAL 60000 -// timers +// timers (array) static struct TimerData* timer_data = NULL; -static int timer_data_max = 0; -static int timer_data_num = 0; +static int timer_data_max = 0; +static int timer_data_num = 0; -// free timers +// free timers (array) static int* free_timer_list = NULL; static int free_timer_list_max = 0; -static int free_timer_list_pos = 0; +static int free_timer_list_num = 0; -//NOTE: using a binary heap should improve performance [FlavioJS] -// timer heap (ordered array of tid's) -static int timer_heap_num = 0; -static int timer_heap_max = 0; -static int* timer_heap = NULL; +// timer heap (binary min heap) +static int* timer_heap = NULL; +static int timer_heap_max = 0; +static int timer_heap_num = 0; // server startup time time_t start_time; + /*---------------------------- * Timer debugging *----------------------------*/ @@ -144,87 +145,184 @@ unsigned int gettick(void) * CORE : Timer Heap *--------------------------------------*/ -// searches for the target tick's position and stores it in pos (binary search) -#define HEAP_SEARCH(target,from,to,pos) \ - do { \ - int max,pivot; \ - max = to; \ - pos = from; \ - while (pos < max) { \ - pivot = (pos + max) / 2; \ - if (DIFF_TICK(target, timer_data[timer_heap[pivot]].tick) < 0) \ - pos = pivot + 1; \ - else \ - max = pivot; \ - } \ - } while(0) +#define BHEAP_PARENT(pos) ( ((pos) - 1)/2 ) +#define BHEAP_LEFT(pos) ( (pos)*2 + 1 ) +#define BHEAP_RIGHT(pos) ( (pos)*2 + 2 ) /// Adds a timer to the timer_heap -static void push_timer_heap(int tid) +static +void push_timer_heap(int tid) { int pos; - // check number of element - if (timer_heap_num >= timer_heap_max) { - if (timer_heap_max == 0) { - timer_heap_max = 256; - CREATE(timer_heap, int, 256); - } else { - timer_heap_max += 256; + // check available space + if( timer_heap_num >= timer_heap_max ) + { + timer_heap_max += 256; + if( timer_heap ) RECREATE(timer_heap, int, timer_heap_max); - memset(timer_heap + (timer_heap_max - 256), 0, sizeof(int) * 256); - } + else + CREATE(timer_heap, int, timer_heap_max); + memset(timer_heap + (timer_heap_max - 256), 0, sizeof(int)*256); } - // do a sorting from higher to lower - if( timer_heap_num == 0 || DIFF_TICK(timer_data[tid].tick, timer_data[timer_heap[timer_heap_num - 1]].tick) < 0 ) - timer_heap[timer_heap_num] = tid; // if lower actual item is higher than new - else + // add the timer + pos = timer_heap_num++; + timer_heap[pos] = tid; + // restore binary heap properties + while( pos > 0 ) { - // searching position - HEAP_SEARCH(timer_data[tid].tick,0,timer_heap_num-1,pos); - // move elements - memmove(&timer_heap[pos + 1], &timer_heap[pos], sizeof(int) * (timer_heap_num - pos)); - // save new element - timer_heap[pos] = tid; + int parent = BHEAP_PARENT(pos); + if( DIFF_TICK(timer_data[tid].tick, timer_data[timer_heap[parent]].tick) > 0 ) + break;// done + swap(timer_heap[pos], timer_heap[parent]); + pos = parent; + } +} + +/// Removes a timer from the timer_heap +static +bool pop_timer_heap(int tid) +{ + int pos; + + // find the timer + pos = 0; + while( pos < timer_heap_num ) + {// search in the order current-left-right + int left = BHEAP_LEFT(pos); + int right = BHEAP_RIGHT(pos); + + if( timer_heap[pos] == tid ) + break;// found the timer + if( left < timer_heap_num && DIFF_TICK(timer_data[tid].tick, timer_data[timer_heap[left]].tick) <= 0 ) + {// try left child + pos = left; + continue; + } + if( right < timer_heap_num && DIFF_TICK(timer_data[tid].tick, timer_data[timer_heap[right]].tick) <= 0 ) + {// try right child + pos = right; + continue; + } + + // back and right + while( true ) + { + int parent; + if( pos == 0 ) + return false;// not found + parent = BHEAP_PARENT(pos); + right = BHEAP_RIGHT(parent); + if( pos != right && right < timer_heap_num && DIFF_TICK(timer_data[tid].tick, timer_data[timer_heap[right]].tick) <= 0 ) + break;// try this right + pos = parent; + } + pos = right; } + if( pos >= timer_heap_num ) + return false;// not found - timer_heap_num++; + // remove timer + timer_heap[pos] = timer_heap[--timer_heap_num]; + // restore binary heap properties + while( pos < timer_heap_num ) + { + int left = BHEAP_LEFT(pos); + int right = BHEAP_RIGHT(pos); + if( left < timer_heap_num && DIFF_TICK(timer_data[timer_heap[pos]].tick, timer_data[timer_heap[left]].tick) > 0 ) + { + if( right < timer_heap_num && DIFF_TICK(timer_data[timer_heap[left]].tick, timer_data[timer_heap[right]].tick) > 0 ) + { + swap(timer_heap[pos], timer_heap[right]); + pos = right; + } + else + { + swap(timer_heap[pos], timer_heap[left]); + pos = left; + } + } + else if( right < timer_heap_num && DIFF_TICK(timer_data[timer_heap[pos]].tick, timer_data[timer_heap[right]].tick) > 0 ) + { + swap(timer_heap[pos], timer_heap[right]); + pos = right; + } + else + { + break;// done + } + } + return true; } /*========================== * Timer Management *--------------------------*/ +// diff_tick limits (2*24*60*60*1000 is 2 days ; 2*60*60*1000 is 2 hours) +#define FUTURE_DIFF_TICK ( INT_MIN + 2*24*60*60*1000 ) +#define MAX_DIFF_TICK ( INT_MAX - 2*60*60*1000 ) +#define MIN_DIFF_TICK ( -2*60*60*1000 ) +#define PAST_DIFF_TICK ( -2*24*60*60*1000 ) + +/// Adjusts the tick value to a valid tick_diff range. +/// Returns false if the tick is invalid. +static +bool adjust_tick(unsigned int* tick) +{ + int diff; + + if( tick == NULL ) + return false; + + diff = DIFF_TICK(*tick, gettick()); + if( diff <= FUTURE_DIFF_TICK || diff > MAX_DIFF_TICK ) + { + ShowWarning("adjust_tick: tick diff too far in the future %d, adjusting to the maximum %d\n", diff, MAX_DIFF_TICK); + *tick -= (diff - MAX_DIFF_TICK); + } + else if( diff < PAST_DIFF_TICK ) + { + return false; + } + else if( diff < MIN_DIFF_TICK ) + { + ShowWarning("adjust_tick: tick diff too far in the past %d, adjusting to the minimm %d\n", diff, MIN_DIFF_TICK); + *tick += (diff - MAX_DIFF_TICK); + } + return true; +} + /// Returns a free timer id. static int acquire_timer(void) { int tid; - if (free_timer_list_pos) { - do { - tid = free_timer_list[--free_timer_list_pos]; - } while(tid >= timer_data_num && free_timer_list_pos > 0); - } else - tid = timer_data_num; - - if (tid >= timer_data_num) - for (tid = timer_data_num; tid < timer_data_max && timer_data[tid].type; tid++); - if (tid >= timer_data_num && tid >= timer_data_max) - {// expand timer array - if (timer_data_max == 0) - {// create timer data (1st time) - timer_data_max = 256; - CREATE(timer_data, struct TimerData, timer_data_max); - } else - {// add more timers - timer_data_max += 256; - RECREATE(timer_data, struct TimerData, timer_data_max); - memset(timer_data + (timer_data_max - 256), 0, sizeof(struct TimerData) * 256); + // select a free timer + tid = timer_data_num; + while( free_timer_list_num ) + { + int pos = --free_timer_list_num; + if( free_timer_list[pos] < timer_data_num ) + { + tid = free_timer_list[pos]; + break; } } - if (tid >= timer_data_num) + // check available space + if( tid >= timer_data_max ) + { + timer_data_max += 256; + if( timer_data ) + RECREATE(timer_data, struct TimerData, timer_data_max); + else + CREATE(timer_data, struct TimerData, timer_data_max); + memset(timer_data + (timer_data_max - 256), 0, sizeof(struct TimerData)*256); + } + + if( tid >= timer_data_num ) timer_data_num = tid + 1; return tid; @@ -235,7 +333,12 @@ static int acquire_timer(void) int add_timer(unsigned int tick, TimerFunc func, int id, intptr data) { int tid; - + + if( !adjust_tick(&tick) ) + { + ShowError("add_timer: tick out of range (tick=%u %08x[%s] id=%d data=%d diff_tick=%d)\n", tick, (int)func, search_timer_func_list(func), id, data, DIFF_TICK(tick, gettick())); + return INVALID_TIMER; + } tid = acquire_timer(); timer_data[tid].tick = tick; timer_data[tid].func = func; @@ -254,11 +357,17 @@ int add_timer_interval(unsigned int tick, TimerFunc func, int id, intptr data, i { int tid; - if( interval < 1 ) { - ShowError("add_timer_interval : function %08x(%s) has invalid interval %d!\n", (int)func, search_timer_func_list(func), interval); - return -1; + if( interval < 1 ) + { + ShowError("add_timer_interval: invalid interval (tick=%u %08x[%s] id=%d data=%d diff_tick=%d)\n", tick, (int)func, search_timer_func_list(func), id, data, DIFF_TICK(tick, gettick())); + return INVALID_TIMER; } - + if( !adjust_tick(&tick) ) + { + ShowError("add_timer_interval: tick out of range (tick=%u %08x[%s] id=%d data=%d diff_tick=%d)\n", tick, (int)func, search_timer_func_list(func), id, data, DIFF_TICK(tick, gettick())); + return INVALID_TIMER; + } + tid = acquire_timer(); timer_data[tid].tick = tick; timer_data[tid].func = func; @@ -272,10 +381,11 @@ int add_timer_interval(unsigned int tick, TimerFunc func, int id, intptr data, i } /// Retrieves internal timer data -//FIXME: for safety, the return value should be 'const' -struct TimerData* get_timer(int tid) +const struct TimerData* get_timer(int tid) { - return &timer_data[tid]; + if( tid >= 0 && tid < timer_data_num ) + return &timer_data[tid]; + return NULL; } /// Marks a timer specified by 'id' for immediate deletion once it expires. @@ -283,11 +393,13 @@ struct TimerData* get_timer(int tid) /// Returns 0 on success, < 0 on failure. int delete_timer(int tid, TimerFunc func) { - if( tid < 0 || tid >= timer_data_num ) { + if( tid < 0 || tid >= timer_data_num ) + { ShowError("delete_timer error : no such timer %d (%08x(%s))\n", tid, (int)func, search_timer_func_list(func)); return -1; } - if( timer_data[tid].func != func ) { + if( timer_data[tid].func != func ) + { ShowError("delete_timer error : function mismatch %08x(%s) != %08x(%s)\n", (int)timer_data[tid].func, search_timer_func_list(timer_data[tid].func), (int)func, search_timer_func_list(func)); return -2; } @@ -309,50 +421,19 @@ int addtick_timer(int tid, unsigned int tick) /// Returns the new tick value, or -1 if it fails. int settick_timer(int tid, unsigned int tick) { - int old_pos,pos; - unsigned int old_tick; - - old_tick = timer_data[tid].tick; - if( old_tick == tick ) + if( timer_data[tid].tick == tick ) return tick; - // search old_tick position - HEAP_SEARCH(old_tick,0,timer_heap_num-1,old_pos); - while( timer_heap[old_pos] != tid ) - {// skip timers with the same tick - if( old_tick != timer_data[timer_heap[old_pos]].tick ) - { - ShowError("settick_timer: no such timer %d (%08x(%s))\n", tid, (int)timer_data[tid].func, search_timer_func_list(timer_data[tid].func)); - return -1; - } - ++old_pos; - } - - if( DIFF_TICK(tick,timer_data[tid].tick) < 0 ) - {// Timer is accelerated, shift timer near the end of the heap. - if (old_pos == timer_heap_num-1) //Nothing to shift. - pos = old_pos; - else { - HEAP_SEARCH(tick,old_pos+1,timer_heap_num-1,pos); - --pos; - if (pos != old_pos) - memmove(&timer_heap[old_pos], &timer_heap[old_pos+1], (pos-old_pos)*sizeof(int)); - } - } else - {// Timer is delayed, shift timer near the beginning of the heap. - if (old_pos == 0) //Nothing to shift. - pos = old_pos; - else { - HEAP_SEARCH(tick,0,old_pos-1,pos); - ++pos; - if (pos != old_pos) - memmove(&timer_heap[pos+1], &timer_heap[pos], (old_pos-pos)*sizeof(int)); - } + if( !adjust_tick(&tick) ) + { + ShowError("settick_timer: tick out of range, leaving timer unmodified (tid=%d tick=%u %08x[%s] diff_tick=%d)\n", tid, tick, (int)timer_data[tid].func, search_timer_func_list(timer_data[tid].func), DIFF_TICK(tick, gettick())); + return -1; } - - timer_heap[pos] = tid; + pop_timer_heap(tid); + if( tick == -1 ) + tick = 0; timer_data[tid].tick = tick; - + push_timer_heap(tid); return tick; } @@ -360,66 +441,70 @@ int settick_timer(int tid, unsigned int tick) /// Returns the value of the smallest non-expired timer (or 1 second if there aren't any). int do_timer(unsigned int tick) { - int nextmin = 1000; // return value - int i; + int diff = 1000; // return value // process all timers one by one while( timer_heap_num ) { - i = timer_heap[timer_heap_num - 1]; // last element in heap (=>smallest) - if( (nextmin = DIFF_TICK(timer_data[i].tick, tick)) > 0 ) + int tid = timer_heap[0]; // first element in heap (=>smallest) + + diff = DIFF_TICK(timer_data[tid].tick, tick); + if( diff > 0 ) break; // no more expired timers to process - --timer_heap_num; // suppress the actual element from the table + pop_timer_heap(tid); // mark timer as 'to be removed' - timer_data[i].type |= TIMER_REMOVE_HEAP; + timer_data[tid].type |= TIMER_REMOVE_HEAP; - if( timer_data[i].func ) + if( timer_data[tid].func ) { - if( nextmin < -1000 ) + if( diff < -1000 ) // 1秒以上の大幅な遅延が発生しているので、 // timer処理タイミングを現在値とする事で // 呼び出し時タイミング(引数のtick)相対で処理してる // timer関数の次回処理タイミングを遅らせる - timer_data[i].func(i, tick, timer_data[i].id, timer_data[i].data); + timer_data[tid].func(tid, tick, timer_data[tid].id, timer_data[tid].data); else - timer_data[i].func(i, timer_data[i].tick, timer_data[i].id, timer_data[i].data); + timer_data[tid].func(tid, timer_data[tid].tick, timer_data[tid].id, timer_data[tid].data); } // in the case the function didn't change anything... - if( timer_data[i].type & TIMER_REMOVE_HEAP ) + if( timer_data[tid].type & TIMER_REMOVE_HEAP ) { - timer_data[i].type &= ~TIMER_REMOVE_HEAP; + timer_data[tid].type &= ~TIMER_REMOVE_HEAP; - switch( timer_data[i].type ) + switch( timer_data[tid].type ) { case TIMER_ONCE_AUTODEL: - timer_data[i].type = 0; - if (free_timer_list_pos >= free_timer_list_max) { + timer_data[tid].type = 0; + if( free_timer_list_num >= free_timer_list_max ) + { free_timer_list_max += 256; - RECREATE(free_timer_list,int,free_timer_list_max); - memset(free_timer_list + (free_timer_list_max - 256), 0, 256 * sizeof(int)); + if( free_timer_list ) + RECREATE(free_timer_list, int, free_timer_list_max); + else + CREATE(free_timer_list, int, free_timer_list_max); + memset(free_timer_list + (free_timer_list_max - 256), 0, sizeof(int)*256); } - free_timer_list[free_timer_list_pos++] = i; - break; + free_timer_list[free_timer_list_num++] = tid; + break; case TIMER_INTERVAL: - if (DIFF_TICK(timer_data[i].tick , tick) < -1000) { - timer_data[i].tick = tick + timer_data[i].interval; - } else { - timer_data[i].tick += timer_data[i].interval; - } - timer_data[i].type &= ~TIMER_REMOVE_HEAP; - push_timer_heap(i); - break; + if( DIFF_TICK(timer_data[tid].tick, tick) < -1000 ) + timer_data[tid].tick = tick + timer_data[tid].interval; + else + timer_data[tid].tick += timer_data[tid].interval; + push_timer_heap(tid); + break; } } } - if( nextmin < TIMER_MIN_INTERVAL ) - nextmin = TIMER_MIN_INTERVAL; - - return nextmin; + if( diff < TIMER_MIN_INTERVAL ) + return TIMER_MIN_INTERVAL; + if( diff > TIMER_MAX_INTERVAL ) + return TIMER_MAX_INTERVAL; + return diff; } unsigned long get_uptime(void) diff --git a/src/common/timer.h b/src/common/timer.h index 28a792f88..354a71113 100644 --- a/src/common/timer.h +++ b/src/common/timer.h @@ -40,7 +40,7 @@ unsigned int gettick_nocache(void); int add_timer(unsigned int tick, TimerFunc func, int id, intptr data); int add_timer_interval(unsigned int tick, TimerFunc func, int id, intptr data, int interval); -struct TimerData* get_timer(int tid); +const struct TimerData* get_timer(int tid); int delete_timer(int tid, TimerFunc func); int addtick_timer(int tid, unsigned int tick); diff --git a/src/map/atcommand.c b/src/map/atcommand.c index 3338a3b04..1bdbf0697 100644 --- a/src/map/atcommand.c +++ b/src/map/atcommand.c @@ -4787,8 +4787,8 @@ char* txt_time(unsigned int duration) *------------------------------------------*/ int atcommand_servertime(const int fd, struct map_session_data* sd, const char* command, const char* message) { - struct TimerData * timer_data; - struct TimerData * timer_data2; + const struct TimerData * timer_data; + const struct TimerData * timer_data2; time_t time_server; // variable for number of seconds (used with time() function) struct tm *datetime; // variable for time in structure ->tm_mday, ->tm_sec, ... char temp[256]; diff --git a/src/map/npc.c b/src/map/npc.c index c987bd5b8..827ee76f8 100644 --- a/src/map/npc.c +++ b/src/map/npc.c @@ -511,7 +511,7 @@ int npc_timerevent_start(struct npc_data* nd, int rid) int npc_timerevent_stop(struct npc_data* nd) { struct map_session_data *sd =NULL; - struct TimerData *td = NULL; + const struct TimerData *td = NULL; int *tid; nullpo_retr(0, nd); if (nd->u.scr.rid) { @@ -541,7 +541,7 @@ int npc_timerevent_stop(struct npc_data* nd) *------------------------------------------*/ void npc_timerevent_quit(struct map_session_data* sd) { - struct TimerData *td; + const struct TimerData *td; struct npc_data* nd; struct timer_event_data *ted; if (sd->npc_timer_id == -1) @@ -1378,7 +1378,7 @@ int npc_unload(struct npc_data* nd) { ev_db->foreach(ev_db,npc_unload_ev,nd->exname); //Clean up all events related. if (nd->u.scr.timerid != -1) { - struct TimerData *td = NULL; + const struct TimerData *td = NULL; td = get_timer(nd->u.scr.timerid); if (td && td->data) ers_free(timer_event_ers, (void*)td->data); diff --git a/src/map/skill.c b/src/map/skill.c index ece5ca0af..1ed9b8268 100644 --- a/src/map/skill.c +++ b/src/map/skill.c @@ -6907,7 +6907,7 @@ int skill_unit_onplace_timer (struct skill_unit *src, struct block_list *bl, uns int sec = skill_get_time2(sg->skill_id,sg->skill_lv); if (status_change_start(bl,type,10000,sg->skill_lv,sg->group_id,0,0,sec, 8)) { - struct TimerData* td = tsc->data[type]?get_timer(tsc->data[type]->timer):NULL; + const struct TimerData* td = tsc->data[type]?get_timer(tsc->data[type]->timer):NULL; if (td) sec = DIFF_TICK(td->tick, tick); map_moveblock(bl, src->bl.x, src->bl.y, tick); clif_fixpos(bl); diff --git a/src/map/unit.c b/src/map/unit.c index d836a01e5..8da6ecddd 100644 --- a/src/map/unit.c +++ b/src/map/unit.c @@ -644,7 +644,7 @@ int unit_warp(struct block_list *bl,short m,short x,short y,int type) int unit_stop_walking(struct block_list *bl,int type) { struct unit_data *ud; - struct TimerData *data; + const struct TimerData* td; unsigned int tick; nullpo_retr(0, bl); @@ -654,13 +654,13 @@ int unit_stop_walking(struct block_list *bl,int type) //NOTE: We are using timer data after deleting it because we know the //delete_timer function does not messes with it. If the function's //behaviour changes in the future, this code could break! - data = get_timer(ud->walktimer); + td = get_timer(ud->walktimer); delete_timer(ud->walktimer, unit_walktoxy_timer); ud->walktimer = -1; ud->state.change_walk_target = 0; tick = gettick(); if ((type&0x02 && !ud->walkpath.path_pos) //Force moving at least one cell. - || (data && DIFF_TICK(data->tick, tick) <= data->data/2)) //Enough time has passed to cover half-cell + || (td && DIFF_TICK(td->tick, tick) <= td->data/2)) //Enough time has passed to cover half-cell { ud->walkpath.path_len = ud->walkpath.path_pos+1; unit_walktoxy_timer(-1, tick, bl->id, ud->walkpath.path_pos); |