WvStreams
wvtask.cc
00001 /*
00002  * Worldvisions Weaver Software:
00003  *   Copyright (C) 1997-2002 Net Integration Technologies, Inc.
00004  * 
00005  * A set of classes that provide co-operative multitasking support.  See
00006  * wvtask.h for more information.
00007  */
00008 
00009 #include "wvautoconf.h"
00010 #ifdef __GNUC__
00011 # define alloca __builtin_alloca
00012 #else
00013 # ifdef _MSC_VER
00014 #  include <malloc.h>
00015 #  define alloca _alloca
00016 # else
00017 #  if HAVE_ALLOCA_H
00018 #   include <alloca.h>
00019 #  else
00020 #   ifdef _AIX
00021 #pragma alloca
00022 #   else
00023 #    ifndef alloca /* predefined by HP cc +Olibcalls */
00024 char *alloca ();
00025 #    endif
00026 #   endif
00027 #  endif
00028 # endif
00029 #endif
00030 
00031 #include "wvtask.h"
00032 #include <stdio.h>
00033 #include <stdlib.h>
00034 #include <assert.h>
00035 #include <sys/mman.h>
00036 #include <signal.h>
00037 #include <unistd.h>
00038 #include <sys/resource.h>
00039 
00040 #ifdef HAVE_VALGRIND_MEMCHECK_H
00041 #include <valgrind/memcheck.h>
00042 // Compatibility for Valgrind 3.1 and previous
00043 #ifndef VALGRIND_MAKE_MEM_DEFINED
00044 #define VALGRIND_MAKE_MEM_DEFINED VALGRIND_MAKE_READABLE 
00045 #endif
00046 #else
00047 #define VALGRIND_MAKE_MEM_DEFINED(x, y)
00048 #define RUNNING_ON_VALGRIND 0
00049 #endif
00050 
00051 #define TASK_DEBUG 0
00052 #if TASK_DEBUG
00053 # define Dprintf(fmt, args...) fprintf(stderr, fmt, ##args)
00054 #else
00055 # define Dprintf(fmt, args...)
00056 #endif
00057 
00058 int WvTask::taskcount, WvTask::numtasks, WvTask::numrunning;
00059 
00060 WvTaskMan *WvTaskMan::singleton;
00061 int WvTaskMan::links;
00062 int volatile WvTaskMan::magic_number;
00063 WvTaskList WvTaskMan::all_tasks, WvTaskMan::free_tasks;
00064 ucontext_t WvTaskMan::stackmaster_task, WvTaskMan::get_stack_return,
00065     WvTaskMan::toplevel;
00066 WvTask *WvTaskMan::current_task, *WvTaskMan::stack_target;
00067 char *WvTaskMan::stacktop;
00068 
00069 static int context_return;
00070 
00071 
00072 static bool use_shared_stack()
00073 {
00074     return RUNNING_ON_VALGRIND;
00075 }
00076 
00077 
00078 static void valgrind_fix(char *stacktop)
00079 {
00080 #ifdef HAVE_VALGRIND_MEMCHECK_H
00081     char val;
00082     //printf("valgrind fix: %p-%p\n", &val, stacktop);
00083     assert(stacktop > &val);
00084 #endif
00085     VALGRIND_MAKE_MEM_DEFINED(&val, stacktop - &val);
00086 }
00087 
00088 
00089 WvTask::WvTask(WvTaskMan &_man, size_t _stacksize) : man(_man)
00090 {
00091     stacksize = _stacksize;
00092     running = recycled = false;
00093     func = NULL;
00094     userdata = NULL;
00095     
00096     tid = ++taskcount;
00097     numtasks++;
00098     magic_number = WVTASK_MAGIC;
00099     stack_magic = NULL;
00100     
00101     man.get_stack(*this, stacksize);
00102 
00103     man.all_tasks.append(this, false);
00104 }
00105 
00106 
00107 WvTask::~WvTask()
00108 {
00109     numtasks--;
00110     if (running)
00111         numrunning--;
00112     magic_number = 42;
00113 }
00114 
00115 
00116 void WvTask::start(WvStringParm _name, TaskFunc *_func, void *_userdata)
00117 {
00118     assert(!recycled);
00119     name = _name;
00120     func = _func;
00121     userdata = _userdata;
00122     running = true;
00123     numrunning++;
00124 }
00125 
00126 
00127 void WvTask::recycle()
00128 {
00129     assert(!running);
00130     
00131     if (!running && !recycled)
00132     {
00133         man.free_tasks.append(this, true);
00134         recycled = true;
00135     }
00136 }
00137 
00138 
00139 WvTaskMan *WvTaskMan::get()
00140 {
00141     if (!links)
00142         singleton = new WvTaskMan;
00143     links++;
00144     return singleton;
00145 }
00146 
00147 
00148 void WvTaskMan::unlink()
00149 {
00150     links--;
00151     if (!links)
00152     {
00153         delete singleton;
00154         singleton = NULL;
00155     }
00156 }
00157 
00158 
00159 static inline const char *Yes_No(bool val)
00160 {
00161     return val? "Yes": "No";
00162 }
00163 
00164 
00165 WvString WvTaskMan::debugger_tasks_run_cb(WvStringParm cmd, WvStringList &args,
00166         WvStreamsDebugger::ResultCallback result_cb, void *)
00167 {
00168     const char *format_str = "%5s%s%7s%s%8s%s%6s%s%s";
00169     WvStringList result;
00170     result.append(format_str, "--TID", "-", "Running", "-", "Recycled", "-", "-StkSz", "-", "Name-----");
00171     result_cb(cmd, result);
00172     WvTaskList::Iter i(all_tasks);
00173     for (i.rewind(); i.next(); )
00174     {
00175         result.zap();
00176         result.append(format_str, i->tid, " ",
00177                 Yes_No(i->running), " ",
00178                 Yes_No(i->recycled), " ",
00179                 i->stacksize, " ",
00180                 i->name);
00181         result_cb(cmd, result);
00182     }
00183     return WvString::null;
00184 }
00185 
00186 
00187 WvTaskMan::WvTaskMan()
00188 {
00189     static bool first = true;
00190     if (first)
00191     {
00192         first = false;
00193         WvStreamsDebugger::add_command("tasks", 0, debugger_tasks_run_cb, 0);
00194     }
00195 
00196     stack_target = NULL;
00197     current_task = NULL;
00198     magic_number = -WVTASK_MAGIC;
00199     
00200     stacktop = (char *)alloca(0);
00201     
00202     context_return = 0;
00203     assert(getcontext(&get_stack_return) == 0);
00204     if (context_return == 0)
00205     {
00206         // initial setup - start the stackmaster() task (never returns!)
00207         stackmaster();
00208     }
00209     // if we get here, stackmaster did a longjmp back to us.
00210 }
00211 
00212 
00213 WvTaskMan::~WvTaskMan()
00214 {    
00215     magic_number = -42;
00216     free_tasks.zap();
00217 }
00218 
00219 
00220 WvTask *WvTaskMan::start(WvStringParm name, 
00221                          WvTask::TaskFunc *func, void *userdata,
00222                          size_t stacksize)
00223 {
00224     WvTask *t;
00225     
00226     WvTaskList::Iter i(free_tasks);
00227     for (i.rewind(); i.next(); )
00228     {
00229         if (i().stacksize >= stacksize)
00230         {
00231             t = &i();
00232             i.set_autofree(false);
00233             i.unlink();
00234             t->recycled = false;
00235             t->start(name, func, userdata);
00236             return t;
00237         }
00238     }
00239     
00240     // if we get here, no matching task was found.
00241     t = new WvTask(*this, stacksize);
00242     t->start(name, func, userdata);
00243     return t;
00244 }
00245 
00246 
00247 int WvTaskMan::run(WvTask &task, int val)
00248 {
00249     assert(magic_number == -WVTASK_MAGIC);
00250     assert(task.magic_number == WVTASK_MAGIC);
00251     assert(!task.recycled);
00252     
00253     Dprintf("WvTaskMan: running task #%d with value %d (%s)\n",
00254             task.tid, val, (const char *)task.name);
00255     
00256     if (&task == current_task)
00257         return val; // that's easy!
00258         
00259     WvTask *old_task = current_task;
00260     current_task = &task;
00261     ucontext_t *state;
00262     
00263     if (!old_task)
00264         state = &toplevel; // top-level call (not in an actual task yet)
00265     else
00266         state = &old_task->mystate;
00267     
00268     context_return = 0;
00269     assert(getcontext(state) == 0);
00270     int newval = context_return;
00271     if (newval == 0)
00272     {
00273         // saved the state, now run the task.
00274         context_return = val;
00275         setcontext(&task.mystate);
00276         return -1;
00277     }
00278     else
00279     {
00280         // need to make state readable to see if we need to make more readable..
00281         VALGRIND_MAKE_MEM_DEFINED(&state, sizeof(state));
00282         // someone did yield() (if toplevel) or run() on our old task; done.
00283         if (state != &toplevel)
00284             valgrind_fix(stacktop);
00285         current_task = old_task;
00286         return newval;
00287     }
00288 }
00289 
00290 
00291 int WvTaskMan::yield(int val)
00292 {
00293     if (!current_task)
00294         return 0; // weird...
00295     
00296     Dprintf("WvTaskMan: yielding from task #%d with value %d (%s)\n",
00297            current_task->tid, val, (const char *)current_task->name);
00298     
00299     assert(current_task->stack_magic);
00300     
00301     // if this fails, this task overflowed its stack.  Make it bigger!
00302     VALGRIND_MAKE_MEM_DEFINED(current_task->stack_magic,
00303                            sizeof(current_task->stack_magic));
00304     assert(*current_task->stack_magic == WVTASK_MAGIC);
00305 
00306 #if TASK_DEBUG
00307     if (use_shared_stack())
00308     {
00309         size_t stackleft;
00310         char *stackbottom = (char *)(current_task->stack_magic + 1);
00311         for (stackleft = 0; stackleft < current_task->stacksize; stackleft++)
00312         {
00313             if (stackbottom[stackleft] != 0x42)
00314                 break;
00315         }
00316         Dprintf("WvTaskMan: remaining stack after #%d (%s): %ld/%ld\n",
00317                 current_task->tid, current_task->name.cstr(), (long)stackleft,
00318                 (long)current_task->stacksize);
00319     }
00320 #endif
00321                 
00322     context_return = 0;
00323     assert(getcontext(&current_task->mystate) == 0);
00324     int newval = context_return;
00325     if (newval == 0)
00326     {
00327         // saved the task state; now yield to the toplevel.
00328         context_return = val;
00329         setcontext(&toplevel);
00330         return -1;
00331     }
00332     else
00333     {
00334         // back via longjmp, because someone called run() again.  Let's go
00335         // back to our running task...
00336         valgrind_fix(stacktop);
00337         return newval;
00338     }
00339 }
00340 
00341 
00342 void WvTaskMan::get_stack(WvTask &task, size_t size)
00343 {
00344     context_return = 0;
00345     assert(getcontext(&get_stack_return) == 0);
00346     if (context_return == 0)
00347     {
00348         assert(magic_number == -WVTASK_MAGIC);
00349         assert(task.magic_number == WVTASK_MAGIC);
00350 
00351         if (!use_shared_stack())
00352         {
00353 #if defined(__linux__) && (defined(__386__) || defined(__i386) || defined(__i386__))
00354             static char *next_stack_addr = (char *)0xB0000000;
00355             static const size_t stack_shift = 0x00100000;
00356 
00357             next_stack_addr -= stack_shift;
00358 #else
00359             static char *next_stack_addr = NULL;
00360 #endif
00361         
00362             task.stack = mmap(next_stack_addr, task.stacksize,
00363                 PROT_READ | PROT_WRITE,
00364 #ifndef MACOS 
00365                 MAP_PRIVATE | MAP_ANONYMOUS,
00366 #else
00367                 MAP_PRIVATE,
00368 #endif
00369                 -1, 0);
00370         }
00371         
00372         // initial setup
00373         stack_target = &task;
00374         context_return = size/1024 + (size%1024 > 0);
00375         setcontext(&stackmaster_task);
00376     }
00377     else
00378     {
00379         if (current_task)
00380             valgrind_fix(stacktop);
00381         assert(magic_number == -WVTASK_MAGIC);
00382         assert(task.magic_number == WVTASK_MAGIC);
00383         
00384         // back from stackmaster - the task is now set up.
00385         return;
00386     }
00387 }
00388 
00389 
00390 void WvTaskMan::stackmaster()
00391 {
00392     // leave lots of room on the "main" stack before doing our magic
00393     alloca(1024*1024);
00394     
00395     _stackmaster();
00396 }
00397 
00398 
00399 void WvTaskMan::_stackmaster()
00400 {
00401     int val;
00402     size_t total;
00403     
00404     Dprintf("stackmaster 1\n");
00405     
00406     // the main loop runs once from the constructor, and then once more
00407     // after each stack allocation.
00408     for (;;)
00409     {
00410         assert(magic_number == -WVTASK_MAGIC);
00411         
00412         context_return = 0;
00413         assert(getcontext(&stackmaster_task) == 0);
00414         val = context_return;
00415         if (val == 0)
00416         {
00417             assert(magic_number == -WVTASK_MAGIC);
00418             
00419             // just did setjmp; save stackmaster's current state (with
00420             // all current stack allocations) and go back to get_stack
00421             // (or the constructor, if that's what called us)
00422             context_return = 1;
00423             setcontext(&get_stack_return);
00424         }
00425         else
00426         {
00427             valgrind_fix(stacktop);
00428             assert(magic_number == -WVTASK_MAGIC);
00429             
00430             total = (val+1) * (size_t)1024;
00431             
00432             if (!use_shared_stack())
00433                 total = 1024; // enough to save the do_task stack frame
00434 
00435             // set up a stack frame for the new task.  This runs once
00436             // per get_stack.
00437             //alloc_stack_and_switch(total);
00438             do_task();
00439             
00440             assert(magic_number == -WVTASK_MAGIC);
00441 
00442             // allocate the stack area so we never use it again
00443             alloca(total);
00444 
00445             // a little sentinel so we can detect stack overflows
00446             stack_target->stack_magic = (int *)alloca(sizeof(int));
00447             *stack_target->stack_magic = WVTASK_MAGIC;
00448             
00449             // clear the stack to 0x42 so we can count unused stack
00450             // space later.
00451 #if TASK_DEBUG
00452             memset(stack_target->stack_magic + 1, 0x42, total - 1024);
00453 #endif
00454         }
00455     }
00456 }
00457 
00458 
00459 void WvTaskMan::call_func(WvTask *task)
00460 {
00461     Dprintf("WvTaskMan: calling task #%d (%s)\n",
00462             task->tid, (const char *)task->name);
00463     task->func(task->userdata);
00464     Dprintf("WvTaskMan: returning from task #%d (%s)\n",
00465             task->tid, (const char *)task->name);
00466     context_return = 1;
00467 }
00468 
00469 
00470 void WvTaskMan::do_task()
00471 {
00472     assert(magic_number == -WVTASK_MAGIC);
00473     WvTask *task = stack_target;
00474     assert(task->magic_number == WVTASK_MAGIC);
00475         
00476     // back here from longjmp; someone wants stack space.    
00477     context_return = 0;
00478     assert(getcontext(&task->mystate) == 0);
00479     if (context_return == 0)
00480     {
00481         // done the setjmp; that means the target task now has
00482         // a working jmp_buf all set up.  Leave space on the stack
00483         // for his data, then repeat the loop in _stackmaster (so we can
00484         // return to get_stack(), and allocate more stack for someone later)
00485         // 
00486         // Note that nothing on the allocated stack needs to be valid; when
00487         // they longjmp to task->mystate, they'll have a new stack pointer
00488         // and they'll already know what to do (in the 'else' clause, below)
00489         Dprintf("stackmaster 5\n");
00490         return;
00491     }
00492     else
00493     {
00494         // someone did a run() on the task, which
00495         // means they're ready to make it go.  Do it.
00496         valgrind_fix(stacktop);
00497         for (;;)
00498         {
00499             assert(magic_number == -WVTASK_MAGIC);
00500             assert(task);
00501             assert(task->magic_number == WVTASK_MAGIC);
00502             
00503             if (task->func && task->running)
00504             {
00505                 if (use_shared_stack())
00506                 {
00507                     // this is the task's main function.  It can call yield()
00508                     // to give up its timeslice if it wants.  Either way, it
00509                     // only returns to *us* if the function actually finishes.
00510                     task->func(task->userdata);
00511                 }
00512                 else
00513                 {
00514                     assert(getcontext(&task->func_call) == 0);
00515                     task->func_call.uc_stack.ss_size = task->stacksize;
00516                     task->func_call.uc_stack.ss_sp = task->stack;
00517                     task->func_call.uc_stack.ss_flags = 0;
00518                     task->func_call.uc_link = &task->func_return;
00519                     Dprintf("WvTaskMan: makecontext #%d (%s)\n",
00520                             task->tid, (const char *)task->name);
00521                     makecontext(&task->func_call,
00522                             (void (*)(void))call_func, 1, task);
00523 
00524                     context_return = 0;
00525                     assert(getcontext(&task->func_return) == 0);
00526                     if (context_return == 0)
00527                         setcontext(&task->func_call);
00528                 }
00529                 
00530                 // the task's function terminated.
00531                 task->name = "DEAD";
00532                 task->running = false;
00533                 task->numrunning--;
00534             }
00535             yield();
00536         }
00537     }
00538 }
00539 
00540 
00541 const void *WvTaskMan::current_top_of_stack()
00542 {
00543 #ifdef HAVE_LIBC_STACK_END
00544     extern const void *__libc_stack_end;
00545     if (use_shared_stack() || current_task == NULL)
00546         return __libc_stack_end;
00547     else
00548         return (const char *)current_task->stack + current_task->stacksize;
00549 #else
00550     return 0;
00551 #endif
00552 }
00553 
00554 
00555 size_t WvTaskMan::current_stacksize_limit()
00556 {
00557     if (use_shared_stack() || current_task == NULL)
00558     {
00559         struct rlimit rl;
00560         if (getrlimit(RLIMIT_STACK, &rl) == 0)
00561             return size_t(rl.rlim_cur);
00562         else
00563             return 0;
00564     }
00565     else
00566         return size_t(current_task->stacksize);
00567 }
00568 
00569