# HG changeset patch # User Jens Alfke # Date 1209590329 25200 # Node ID 2475f871c218f0c5078bba6772724dc9d109f584 # Parent deb0ee0c5b21fae3b2451277ea5965f0cb8ae54e Rewrote CoroX. Simplified APIs. Improved stack size checks. diff -r deb0ee0c5b21 -r 2475f871c218 Actors.xcodeproj/project.pbxproj --- a/Actors.xcodeproj/project.pbxproj Tue Apr 29 17:05:32 2008 -0700 +++ b/Actors.xcodeproj/project.pbxproj Wed Apr 30 14:18:49 2008 -0700 @@ -86,9 +86,9 @@ children = ( 2703CFE20DC796DC00DD026B /* MYCoroutine.h */, 2703CFE30DC796DC00DD026B /* MYCoroutine.m */, - 2703D28A0DC7EC5A00DD026B /* MYCoroutineTest.m */, 2703D1BC0DC7DAD100DD026B /* CoroX.h */, 2703D1BD0DC7DAD100DD026B /* CoroX.c */, + 2703D28A0DC7EC5A00DD026B /* MYCoroutineTest.m */, ); path = Coroutines; sourceTree = ""; diff -r deb0ee0c5b21 -r 2475f871c218 Coroutines/CoroX.c --- a/Coroutines/CoroX.c Tue Apr 29 17:05:32 2008 -0700 +++ b/Coroutines/CoroX.c Wed Apr 30 14:18:49 2008 -0700 @@ -5,9 +5,6 @@ * Created by Jens Alfke on 4/29/08. * Adapted from Steve Dekorte's libCoroutine: * - * by putting it on a piece of wood and banging a few nails through it. - * No, actually I removed all the stuff for cross-platform support, leaving only the simple - * code that works on Mac OS X 10.5, and then cleaned things up a bit. * * Copyright 2008 Jens Alfke. All rights reserved. * Copyright (c) 2002, 2003 Steve Dekorte. All rights reserved. @@ -15,142 +12,142 @@ * */ +#define _XOPEN_SOURCE /* decl of ucontext_t in is wrong unless this is defined */ + #include "CoroX.h" +#include +#include +#include #include -#include -#include -#include +// Experimentally, the coroutine bus-errors when its stack space drops below about 10k, +// implying that the kernel unmaps the very end of it. So allow extra room: +#define STACK_OVERHEAD (12*1024) -#define CORO_DEFAULT_STACK_SIZE (65536*4) -#define CORO_STACK_SIZE_MIN 8192 +// Even with that overhead, stack sizes less than this cause an immediate crash: +const size_t kCoroX_minStackSize = 20*1024; -struct Coro +struct CoroX { size_t stackSize; void *stack; + CoroEntryPoint entryPoint; + void *userData; ucontext_t env; - // The following field works around bug(?) in sys/_structs.h. This field should be part of ucontext_t: - _STRUCT_MCONTEXT env_registers; - unsigned char isMain; }; -typedef struct CallbackBlock +CoroX *CoroX_new(CoroEntryPoint entryPoint, void *userData) { - void *context; - CoroStartCallback *func; -} CallbackBlock; - - -Coro *Coro_new(void) -{ - Coro *self = (Coro *)calloc(1, sizeof(Coro)); - self->stackSize = CORO_DEFAULT_STACK_SIZE; - self->stack = NULL; + CoroX *self = (CoroX *)calloc(1, sizeof(CoroX)); + self->stackSize = CoroX_getDefaultStackSize(); + self->entryPoint = entryPoint; + self->userData = userData; return self; } -void Coro_free(Coro *self) +void CoroX_free(CoroX *self) { - if (self->stack) - free(self->stack); - free(self); + if( self ) { + if (self->stack) + free(self->stack); + free(self); + } } +void* CoroX_userData(CoroX *self) {return self->userData;} +bool CoroX_isMain(CoroX *self) {return self->entryPoint==NULL;} -void *Coro_stack(Coro *self) + +#pragma mark STACK: + + +void* CoroX_stack(CoroX *self) {return self->stack;} +size_t CoroX_stackSize(CoroX *self) {return self->stackSize;} + +void CoroX_setStackSize_(CoroX *self, size_t sizeInBytes) { - return self->stack; -} - -size_t Coro_stackSize(Coro *self) -{ - return self->stackSize; -} - -void Coro_setStackSize_(Coro *self, size_t sizeInBytes) -{ + if( sizeInBytes < kCoroX_minStackSize ) + sizeInBytes = kCoroX_minStackSize; self->stackSize = sizeInBytes; } -uint8_t *Coro_CurrentStackPointer(void) __attribute__ ((noinline)); -uint8_t *Coro_CurrentStackPointer(void) +static size_t sDefaultStackSize; + +size_t CoroX_getDefaultStackSize(void) +{ + if( sDefaultStackSize == 0 ) { + pthread_attr_t pthreadAttrs; // Find out default pthread stack size + int err = pthread_attr_init(&pthreadAttrs); + if( ! err ) + err = pthread_attr_getstacksize(&pthreadAttrs, &sDefaultStackSize); + if (err) + sDefaultStackSize = 512*1024; + } + return sDefaultStackSize; +} + +void CoroX_setDefaultStackSize( size_t size ) +{ + sDefaultStackSize = size; +} + + + __attribute__ ((noinline)) +static uint8_t *CoroX_CurrentStackPointer(void) { uint8_t a; uint8_t *b = &a; return b; } -size_t Coro_bytesLeftOnStack(Coro *self) +size_t CoroX_bytesLeftOnStack(CoroX *self) { uint8_t dummy; ptrdiff_t p1 = (ptrdiff_t)(&dummy); - ptrdiff_t p2 = (ptrdiff_t)Coro_CurrentStackPointer(); + ptrdiff_t p2 = (ptrdiff_t)CoroX_CurrentStackPointer(); int stackMovesUp = p2 > p1; - ptrdiff_t start = ((ptrdiff_t)self->stack); + ptrdiff_t start = ((ptrdiff_t)self->stack) ; ptrdiff_t end = start + self->stackSize; if (stackMovesUp) - { - return end - p1; - } + return end - p1 - STACK_OVERHEAD; else - { - return p1 - start; - } + return p1 - start - STACK_OVERHEAD; } -int Coro_stackSpaceAlmostGone(Coro *self) +int CoroX_stackSpaceAlmostGone(CoroX *self) { - return Coro_bytesLeftOnStack(self) < CORO_STACK_SIZE_MIN; + return CoroX_bytesLeftOnStack(self) < 2048; } -void Coro_initializeMainCoro(Coro *self) -{ - self->isMain = 1; -} +#pragma mark SETUP & SWITCH: -static void Coro_StartWithArg(CallbackBlock *block) -{ - (block->func)(block->context); - fprintf(stderr,"CoroX error: returned from coro start function\n"); - abort(); -} - typedef void (*makecontext_func)(void); -static void Coro_setup(Coro *self, void *arg) +static void CoroX_setup_(CoroX *self) { - ucontext_t *ucp = (ucontext_t *) &self->env; - getcontext(ucp); + size_t stackSize = self->stackSize + STACK_OVERHEAD; + self->stack = valloc(stackSize); + assert(self->stack); - ucp->uc_stack.ss_sp = Coro_stack(self); - ucp->uc_stack.ss_size = Coro_stackSize(self); - ucp->uc_stack.ss_flags = 0; - ucp->uc_link = NULL; - - makecontext(ucp, (makecontext_func)Coro_StartWithArg, 1, arg); + getcontext(&self->env); + self->env.uc_stack.ss_sp = self->stack; + self->env.uc_stack.ss_size = stackSize; + self->env.uc_stack.ss_flags = 0; + self->env.uc_link = NULL; + makecontext(&self->env, (makecontext_func)self->entryPoint, 1, self); } -void Coro_startCoro_(Coro *self, Coro *other, void *context, CoroStartCallback *callback) +void CoroX_switchTo_(CoroX *self, CoroX *next) { - assert(other->stack==NULL); - other->stack = calloc(1, other->stackSize + 16); - - CallbackBlock callbackBlock = {context,callback}; - Coro_setup(other, &callbackBlock); - - Coro_switchTo_(self, other); -} - -void Coro_switchTo_(Coro *self, Coro *next) -{ + if( ! next->stack && next->entryPoint ) + CoroX_setup_(next); swapcontext(&self->env, &next->env); } diff -r deb0ee0c5b21 -r 2475f871c218 Coroutines/CoroX.h --- a/Coroutines/CoroX.h Tue Apr 29 17:05:32 2008 -0700 +++ b/Coroutines/CoroX.h Wed Apr 30 14:18:49 2008 -0700 @@ -5,9 +5,6 @@ * Created by Jens Alfke on 4/29/08. * Adapted from Steve Dekorte's libCoroutine: * - * by putting it on a piece of wood and banging a few nails through it. - * No, actually I removed all the stuff for cross-platform support, leaving only the simple - * code that works on Mac OS X 10.5, and then cleaned things up a bit. * * Copyright 2008 Jens Alfke. All rights reserved. * Copyright (c) 2002, 2003 Steve Dekorte. All rights reserved. @@ -18,6 +15,8 @@ #pragma once #include #include +#include + /** C coroutine implementation for Mac OS X. Based on, and API-compatible with, Steve Dekorte's libCoroutine. @@ -28,30 +27,30 @@ extern "C" { #endif - typedef struct Coro Coro; + typedef struct CoroX CoroX; - Coro *Coro_new(void); - void Coro_free(Coro *self); + typedef void (*CoroEntryPoint)(CoroX*); + + CoroX* CoroX_new(CoroEntryPoint, void *userData); // use entryPoint==NULL to init main Coro + void CoroX_free(CoroX*); - // stack + void CoroX_switchTo_(CoroX *current, CoroX *next); - void *Coro_stack(Coro *self); - size_t Coro_stackSize(Coro *self); - void Coro_setStackSize_(Coro *self, size_t sizeInBytes); - size_t Coro_bytesLeftOnStack(Coro *self); - int Coro_stackSpaceAlmostGone(Coro *self); + void* CoroX_userData(CoroX*); + bool CoroX_isMain(CoroX*); - // initialization + // Stack: + + extern const size_t kCoroX_minStackSize; // Minimum useable stack size - void Coro_initializeMainCoro(Coro *self); - - typedef void (CoroStartCallback)(void *); - - void Coro_startCoro_(Coro *self, Coro *other, void *context, CoroStartCallback *callback); - - // context-switch - - void Coro_switchTo_(Coro *self, Coro *next); + size_t CoroX_getDefaultStackSize(void); + void CoroX_setDefaultStackSize(size_t); + + void* CoroX_stack(CoroX*); + size_t CoroX_stackSize(CoroX*); + void CoroX_setStackSize_(CoroX*, size_t); + size_t CoroX_bytesLeftOnStack(CoroX*); + int CoroX_stackSpaceAlmostGone(CoroX*); #ifdef __cplusplus } diff -r deb0ee0c5b21 -r 2475f871c218 Coroutines/MYCoroutine.h --- a/Coroutines/MYCoroutine.h Tue Apr 29 17:05:32 2008 -0700 +++ b/Coroutines/MYCoroutine.h Wed Apr 30 14:18:49 2008 -0700 @@ -15,7 +15,8 @@ @interface MYCoroutine : NSObject { @private - struct Coro *_coro; + struct CoroX *_coro; + NSInvocation *_invocation; NSString *_name; } @@ -33,42 +34,42 @@ /** Creates but does not start a coroutine. */ - (id) init; -/** Starts a new coroutine, and performs the given invocation on it. - The current coroutine will block (i.e. this call won't return) - until some other coroutine tells it to resume. */ -- (void) startWithInvocation: (NSInvocation*)invocation; -/** Starts a new coroutine, invoking its -main method as its body. - Since the default implementation of -main is empty, this only makes sense to call - on an instance of a subclass of MYCoroutine that's overridden -main. - The current coroutine will block (i.e. this call won't return) - until some other coroutine tells it to resume. */ -- (void) start; +@property (retain) NSInvocation *invocation; + +/** The stack size of the coroutine. You can only change this before calling -start! */ +@property size_t stackSize; + +/** The coroutine's name. You can put anything you want here, as a debugging aid. */ +@property (copy) NSString* name; + /** The "main" method that will be called if the coroutine is started with -start. The default implementation is empty, so a subclass using -start must override this. */ - (void) main; -/** Returns control to an already-started (but blocked) coroutine. + +/** Returns control to a coroutine. The most recent -resume call made from within that coroutine will return. The current coroutine will block (i.e. this call won't return) until some other coroutine tells it to resume. */ - (void) resume; +- (id) call; -/** The coroutine's name. You can put anything you want here, as a debugging aid. */ -@property (copy) NSString* name; ++ (void) yieldToCaller: (id)value; + /** Returns YES if this is the currently executing coroutine. */ @property (readonly) BOOL isCurrent; -/** The stack size of the coroutine. You can only change this before calling -start! */ -@property size_t stackSize; - /** The number of bytes of stack space left on this coroutine. */ @property (readonly) size_t bytesLeftOnStack; /** Returns YES if this coroutine is almost out of stack space (less than 8k left) */ @property (readonly) BOOL stackSpaceAlmostGone; + ++ (void) setDefaultStackSize: (size_t)stackSize; + @end diff -r deb0ee0c5b21 -r 2475f871c218 Coroutines/MYCoroutine.m --- a/Coroutines/MYCoroutine.m Tue Apr 29 17:05:32 2008 -0700 +++ b/Coroutines/MYCoroutine.m Wed Apr 30 14:18:49 2008 -0700 @@ -12,7 +12,7 @@ #ifndef LogTo -#define kEnableLog 0 /* 1 enables logging, 0 disables it */ +#define kEnableLog 1 /* 1 enables logging, 0 disables it */ #define LogTo(DOMAIN,MSG,...) do{ if(kEnableLog) NSLog(@""#DOMAIN ": " MSG,__VA_ARGS__); }while(0) #endif @@ -21,20 +21,29 @@ #endif +static void MYCoroutineStart( CoroX *coro ); + + @implementation MYCoroutine static MYCoroutine *sMain, *sCurrent; +static NSMutableArray *sCallers; +static id sYieldResult; -+ (void) initialize + +- (id) _initMain { - if( self == [MYCoroutine class] ) { - sMain = [[self alloc] init]; - Coro_initializeMainCoro(sMain->_coro); - sMain.name = @"MAIN"; - sCurrent = sMain; + self = [super init]; + if (self != nil) { + NSAssert(!sMain,@"Already created a main coroutine"); + _coro = CoroX_new(NULL,NULL); + self.name = @"MAIN"; + sMain = self; + LogTo(Coroutine,@"INIT %@ : _coro=%p",self,_coro); } + return self; } @@ -42,7 +51,7 @@ { self = [super init]; if (self != nil) { - _coro = Coro_new(); + _coro = CoroX_new(&MYCoroutineStart,self); LogTo(Coroutine,@"INIT %@ : _coro=%p",self,_coro); } return self; @@ -52,11 +61,20 @@ - (void) dealloc { LogTo(Coroutine,@"DEALLOC %@",self); - Coro_free(_coro); + CoroX_free(_coro); [super dealloc]; } ++ (void) initialize +{ + if( self == [MYCoroutine class] ) { + sCurrent = [[self alloc] _initMain]; + sCallers = [[NSMutableArray alloc] init]; + } +} + + - (NSString*) description { if( _name ) @@ -66,7 +84,7 @@ } -@synthesize name=_name; +@synthesize name=_name, invocation=_invocation; + (MYCoroutine*) mainCoroutine {return sMain;} @@ -74,70 +92,88 @@ - (BOOL) isCurrent {return self==sCurrent;} -- (const void*) stack {return Coro_stack(_coro);} -- (size_t) stackSize {return Coro_stackSize(_coro);} -- (void) setStackSize: (size_t)size {Coro_setStackSize_(_coro,size);} +- (const void*) stack {return CoroX_stack(_coro);} +- (size_t) stackSize {return CoroX_stackSize(_coro);} +- (void) setStackSize: (size_t)size {CoroX_setStackSize_(_coro,size);} -- (size_t) bytesLeftOnStack {return Coro_bytesLeftOnStack(_coro);} -- (BOOL) stackSpaceAlmostGone {return Coro_stackSpaceAlmostGone(_coro);} ++ (void) setDefaultStackSize: (size_t)s {CoroX_setDefaultStackSize(s);} +- (size_t) bytesLeftOnStack {return CoroX_bytesLeftOnStack(_coro);} +- (BOOL) stackSpaceAlmostGone {return CoroX_stackSpaceAlmostGone(_coro);} -static void startWithInvocation( void *context ) +- (BOOL) hasStarted {return CoroX_stack(_coro)!=NULL || self==sMain;} + + +- (void) _start { - [(NSInvocation*)context invoke]; + if( _invocation ) + [_invocation invoke]; + else + [self main]; + // If body returns, yield control to caller: + LogTo(Coroutine,@"%@ finished",self); + [MYCoroutine yieldToCaller: nil]; } -static void startWithMain( void *context ) +static void MYCoroutineStart( CoroX *coro ) { - [(MYCoroutine*)context main]; -} - -- (void) startWithInvocation: (NSInvocation*)invocation -{ - LogTo(Coroutine,@"Starting %@ (currently in %@)",self,sCurrent); - MYCoroutine *current = sCurrent; - sCurrent = self; - - if( invocation ) - Coro_startCoro_(current->_coro, _coro, invocation, &startWithInvocation); - else - Coro_startCoro_(current->_coro, _coro, self, &startWithMain); - - sCurrent = current; - LogTo(Coroutine,@"...resumed %@ after starting %@",sCurrent,self); -} - -- (void) start -{ - [self startWithInvocation: nil]; + MYCoroutine *self = CoroX_userData(coro); + [self _start]; } + (MYCoroutine*) startWithInvocation: (NSInvocation*)invocation { MYCoroutine *cr = [[self alloc] init]; - [cr startWithInvocation: invocation]; + cr.invocation = invocation; + [cr resume]; return cr; } +- (void) main +{ + // subclasses should override this if they don't use an invocation. +} + + +#pragma mark - +#pragma mark CALLING: + + - (void) resume { LogTo(Coroutine,@"Resuming %@ (currently in %@)",self,sCurrent); MYCoroutine *current = sCurrent; sCurrent = self; - Coro_switchTo_(current->_coro,_coro); + CoroX_switchTo_(current->_coro,_coro); sCurrent = current; LogTo(Coroutine,@"...resumed %@",sCurrent); } -- (void) main +- (id) call { - // subclasses should override this. + NSAssert(sCurrent!=self,@"Cannot call the current coroutine"); + [sCallers addObject: sCurrent]; + [self resume]; + id result = sYieldResult; + sYieldResult = nil; + return result; } ++ (void) yieldToCaller: (id)value +{ + MYCoroutine *caller = sCallers.lastObject; + NSAssert(caller, @"No caller to yield to"); + sYieldResult = value; + [sCallers removeLastObject]; + [caller resume]; +} + + + @end diff -r deb0ee0c5b21 -r 2475f871c218 Coroutines/MYCoroutineTest.m --- a/Coroutines/MYCoroutineTest.m Tue Apr 29 17:05:32 2008 -0700 +++ b/Coroutines/MYCoroutineTest.m Wed Apr 30 14:18:49 2008 -0700 @@ -7,6 +7,7 @@ // #import "MYCoroutine.h" +#import "CoroX.h" @interface CoroTest1 : MYCoroutine @@ -45,6 +46,17 @@ @synthesize value; +- (void) regress: (int)depth +{ + char useUpSpace[1024]; + useUpSpace[0] = 0; + NSLog(@"infinite regress: depth=%i, stack space=%d", depth,self.bytesLeftOnStack); + if( [[MYCoroutine currentCoroutine] stackSpaceAlmostGone] ) + NSLog(@"infinite regress: bailing out!"); + else + [self regress: depth+1]; +} + - (void) main { int num = 0; @@ -53,7 +65,6 @@ secondCoro = [[CoroTest2 alloc] init]; secondCoro.name = @"second"; secondCoro.value = 2; - [secondCoro start]; while ( num < 100 ) { @@ -63,26 +74,78 @@ [secondCoro release]; + NSLog(@"*** TESTING STACK LIMITS ***"); + [self regress: 1]; + [[MYCoroutine mainCoroutine] resume]; } ++ (void) test +{ + NSLog(@"*** TESTING COROUTINES ***"); + firstCoro = [[CoroTest1 alloc] init]; + firstCoro.name = @"first"; + firstCoro.value = 1; + [firstCoro resume]; + + NSLog(@"Returned from coroutines; exiting"); + + [firstCoro release]; +} + @end + + +@interface Generator : MYCoroutine +{ int _count; } +- (id) initWithCount: (int)count; +@end + +@implementation Generator + +- (id) initWithCount: (int)count +{ + self = [super init]; + if (self != nil) { + _count = count; + } + return self; +} + + +- (void) main +{ + for( int i=1; i<=_count; i++ ) + [MYCoroutine yieldToCaller: [NSNumber numberWithInt: i]]; +} + ++ (void) test +{ + NSLog(@"*** TESTING GENERATOR ***"); + Generator *g = [[Generator alloc] initWithCount: 10]; + id value; + while( nil != (value = [g call]) ) + NSLog(@"Generator yielded %@",value); + NSLog(@"Generator returned nil"); +} + +@end + + + int main() { NSAutoreleasePool *pool = [NSAutoreleasePool new]; + NSLog(@"Starting test..."); - NSLog(@"Starting test..."); - //[[[NSThread alloc] init] start]; - firstCoro = [[CoroTest1 alloc] init]; - firstCoro.name = @"first"; - firstCoro.value = 1; - [firstCoro start]; + [MYCoroutine setDefaultStackSize: kCoroX_minStackSize]; - NSLog(@"Returned from coroutines; exiting"); + [CoroTest1 test]; - [firstCoro release]; + [Generator test]; + NSLog(@"FINISHED"); [pool drain]; }