Rainer Weikusat <[email protected]> writes: [...]
> There are probably all kinds of 'weird, stylistic issues' and > possible, yet unknown bugs, Attached is a slightly updated version of this. Mostly, it fixes an accidentally inverted comparison in down_heap, uses the squid x* memory allocation wrapper routines I found meanwhile and is more careful to avoid possibly invoking external code while the heap is not in a consistent state. It has still only been used on development computers.
--- mad-squid-log-sched/src/event.cc 8 Jan 2013 17:36:44 -0000 1.1.1.3 +++ mad-squid-log-sched/src/event.cc 29 Jan 2013 21:22:25 -0000 @@ -1,6 +1,7 @@ /* * DEBUG: section 41 Event Processing * AUTHOR: Henrik Nordstrom + * Heap-based priority queue: Rainer Weikusat <[email protected]> * * SQUID Web Proxy Cache http://www.squid-cache.org/ * ---------------------------------------------------------- @@ -38,6 +39,9 @@ #include "SquidTime.h" #include "profiler/Profiler.h" #include "tools.h" +#include "util.h" + +static unsigned const INITIAL_SIZE = 512; /* The list of event processes */ @@ -111,7 +115,7 @@ ev_entry::ev_entry(char const * aName, EVH * aFunction, void * aArgument, double evWhen, int aWeight, bool haveArgument) : name(aName), func(aFunction), arg(haveArgument ? cbdataReference(aArgument) : aArgument), when(evWhen), weight(aWeight), - cbdata(haveArgument) + cbdata(haveArgument), tag(NULL) { } @@ -121,15 +125,27 @@ cbdataReferenceDone(arg); } -void -eventAdd(const char *name, EVH * func, void *arg, double when, int weight, bool cbdata) +class ev_tag { - EventScheduler::GetInstance()->schedule(name, func, arg, when, weight, cbdata); +public: + ev_entry *event; + + MEMPROXY_CLASS(ev_tag); +}; + +MEMPROXY_CLASS_INLINE(ev_tag); + +void +eventAdd(const char *name, EVH * func, void *arg, double when, int weight, bool cbdata, + void **tag) +{ + EventScheduler::GetInstance()->schedule(name, func, arg, when, weight, cbdata, tag); } /* same as eventAdd but adds a random offset within +-1/3 of delta_ish */ void -eventAddIsh(const char *name, EVH * func, void *arg, double delta_ish, int weight) +eventAddIsh(const char *name, EVH * func, void *arg, double delta_ish, int weight, + void **tag) { if (delta_ish >= 3.0) { const double two_third = (2.0 * delta_ish) / 3.0; @@ -140,7 +156,7 @@ */ } - eventAdd(name, func, arg, delta_ish, weight); + eventAdd(name, func, arg, delta_ish, weight, tag); } void @@ -149,6 +165,16 @@ EventScheduler::GetInstance()->cancel(func, arg); } +void *eventDelete(void *tag) +{ + return EventScheduler::GetInstance()->cancel(tag); +} + +void eventReleaseTag(void *tag) +{ + EventScheduler::GetInstance()->releaseTag(tag); +} + void eventInit(void) { @@ -175,8 +201,9 @@ EventScheduler EventScheduler::_instance; -EventScheduler::EventScheduler(): tasks(NULL) -{} +EventScheduler::EventScheduler(): tasks(NULL), used(0), max(0) +{ +} EventScheduler::~EventScheduler() { @@ -186,46 +213,48 @@ void EventScheduler::cancel(EVH * func, void *arg) { - ev_entry **E; ev_entry *event; + unsigned ndx; - for (E = &tasks; (event = *E) != NULL; E = &(*E)->next) { - if (event->func != func) - continue; - - if (arg && event->arg != arg) - continue; - - *E = event->next; - - delete event; - - if (arg) - return; - /* - * DPW 2007-04-12 - * Since this method may now delete multiple events (when - * arg is NULL) it no longer returns after a deletion and - * we have a potential NULL pointer problem. If we just - * deleted the last event in the list then *E is now equal - * to NULL. We need to break here or else we'll get a NULL - * pointer dereference in the last clause of the for loop. - */ - if (NULL == *E) - break; + ndx = used; + while (ndx) { + event = tasks[ndx]; + if (event->func == func && (!arg || event->arg == arg)) { + cancelEvent(event); + + if (arg) + return; + + if (ndx > used) + ndx = used; + } else + --ndx; } +} - if (arg) - debug_trap("eventDelete: event not found"); +void *EventScheduler::cancel(void *tag) +{ + class ev_tag *ev_tag; + void *arg; + + ev_tag = static_cast<class ev_tag *>(tag); + + if (ev_tag->event) + arg = cancelEvent(ev_tag->event); + else + arg = NULL; + + delete ev_tag; + return arg; } int EventScheduler::checkDelay() { - if (!tasks) + if (!used) return EVENT_IDLE; - int result = (int) ((tasks->when - current_dtime) * 1000); + int result = (int) ((tasks[1]->when - current_dtime) * 1000); if (result < 0) return 0; @@ -236,23 +265,35 @@ int EventScheduler::checkEvents(int timeout) { - ev_entry *event = NULL; + ev_tag *ev_tag; - if (NULL == tasks) + if (!used) return checkDelay(); - if (tasks->when > current_dtime) + event = tasks[1]; + if (event->when > current_dtime) return checkDelay(); PROF_start(eventRun); debugs(41, 5, HERE << "checkEvents"); - while ((event = tasks)) { - if (event->when > current_dtime) - break; - + do { + if (used > 1) { + tasks[1] = tasks[used--]; + tasks[1]->slot = 1; + + if (used > 1) + downHeap(1); + } else + used = 0; + + + ev_tag = static_cast<class ev_tag *>(event->tag); + if (ev_tag) + ev_tag->event = NULL; + /* XXX assumes event->name is static memory! */ AsyncCall::Pointer call = asyncCall(41,5, event->name, EventDialer(event->func, event->arg, event->cbdata)); @@ -262,14 +303,13 @@ const bool heavy = event->weight && (!event->cbdata || cbdataReferenceValid(event->arg)); - tasks = event->next; - delete event; + delete event; // XXX: We may be called again during the same event loop iteration. // Is there a point in breaking now? if (heavy) break; // do not dequeue events following a heavy event - } + } while (used && (event = tasks[1], event->when <= current_dtime)); PROF_stop(eventRun); return checkDelay(); @@ -278,46 +318,72 @@ void EventScheduler::clean() { - while (ev_entry * event = tasks) { - tasks = event->next; - delete event; - } - + ev_entry **t, *event; + ev_tag *ev_tag; + unsigned u; + + t = tasks; + if (!t) + return; + u = used; + if (!u) + return; + tasks = NULL; + max = used = 0; + + do { + event = t[u]; + + ev_tag = static_cast<class ev_tag *>(event->tag); + if (ev_tag) + ev_tag->event = NULL; + + delete event; + } while (--u); + + xfree(t); } void EventScheduler::dump(StoreEntry * sentry) { - - ev_entry *e = tasks; + ev_entry *e; + unsigned ndx; if (last_event_ran) storeAppendPrintf(sentry, "Last event to run: %s\n\n", last_event_ran); + if (!used) + return; + storeAppendPrintf(sentry, "%-25s\t%-15s\t%s\t%s\n", "Operation", "Next Execution", "Weight", "Callback Valid?"); - while (e != NULL) { - storeAppendPrintf(sentry, "%-25s\t%0.3f sec\t%5d\t %s\n", + ndx = 1; + do { + e = tasks[ndx]; + storeAppendPrintf(sentry, "%-25s\t%0.3f sec\t%5d\t %s\n", e->name, e->when ? e->when - current_dtime : 0, e->weight, (e->arg && e->cbdata) ? cbdataReferenceValid(e->arg) ? "yes" : "no" : "N/A"); - e = e->next; - } + + } while (++ndx <= used); } bool EventScheduler::find(EVH * func, void * arg) { + unsigned ndx; - ev_entry *event; + ndx = 1; + while (ndx < used) { + if (tasks[ndx]->func == func && tasks[ndx]->arg == arg) + return true; - for (event = tasks; event != NULL; event = event->next) { - if (event->func == func && event->arg == arg) - return true; + ++ndx; } return false; @@ -330,23 +396,148 @@ } void -EventScheduler::schedule(const char *name, EVH * func, void *arg, double when, int weight, bool cbdata) +EventScheduler::schedule(const char *name, EVH * func, void *arg, double when, int weight, bool cbdata, + void **tag) { + if (used == max) + growTasks(); + // Use zero timestamp for when=0 events: Many of them are async calls that // must fire in the submission order. We cannot use current_dtime for them // because it may decrease if system clock is adjusted backwards. const double timestamp = when > 0.0 ? current_dtime + when : 0; ev_entry *event = new ev_entry(name, func, arg, timestamp, weight, cbdata); - ev_entry **E; debugs(41, 7, HERE << "schedule: Adding '" << name << "', in " << when << " seconds"); - /* Insert after the last event with the same or earlier time */ - for (E = &tasks; *E; E = &(*E)->next) { - if ((*E)->when > event->when) - break; + tasks[++used] = event; + event->slot = used; + if (used > 1) + upHeap(used); + + if (tag) { + ev_tag *ev_tag = new class ev_tag; + ev_tag->event = event; + *tag = ev_tag; + + event->tag = ev_tag; + } +} + +void +EventScheduler::releaseTag(void *tag) +{ + ev_entry *event; + ev_tag *ev_tag; + + ev_tag = static_cast<class ev_tag *>(tag); + + event = ev_tag->event; + if (event) + event->tag = NULL; + + delete ev_tag; +} + +void * +EventScheduler::cancelEvent(ev_entry *event) +{ + ev_tag *ev_tag; + void *arg; + unsigned ndx; + + if (!tasks) + return NULL; + + ndx = event->slot; + if (ndx < used) { + tasks[ndx] = tasks[used--]; + tasks[ndx]->slot = ndx; + + if (used > 1) { + if (ndx > 1 && tasks[ndx]->when < tasks[ndx / 2]->when) + upHeap(ndx); + else if (ndx <= used / 2) + downHeap(ndx); + } + } else + --used; + + arg = event->arg; + + ev_tag = static_cast<class ev_tag *>(event->tag); + if (ev_tag) ev_tag->event = NULL; + + delete event; + + return arg; +} + +void +EventScheduler::growTasks() +{ + void *p; + unsigned want; + + want = tasks ? (max + 1) * 2 : INITIAL_SIZE; + p = xrealloc(tasks, want * sizeof(*tasks)); + tasks = static_cast<ev_entry **>(p); + max = want - 1; +} + +void +EventScheduler::upHeap(unsigned ndx) +{ + ev_entry *event; + double when; + unsigned next, cur; + + event = tasks[ndx]; + when = event->when; + cur = ndx; + do { + next = cur / 2; + if (when >= tasks[next]->when) + break; + + tasks[cur] = tasks[next]; + tasks[cur]->slot = cur; + + cur = next; + } while (cur > 1); + + if (cur != ndx) { + tasks[cur] = event; + event->slot = cur; } +} - event->next = *E; - *E = event; +void +EventScheduler::downHeap(unsigned ndx) +{ + ev_entry *event; + double when; + unsigned next, cur; + + event = tasks[ndx]; + when = event->when; + cur = ndx; + do { + next = cur * 2; + if (next < used && tasks[next]->when > tasks[next + 1]->when) + ++next; + + if (when <= tasks[next]->when) + break; + + tasks[cur] = tasks[next]; + tasks[cur]->slot = cur; + + cur = next; + } while (cur <= used / 2); + + if (cur != ndx) { + tasks[cur] = event; + event->slot = cur; + } } --- mad-squid-log-sched/src/event.h 8 Jan 2013 17:36:44 -0000 1.1.1.3 +++ mad-squid-log-sched/src/event.h 29 Jan 2013 21:22:25 -0000 @@ -42,16 +42,19 @@ typedef void EVH(void *); -void eventAdd(const char *name, EVH * func, void *arg, double when, int, bool cbdata=true); -void eventAddIsh(const char *name, EVH * func, void *arg, double delta_ish, int); +void eventAdd(const char *name, EVH * func, void *arg, double when, int, bool cbdata=true, + void **tag = NULL); +void eventAddIsh(const char *name, EVH * func, void *arg, double delta_ish, int, + void **tag = NULL); void eventDelete(EVH * func, void *arg); +void *eventDelete(void *tag); +void eventReleaseTag(void *tag); void eventInit(void); void eventFreeMemory(void); int eventFind(EVH *, void *); class ev_entry { - public: ev_entry(char const * name, EVH * func, void *arg, double when, int weight, bool cbdata=true); ~ev_entry(); @@ -64,7 +67,8 @@ int weight; bool cbdata; - ev_entry *next; + unsigned slot; + void *tag; }; MEMPROXY_CLASS_INLINE(ev_entry); @@ -78,6 +82,7 @@ ~EventScheduler(); /* cancel a scheduled but not dispatched event */ void cancel(EVH * func, void * arg); + void *cancel(void *tag); /* clean up the used memory in the scheduler */ void clean(); /* how long until the next event ? */ @@ -87,13 +92,21 @@ /* find a scheduled event */ bool find(EVH * func, void * arg); /* schedule a callback function to run in when seconds */ - void schedule(const char *name, EVH * func, void *arg, double when, int weight, bool cbdata=true); + void schedule(const char *name, EVH * func, void *arg, double when, int weight, bool cbdata=true, + void **tag = NULL); int checkEvents(int timeout); + void releaseTag(void *tag); static EventScheduler *GetInstance(); private: static EventScheduler _instance; - ev_entry * tasks; + ev_entry **tasks; + unsigned used, max; + + void *cancelEvent(ev_entry *event); + void growTasks(); + void upHeap(unsigned ndx); + void downHeap(unsigned ndx); }; #endif /* SQUID_EVENT_H */
