Propstacklen: A program to calculate SPIN stack sizes
For some time now I've been working on a program that will calculate the stack size required for a SPIN program. It's now at the stage of generating output, and I'd like to gauge how much interest there'd be if I published it in the Obex.
At the moment, I believe the usual way to check stack size is to fill the stack area with longs of some value, and then run the program and see how many get overwritten. The snag with that technique is that it gives only a lower bound for the size - a program run with different inputs may send the stack deeper.
So I wrote propstacklen to carry out a static analysis of the SPIN program, from which the deepest possible stack can be traced. When run, propstacklen reads the .list and .eeprom files that the compiler generated, and generates a report showing the trace of method calls that will produce the maximum stack. In this way, the figures generated in the report are the upper bound on the stack size.
Here's the output from PlayWav_8bit.spin in the WavPlayers Obex object. This is about a simple as it gets, because that program has only two methods: a main method, and one that's called by main(). The maximum stack depth is 80 bytes
The other thing to note is that if you scroll to the bottom of the report, you'll find that BoeBotBasic has two methods (servoProcess and pingProcess) that are opened in seperate cogs. Propstacklen detects this, and reports on the stack sizes those cogs will need.
Not shown here, but some SPIN programs are intended as libraries - not complete programs, but objects to be used within other programs. In such cases, propstacklen can be told to produce a separate report for each PUB method in the top object, giving an indication of the stack impact of using the library.
Propstacklen is a command line program written in C++, so it should run on any platform that has a C++ compiler. It writes its output to the standard output stream. It's developed and has been (minimally) tested under Linux; if it fails to build and run under other operating systems I'll consider that a bug.
Techie note: propstacklen doesn't work on the .spin file. Instead, it uses the .list and .eeprom files as generated by Brad's bstc compiler. That means that it should reflect any compiler optimisations that are applied. It also means that *any* compiler, for any language, that generates SPIN byte code should be covered by it - with the possible need to accommodate that compiler's particular syntax of the list file.
Source code. I don't believe the source code is polished enough for public display, but if I wait until it is you'll never see it :-)
So I've put it on my website here: http://www.jsjf.demon.uk/propstacklen.zip. I would have attached it to this post, but the forum software and Firefox don't seem to play well together in that regard. See the file README.txt for more details of how to use propstacklen.
Update: the latest version is http://www.jsjf.demon.co.uk/propstacklen_0.3.zip.
At the moment, I believe the usual way to check stack size is to fill the stack area with longs of some value, and then run the program and see how many get overwritten. The snag with that technique is that it gives only a lower bound for the size - a program run with different inputs may send the stack deeper.
So I wrote propstacklen to carry out a static analysis of the SPIN program, from which the deepest possible stack can be traced. When run, propstacklen reads the .list and .eeprom files that the compiler generated, and generates a report showing the trace of method calls that will produce the maximum stack. In this way, the figures generated in the report are the upper bound on the stack size.
Here's the output from PlayWav_8bit.spin in the WavPlayers Obex object. This is about a simple as it gets, because that program has only two methods: a main method, and one that's called by main(). The maximum stack depth is 80 bytes
Stack depth report for PlayWav_8bit Generated by propstacklen version 0.1 ======================================================== STACK DEPTH REPORT for Method PlayWav_8bit.Main All reported values are in decimal notation unless prefixed with 0x Stack sizes are given in bytes Main stack starts at 0x7340 and so extends to 0x738f 80 Max stack depth within PlayWav_8bit.Main() occurs in line 12 at statement: Player(@Wav,10,11) 24 is the local stack frame depth before the call to PlayWav_8bit.Player 56 Max stack depth within PlayWav_8bit.Player() occurs in line 24 at statement: CTRA:= 110 << 26 + 0<<9 + PinR ========================================================By way of contrast, here's the much more extensive report for Mike Green's BoeBotBasic:
Stack depth report for BoeBotBasic Generated by propstacklen version 0.1 ======================================================== STACK DEPTH REPORT for Method BoeBotBasic.main All reported values are in decimal notation unless prefixed with 0x Stack sizes are given in bytes RECURSION WARNING: Recursion has been detected and will add to the stack size Main stack starts at 0x4900 and so extends to 0x4b3b 572 Max stack depth within BoeBotBasic.main() occurs in line 220 at statement: err := \doline(s) 20 is the local stack frame depth before the call to BoeBotBasic.doline 552 Max stack depth within BoeBotBasic.doline() occurs in line 1300 at statement: texec 20 is the local stack frame depth before the call to BoeBotBasic.texec 532 Max stack depth within BoeBotBasic.texec() occurs in line 1284 at statement: mass.writeExpander(a,specialExpr) 96 is the local stack frame depth before the call to BoeBotBasic.specialExpr 436 Max stack depth within BoeBotBasic.specialExpr() occurs in line 666 at statement: return expr 12 is the local stack frame depth before the call to BoeBotBasic.expr 424 Max stack depth within BoeBotBasic.expr() occurs in line 653 at statement: t := logicAnd 20 is the local stack frame depth before the call to BoeBotBasic.logicAnd 404 Max stack depth within BoeBotBasic.logicAnd() occurs in line 643 at statement: t := logicNot 20 is the local stack frame depth before the call to BoeBotBasic.logicNot 384 Max stack depth within BoeBotBasic.logicNot() occurs in line 639 at statement: return not compare 12 is the local stack frame depth before the call to BoeBotBasic.compare 372 Max stack depth within BoeBotBasic.compare() occurs in line 612 at statement: a := arithExpr 28 is the local stack frame depth before the call to BoeBotBasic.arithExpr 344 Max stack depth within BoeBotBasic.arithExpr() occurs in line 599 at statement: t := term 20 is the local stack frame depth before the call to BoeBotBasic.term 324 Max stack depth within BoeBotBasic.term() occurs in line 583 at statement: t := bitTerm 20 is the local stack frame depth before the call to BoeBotBasic.bitTerm 304 Max stack depth within BoeBotBasic.bitTerm() occurs in line 570 at statement: t := bitFactor 20 is the local stack frame depth before the call to BoeBotBasic.bitFactor 284 Max stack depth within BoeBotBasic.bitFactor() occurs in line 560 at statement: t := shifts 20 is the local stack frame depth before the call to BoeBotBasic.shifts 264 Max stack depth within BoeBotBasic.shifts() occurs in line 536 at statement: t := factor 20 is the local stack frame depth before the call to BoeBotBasic.factor 244 Max stack depth within BoeBotBasic.factor() occurs in line 465 at statement: return mass.getByte 20 is the local stack frame depth before the call to BB_massStorage.getByte 224 Max stack depth within BB_massStorage.getByte() occurs in line 170 at statement: return pgetc 12 is the local stack frame depth before the call to BB_massStorage.pgetc 212 Max stack depth within BB_massStorage.pgetc() occurs in line 667 at statement: t := pfillbuf 16 is the local stack frame depth before the call to BB_massStorage.pfillbuf 196 Max stack depth within BB_massStorage.pfillbuf() occurs in line 483 at statement: fclust := nextcluster 16 is the local stack frame depth before the call to BB_massStorage.nextcluster 180 Max stack depth within BB_massStorage.nextcluster() occurs in line 378 at statement: clust := followchain 16 is the local stack frame depth before the call to BB_massStorage.followchain 164 Max stack depth within BB_massStorage.followchain() occurs in line 368 at statement: clust := brword(readfat(fclust)) 20 is the local stack frame depth before the call to BB_massStorage.readfat 144 Max stack depth within BB_massStorage.readfat() occurs in line 362 at statement: return readbytec(fatptr) 16 is the local stack frame depth before the call to BB_massStorage.readbytec 128 Max stack depth within BB_massStorage.readbytec() occurs in line 353 at statement: readblockc(byteloc >> SectorShift) 16 is the local stack frame depth before the call to BB_massStorage.readblockc 112 Max stack depth within BB_massStorage.readblockc() occurs in line 268 at statement: flushifdirty 16 is the local stack frame depth before the call to BB_massStorage.flushifdirty 96 Max stack depth within BB_massStorage.flushifdirty() occurs in line 259 at statement: writeblock2(lastread, @buf2) 12 is the local stack frame depth before the call to BB_massStorage.writeblock2 84 Max stack depth within BB_massStorage.writeblock2() occurs in line 250 at statement: ldr.writeSDCard(n, b, SectorSize) 20 is the local stack frame depth before the call to BB_i2cSpiLdr.writeSDCard 64 Max stack depth within BB_i2cSpiLdr.writeSDCard() occurs in line 107 at statement: return doOperation(def#ioSpiWrite,addr,buffer,count) 24 is the local stack frame depth before the call to BB_i2cSpiLdr.doOperation 40 Max stack depth within BB_i2cSpiLdr.doOperation() occurs in line 123 at statement: long[def#ioControl+4] := (count << 16) | (buffer & $FFFF) ======================================================== STACK DEPTH REPORT for Method BoeBotBasic.servoProcess All reported values are in decimal notation unless prefixed with 0x Stack sizes are given in bytes 36 Max stack depth within BoeBotBasic.servoProcess() occurs in line 1463 at statement: uS := clkfreq / 1_000_000 ======================================================== STACK DEPTH REPORT for Method BoeBotBasic.pingProcess All reported values are in decimal notation unless prefixed with 0x Stack sizes are given in bytes 32 Max stack depth within BoeBotBasic.pingProcess() occurs in line 1490 at statement: waitpne(0, |< pingData, 0) ========================================================The first thing to notice is that BoeBotBasic uses recursion. Nothing wrong with that in itself, but it does mean that the stack size is unpredictable as far as a program like propstacklen (or, I believe, any other conceivable program) is concerned. So it reports the stack size for the main program as 572 bytes, but every recursive call will add to that amount. So far, propstacklen merely notes that recursion was detected. It would be possible to improve on that level of reporting, though never to the extent of predicting a maximum stack size when recursion is present.
The other thing to note is that if you scroll to the bottom of the report, you'll find that BoeBotBasic has two methods (servoProcess and pingProcess) that are opened in seperate cogs. Propstacklen detects this, and reports on the stack sizes those cogs will need.
Not shown here, but some SPIN programs are intended as libraries - not complete programs, but objects to be used within other programs. In such cases, propstacklen can be told to produce a separate report for each PUB method in the top object, giving an indication of the stack impact of using the library.
Propstacklen is a command line program written in C++, so it should run on any platform that has a C++ compiler. It writes its output to the standard output stream. It's developed and has been (minimally) tested under Linux; if it fails to build and run under other operating systems I'll consider that a bug.
Techie note: propstacklen doesn't work on the .spin file. Instead, it uses the .list and .eeprom files as generated by Brad's bstc compiler. That means that it should reflect any compiler optimisations that are applied. It also means that *any* compiler, for any language, that generates SPIN byte code should be covered by it - with the possible need to accommodate that compiler's particular syntax of the list file.
Source code. I don't believe the source code is polished enough for public display, but if I wait until it is you'll never see it :-)
So I've put it on my website here: http://www.jsjf.demon.uk/propstacklen.zip. I would have attached it to this post, but the forum software and Firefox don't seem to play well together in that regard. See the file README.txt for more details of how to use propstacklen.
Update: the latest version is http://www.jsjf.demon.co.uk/propstacklen_0.3.zip.
Comments
Any ideas? I should add that the program compiles and runs.
The error message it's referring to was the line:
You've found an error in the program.
Could you either post or send by PM your .list and .eeprom files?
I'll look into it. The message you saw was generated by defensive code and should not have happened :-(
Happy bug hunting!
Well, that was exciting. I'm not done yet, but I can present the report for your program:
You might want to examine the section on cog_Log - if propstacklen is right (big if), you'll be wanting to increase that stack allowance.
I haven't yet published the updated source, because one of the things I had to fix was an error in handling the bytecode generated for the LOOKUPZ spin statement. A similar fix will be needed for LOOKDOWN/LOOKDOWNZ so I'd like to do that before unleashing the next version.
Meanwhile, I hope the report helps.
This is great. I'll be sure to try it out.
Thank you,
Please do - and please be patient if, like JLocke, it doesn't work for you out of the box. I've been testing it on objects pulled more or less at random from the Obex, and clearly I haven't necessarily covered all the possible cases yet.
Suggestions of large and/or complicated Obex programs that might be good exercises are also welcome.
http://www.jsjf.demon.co.uk/propstacklen_0.2.zip
See README.txt for detailed information about the program.
I have (I hope) fixed the problem that DLocke had, and made a few other mainly cosmetic changes. For example, error messages are now clearly marked as such instead of just being buried in the rest of the output.
My test cases still don't include full coverage of the SPIN bytecodes, and I'd be very grateful if someone could suggest an Obex program that makes extensive use of locks in particular.
I'm also contemplating the fact that this tool should work with compilers other than bstc. If anyone's interested in that, I'd need a listing file and eeprom file generated by the compiler. The source language doesn't have to be spin: any compiler that generates spin byte code should be fair game.
Enjoy!
I've made some rather significant changes to my project source, so thought I'd try version 0.2. I built the executable and ran it against my project files, and again came up with an error. Below is the output from the program:
I've attached my .list and .eeprom files for your inspection. Thanks!
The issue is that propstacklen is being confused by a perfectly legitimate trick you're using: breaking a long line of code by terminating it with '{' and starting the next line with '}'. The continuation line then appears in the list file out of the normal sequence.
I need to fix propstacklen, but as a temporary work-round you could try removing those line breaks (there are only four). Propstacklen v0.2 will then process your files.
My problem is that bstc appears to be inconsistent in its own handling of this: sometimes it lists the continuation line, sometimes not. I need to look further into it.
It fixes the problem where using a curly bracketted comment to split long source lines was causing confusion in the parse of the list file. No other changes.
For the second, it's complaining that you ran bstc without specifying the -s flag (which tells bstc to include the source lines in the list file). Since you've been using propstacklen successfully I assume you did use the flag, in which case this is a propstacklen error.
If you'd care to post the list and eeprom files for the failure case, I'll look into it.
And thanks for your patience and all the useful feedback.