@JRoark: it does look like there are two bugs, one in fastspin and one in your code. The easy one is a cut and paste error in your code: note that in your second print loop you're resetting all of the data values back to 255:
print "MAIN: byte array data values AFTER call to SUB)"
for n = 0 to 15
main_buffer(n) = 255
print "["; main_buffer(n); "] ";
next n
The harder bug is in fastspin: if you give an explicit BYREF on an array parameter the final type of the parameter is coming out wrong. I'm looking into that, but for now you can work around it by leaving off the "BYREF" on the array parameter: arrays default to being BYREF, and that default seems to work OK.
@ersmith,
Can I add a c file to my main spin code in order to get access to malloc?
AFAIK, there is no dynamic memory mechanism in Spin. But, would be nice to have...
I'm going to assume the answer to that is yes.
But then... Does it know the size of available memory? Or, does it always return true?
Also, is there any garbage collection mechanism? Probably not, right?
Or, is there a way to free all and start over with the heap? Might be nice for opening a new file, for example...
@ersmith,
Can I add a c file to my main spin code in order to get access to malloc?
AFAIK, there is no dynamic memory mechanism in Spin. But, would be nice to have...
I'm going to assume the answer to that is yes.
But then... Does it know the size of available memory? Or, does it always return true?
Also, is there any garbage collection mechanism? Probably not, right?
Or, is there a way to free all and start over with the heap? Might be nice for opening a new file, for example...
You can add a .c file, but there's no need. Spin code can directly call the low level functions used by BASIC and C for memory allocation. There is a garbage collector. It's only added to your code if you ask for it by using one of its functions.
The low level memory functions are documented in the BASIC manual under the "language features / memory allocation" section. The main function is _gc_alloc_managed(siz), which allocates "siz" bytes of memory managed by the garbage collector. It returns NULL if not enough memory is avilable, otherwise returns a pointer to the start of the memory (like malloc). As long as there is some reference in COG or HUB memory to the pointer which got returned, the memory will be considered "in use". If there is no more such reference then the garbage collector will feel free to reclaim it. There's also "_gc_alloc(siz)" which is similar but marks the memory so it will never be reclaimed, and "_gc_free(ptr)" which explicitly frees a pointer previously allocated by "_gc_alloc" or "_gc_alloc_managed".
The size of the heap is determined by a constant HEAPSIZE declared in the top level object. If none is given a (small) default value is used.
Example Spin code:
' put this CON in the top level object to specify how much memory should be provided for
' memory allocation (the "heap"). The default is 4K on P2, 256 bytes on P1
CON
HEAPSIZE = 32768 ' or however much memory you want to provide for the allocator
' here's a function to allocate memory
' "siz" is the size in bytes
PUB allocmem(size) : ptr
ptr := _gc_alloc_managed(size)
@ersmith,
Can I add a c file to my main spin code in order to get access to malloc?
AFAIK, there is no dynamic memory mechanism in Spin. But, would be nice to have...
I'm going to assume the answer to that is yes.
But then... Does it know the size of available memory? Or, does it always return true?
Also, is there any garbage collection mechanism? Probably not, right?
Or, is there a way to free all and start over with the heap? Might be nice for opening a new file, for example...
You can add a .c file, but there's no need. Spin code can directly call the low level functions used by BASIC and C for memory allocation. There is a garbage collector. It's only added to your code if you ask for it by using one of its functions.
The low level memory functions are documented in the BASIC manual under the "language features / memory allocation" section. The main function is _gc_alloc_managed(siz), which allocates "siz" bytes of memory managed by the garbage collector. It returns NULL if not enough memory is avilable, otherwise returns a pointer to the start of the memory (like malloc). As long as there is some reference in COG or HUB memory to the pointer which got returned, the memory will be considered "in use". If there is no more such reference then the garbage collector will feel free to reclaim it. There's also "_gc_alloc(siz)" which is similar but marks the memory so it will never be reclaimed, and "_gc_free(ptr)" which explicitly frees a pointer previously allocated by "_gc_alloc" or "_gc_alloc_managed".
The size of the heap is determined by a constant HEAPSIZE declared in the top level object. If none is given a (small) default value is used.
Example Spin code:
' put this CON in the top level object to specify how much memory should be provided for
' memory allocation (the "heap"). The default is 4K on P2, 256 bytes on P1
CON
HEAPSIZE = 32768 ' or however much memory you want to provide for the allocator
' here's a function to allocate memory
' "siz" is the size in bytes
PUB allocmem(size) : ptr
ptr := _gc_alloc_managed(size)
That's a very nice feature. I have to work on getting more comfortable with conservative garbage collectors.
@JRoark: it does look like there are two bugs, one in fastspin and one in your code. The easy one is a cut and paste error in your code: note that in your second print loop you're resetting all of the data values back to 255:
print "MAIN: byte array data values AFTER call to SUB)"
for n = 0 to 15
main_buffer(n) = 255
print "["; main_buffer(n); "] ";
next n
Oh for Pete's sake. (Hangs head). There are days I look in the mirror and go "Dang, Roark! You make obtuse look acute!". In my defense, I was 16 hours into Prop'ing and not feeling well.
The harder bug is in fastspin: if you give an explicit BYREF on an array parameter the final type of the parameter is coming out wrong. I'm looking into that, but for now you can work around it by leaving off the "BYREF" on the array parameter: arrays default to being BYREF, and that default seems to work OK.
Good to know! Thank you.
EDIT: After correcting the error you pointed-out (ahem), I tried the corrected code with BYVAL just to see what happened. It looks like BYVAL is behaving like BYREF properly should, ie, any changes to the array data inside the sub propagate back to the main loop when the array is declared as BYVAL.
I just tried converting my fixed static VGA image buffer to one on the heap and it doesn't seem to work...
Goes off the rails if I try use the managed version and returns null pointer with regular one....
Also, my main motivation in this case was to reduce the download size. But, it doesn't seem to do that.
Does the heap need to be part of the download?
@Rayman: Sorry, but if your main motivation is reducing the download size then the heap allocation won't help; it's implemented as an object and so the memory for the heap gets put into the image, at least for now.
The best way to reduce the download size is to use the highest optimization setting (-O2), which eliminates a lot of variable space.
If your actual goal is to reduce download *time* rather than size, then what baud rate are you using for loadp2's downloads? I've found 2000000 baud to be very stable and also very fast.
@Rayman: Sorry, but if your main motivation is reducing the download size then the heap allocation won't help; it's implemented as an object and so the memory for the heap gets put into the image, at least for now.
The best way to reduce the download size is to use the highest optimization setting (-O2), which eliminates a lot of variable space.
If your actual goal is to reduce download *time* rather than size, then what baud rate are you using for loadp2's downloads? I've found 2000000 baud to be very stable and also very fast.
Is sbrk() in your future? Would it be easy to implement given your current memory layout?
sbrk() isn't on the roadmap and isn't needed (malloc uses the garbage collected heap). The memory layout would make it hard anyway.
I mentioned it because you could have the garbage collector allocate its heap at startup using sbrk() and hence not have the heap baked into the executable. I didn't mean it as a replacement for your current allocator.
@Rayman: no, there's no size limit, but there is a bad typo that's causing the actual usable heap size to be only 1/4 the reserved size . So until the next release the GC is not usable for large allocations. I'm working on a fix now and hope to make a new binary in a day or two.
I'm curious now as to how garbage collection works... Must be some real magic in there.
But, am I right that it only goes to work when called via this function: _gc_collect()
Does it move pointed to data around and update pointers, or just combine free areas?
The garbage collection never moves anything. It just frees blocks of memory that are no longer in use. It detects "no longer in use" automatically by scanning HUB and COG memory for pointers into the heap (which are also tagged with a special value in the upper 12 bits).
_gc_collect() is called automatically by _gc_alloc*() if there isn't enough space. If there's still not enough space after _gc_collect(), then the _gc_alloc* fails (returns 0).
(which are also tagged with a special value in the upper 12 bits).
I was wondering what magic could make that work! I can see how it can work now...
Is there no chance that some data just happens to have the magic 12 bits plus pointer address? Does it actually look at the context in which values are being used? I think it must...
Is there no chance that some data just happens to have the magic 12 bits plus pointer address? Does it actually look at the context in which values are being used? I think it must...
Yes, there's a chance that some data might happen to have the magic 12 bits, and the remaining 20 bits points into the heap, and that part of the heap is the start of a heap block, and it's a heap block that is marked as in use but really it doesn't have to be. It's an extremely small chance. In that case some memory doesn't get freed that could have been.
The collector can't look at how the values are used because it doesn't know that (the values are just pointers in memory, it doesn't know anything about how the program may end up using some arbitrary 32 bit value in HUB memory).
Eric, is the garbage collection just a Spin thing?
No, it's available in any language. It's used most heavily in BASIC, for the string functions.
Your description of garbage collection just sounds like what happens when free() is called in C.
Perhaps I didn't explain it well, but it's very different. free(x) frees one specific pointer ("x") and doesn't necessarily check whether it is in use or not. The garbage collector scans all of HUB & COG memory and marks what allocated blocks are in use, then frees the ones that aren't used.
What is the memory map used by fastspin? Where is code loaded? Where is the stack placed? How can I know what memory is still available after loading a program?
I'm using FastGUI 4.1.6 beta running on my MacBook and it can't find my P2 Eval Board:
loadp2 FemtoBasic.binary -t
Could not find a P2
I tried plugging into different USB ports and restarting the MacBook. Not helpful.
Here's an example running FlexGUI from a one line AppleScript app:
/Users/mgreen/Applications/flexgui/bin/loadp2.mac -b230400 /Users/mgreen/Desktop/FemtoBasic/FemtoBasic.binary -9/Users/mgreen/Desktop/FemtoBasic -k; osascript -e 'tell application "Wish" to activate'; exit 0
Could not find a P2
Press enter to continue...
What is the memory map used by fastspin? Where is code loaded? Where is the stack placed? How can I know what memory is still available after loading a program?
There is a command line switch (-H) to specify the starting address, but the default is 0. First comes whatever COG code is needed (very little for the P2, just enough to bootstrap). Then comes the hubexec code. Then comes the data (including all variables). The heap (the size of which is given by HEAPSIZE) is part of that data. After that comes the stack, which grows upwards towards the end of memory. You can access the stack pointer by the variable "sp" in inline assembly, or by calling __getsp() in a high level language. The stuff above that is "free" (as long as you don't need a deeper stack, of course).
I'm using FastGUI 4.1.6 beta running on my MacBook and it can't find my P2 Eval Board:
loadp2 FemtoBasic.binary -t
Could not find a P2
If you know which port the P2 is plugged in to you can skip the search for the P2 Eval board and specify it directly on the command line with the -p option, e.g.
loadp2.mac -p/dev/cu.usbserial-P2EEI93 ...
You can also give a "-v" option to loadp2 to see what it's doing and perhaps debug what's going wrong.
Have you flashed a boot program or inserted an SD card? If the P2 is booting from another source it may not pay attention to the serial. The P2 Eval Board docs has a description of switch settings and how they control the boot process; the safest setting for development seems to be all switches in the "off" position.
Your description of garbage collection just sounds like what happens when free() is called in C.
Perhaps I didn't explain it well, but it's very different. free(x) frees one specific pointer ("x") and doesn't necessarily check whether it is in use or not. The garbage collector scans all of HUB & COG memory and marks what allocated blocks are in use, then frees the ones that aren't used.
The way I understand it for C, is that the heap starts just after the end of program space, and goes to the end of memory, or to some other ending that could be specified. The way I've implemented malloc and free is to use a linked list to keep track of what has been allocated and freed. When free is called, it releases the memory that was being used, and the user program can no longer use it. So free doesn't need to check whether it is in use or not because it is always not in use after that. Any memory that is freed using free can then be allocated again using malloc.
I apologize for my ignorance, but it seems that your memory management scheme is different than that used by C.
I'm using FastGUI 4.1.6 beta running on my MacBook and it can't find my P2 Eval Board:
loadp2 FemtoBasic.binary -t
Could not find a P2
I tried plugging into different USB ports and restarting the MacBook. Not helpful.
Here's an example running FlexGUI from a one line AppleScript app:
/Users/mgreen/Applications/flexgui/bin/loadp2.mac -b230400 /Users/mgreen/Desktop/FemtoBasic/FemtoBasic.binary -9/Users/mgreen/Desktop/FemtoBasic -k; osascript -e 'tell application "Wish" to activate'; exit 0
Could not find a P2
Press enter to continue...
Is your P2 board showing up in /dev???
ls /dev | grep cu.
I created an alias that resides in ~/.profile that lets me just type 'lsdev' in Terminal app to display any USB serial devices that I may have plugged into my Mac. Somewhere inside ./profile, I added:
# list USB serial devices
alias lsdev='ls /dev | grep cu.'
Also, I use the CoolTerm app to talk to my USB serial devices (P1, P2, Arduino's, etc...). It's a good option to just check out your P2... You can exec into the Cluso99's ROM monitor or Peter's TAKOZ. When loadp2 can't find the P2, it's good to know if other code can see and communicate with the P2!
I switched to Parallels on my Mac mini after a bunch of other stuff didn't work...
I imagine you might want to use that when the new Prop Tool comes out...
Everything seems to work that way...
I haven't tried Fastspin or SpinEdit that way yet, but need to soon...
The way I understand it for C, is that the heap starts just after the end of program space, and goes to the end of memory, or to some other ending that could be specified.
That's a common way it's implemented, but the C standard doesn't specify where the heap is, or anything about its size.
The way I've implemented malloc and free is to use a linked list to keep track of what has been allocated and freed. When free is called, it releases the memory that was being used, and the user program can no longer use it. So free doesn't need to check whether it is in use or not because it is always not in use after that. Any memory that is freed using free can then be allocated again using malloc.
The fastspin memory allocator is implemented similarly, but there are some additions:
(1) Each block of memory, besides having an "allocated/free" flag, also has two additional flags: one that indicates whether the block is "managed" (eligible to be garbage collected), and one that indicates whether the block is "in use". For blocks allocated by the C malloc function, "managed" is false and "in use" is always true until the block is freed. For blocks allocated by _gc_alloc_managed() the "manged" bit is true, and "in use" is initially true but may be changed (see below).
(2) The user can always explicitly free blocks and return them to the pool of available memory; this clears all of the flags.
(3) If we never run out of memory, things act just like your allocator.
(4) If we do run out of memory then the garbage collector is invoked. This walks through the list of allocated blocks and updates their "in use" flags, as follows:
(a) if the block is unmanaged (allocated by the C malloc() call or the like) then "in use" remains set
(b) if the block is managed (e.g. allocated by BASIC string routines) then "in use" is tentatively cleared
(c) once all allocated blocks have been updated, the collector then goes through HUB and COG memory looking for 32 bit values which point into the heap to the start of an allocated block. Whenever one of these is found, that block's corresponding "in use" flag is set. To assist in avoiding false positives, the upper 12 bits of pointers have a special tag
(d) at the end of this, we make a final pass through the allocated blocks. Any managed block with a clear "in use" flag is then freed, just as though the user had explicitly called free() on it. The reasoning here is that if there are no pointers to a block, the user is no longer using it and it is safe to free it.
(5) Now we can retry the failed allocation, since presumably some memory was freed up by the garbage collector. If the allocation still fails, we have to give up and return a NULL pointer
There are some subtleties, e.g. the pointers in the internal linked list point to block headers (and are not tagged!) and so can be distinguished from user pointers which point beyond the block headers. Also, it is important to always keep a copy of the original pointer returned by _gc_alloc_managed() somewhere for as long as that memory is in use; if you modify that original pointer in some way (e.g. by rounding it to force alignment) then the garbage collector won't know it's still in use. Again, that's only an issue for managed memory; C's malloc() returns unmanaged memory and so must be explicitly freed by the user.
Comments
The harder bug is in fastspin: if you give an explicit BYREF on an array parameter the final type of the parameter is coming out wrong. I'm looking into that, but for now you can work around it by leaving off the "BYREF" on the array parameter: arrays default to being BYREF, and that default seems to work OK.
Can I add a c file to my main spin code in order to get access to malloc?
AFAIK, there is no dynamic memory mechanism in Spin. But, would be nice to have...
I'm going to assume the answer to that is yes.
But then... Does it know the size of available memory? Or, does it always return true?
Also, is there any garbage collection mechanism? Probably not, right?
Or, is there a way to free all and start over with the heap? Might be nice for opening a new file, for example...
BTW: If anybody doesn't know what I'm talking about, there's a nice summary here:
https://www.design-reuse.com/articles/25090/dynamic-memory-allocation-fragmentation-c.html
You can add a .c file, but there's no need. Spin code can directly call the low level functions used by BASIC and C for memory allocation. There is a garbage collector. It's only added to your code if you ask for it by using one of its functions.
The low level memory functions are documented in the BASIC manual under the "language features / memory allocation" section. The main function is _gc_alloc_managed(siz), which allocates "siz" bytes of memory managed by the garbage collector. It returns NULL if not enough memory is avilable, otherwise returns a pointer to the start of the memory (like malloc). As long as there is some reference in COG or HUB memory to the pointer which got returned, the memory will be considered "in use". If there is no more such reference then the garbage collector will feel free to reclaim it. There's also "_gc_alloc(siz)" which is similar but marks the memory so it will never be reclaimed, and "_gc_free(ptr)" which explicitly frees a pointer previously allocated by "_gc_alloc" or "_gc_alloc_managed".
The size of the heap is determined by a constant HEAPSIZE declared in the top level object. If none is given a (small) default value is used.
Example Spin code:
Good to know! Thank you.
EDIT: After correcting the error you pointed-out (ahem), I tried the corrected code with BYVAL just to see what happened. It looks like BYVAL is behaving like BYREF properly should, ie, any changes to the array data inside the sub propagate back to the main loop when the array is declared as BYVAL.
Goes off the rails if I try use the managed version and returns null pointer with regular one....
Also, my main motivation in this case was to reduce the download size. But, it doesn't seem to do that.
Does the heap need to be part of the download?
The best way to reduce the download size is to use the highest optimization setting (-O2), which eliminates a lot of variable space.
If your actual goal is to reduce download *time* rather than size, then what baud rate are you using for loadp2's downloads? I've found 2000000 baud to be very stable and also very fast.
Is there some size limit?
Thanks for the bug report!
I'm curious now as to how garbage collection works... Must be some real magic in there.
But, am I right that it only goes to work when called via this function: _gc_collect()
Does it move pointed to data around and update pointers, or just combine free areas?
_gc_collect() is called automatically by _gc_alloc*() if there isn't enough space. If there's still not enough space after _gc_collect(), then the _gc_alloc* fails (returns 0).
I was wondering what magic could make that work! I can see how it can work now...
Is there no chance that some data just happens to have the magic 12 bits plus pointer address? Does it actually look at the context in which values are being used? I think it must...
Yes, there's a chance that some data might happen to have the magic 12 bits, and the remaining 20 bits points into the heap, and that part of the heap is the start of a heap block, and it's a heap block that is marked as in use but really it doesn't have to be. It's an extremely small chance. In that case some memory doesn't get freed that could have been.
The collector can't look at how the values are used because it doesn't know that (the values are just pointers in memory, it doesn't know anything about how the program may end up using some arbitrary 32 bit value in HUB memory).
Thanks,
Ok, thanks. I see now that the rare case of data having same value as magic 12 bits plus pointer isn't such a big deal...
Perhaps I didn't explain it well, but it's very different. free(x) frees one specific pointer ("x") and doesn't necessarily check whether it is in use or not. The garbage collector scans all of HUB & COG memory and marks what allocated blocks are in use, then frees the ones that aren't used.
I'm using FastGUI 4.1.6 beta running on my MacBook and it can't find my P2 Eval Board:
loadp2 FemtoBasic.binary -t
Could not find a P2
I tried plugging into different USB ports and restarting the MacBook. Not helpful.
Here's an example running FlexGUI from a one line AppleScript app:
/Users/mgreen/Applications/flexgui/bin/loadp2.mac -b230400 /Users/mgreen/Desktop/FemtoBasic/FemtoBasic.binary -9/Users/mgreen/Desktop/FemtoBasic -k; osascript -e 'tell application "Wish" to activate'; exit 0
Could not find a P2
Press enter to continue...
There is a command line switch (-H) to specify the starting address, but the default is 0. First comes whatever COG code is needed (very little for the P2, just enough to bootstrap). Then comes the hubexec code. Then comes the data (including all variables). The heap (the size of which is given by HEAPSIZE) is part of that data. After that comes the stack, which grows upwards towards the end of memory. You can access the stack pointer by the variable "sp" in inline assembly, or by calling __getsp() in a high level language. The stuff above that is "free" (as long as you don't need a deeper stack, of course).
If you know which port the P2 is plugged in to you can skip the search for the P2 Eval board and specify it directly on the command line with the -p option, e.g.
You can also give a "-v" option to loadp2 to see what it's doing and perhaps debug what's going wrong.
Have you flashed a boot program or inserted an SD card? If the P2 is booting from another source it may not pay attention to the serial. The P2 Eval Board docs has a description of switch settings and how they control the boot process; the safest setting for development seems to be all switches in the "off" position.
I apologize for my ignorance, but it seems that your memory management scheme is different than that used by C.
Also, I use the CoolTerm app to talk to my USB serial devices (P1, P2, Arduino's, etc...). It's a good option to just check out your P2... You can exec into the Cluso99's ROM monitor or Peter's TAKOZ. When loadp2 can't find the P2, it's good to know if other code can see and communicate with the P2!
dgately
I imagine you might want to use that when the new Prop Tool comes out...
Everything seems to work that way...
I haven't tried Fastspin or SpinEdit that way yet, but need to soon...
The fastspin memory allocator is implemented similarly, but there are some additions:
(1) Each block of memory, besides having an "allocated/free" flag, also has two additional flags: one that indicates whether the block is "managed" (eligible to be garbage collected), and one that indicates whether the block is "in use". For blocks allocated by the C malloc function, "managed" is false and "in use" is always true until the block is freed. For blocks allocated by _gc_alloc_managed() the "manged" bit is true, and "in use" is initially true but may be changed (see below).
(2) The user can always explicitly free blocks and return them to the pool of available memory; this clears all of the flags.
(3) If we never run out of memory, things act just like your allocator.
(4) If we do run out of memory then the garbage collector is invoked. This walks through the list of allocated blocks and updates their "in use" flags, as follows:
(a) if the block is unmanaged (allocated by the C malloc() call or the like) then "in use" remains set
(b) if the block is managed (e.g. allocated by BASIC string routines) then "in use" is tentatively cleared
(c) once all allocated blocks have been updated, the collector then goes through HUB and COG memory looking for 32 bit values which point into the heap to the start of an allocated block. Whenever one of these is found, that block's corresponding "in use" flag is set. To assist in avoiding false positives, the upper 12 bits of pointers have a special tag
(d) at the end of this, we make a final pass through the allocated blocks. Any managed block with a clear "in use" flag is then freed, just as though the user had explicitly called free() on it. The reasoning here is that if there are no pointers to a block, the user is no longer using it and it is safe to free it.
(5) Now we can retry the failed allocation, since presumably some memory was freed up by the garbage collector. If the allocation still fails, we have to give up and return a NULL pointer
There are some subtleties, e.g. the pointers in the internal linked list point to block headers (and are not tagged!) and so can be distinguished from user pointers which point beyond the block headers. Also, it is important to always keep a copy of the original pointer returned by _gc_alloc_managed() somewhere for as long as that memory is in use; if you modify that original pointer in some way (e.g. by rounding it to force alignment) then the garbage collector won't know it's still in use. Again, that's only an issue for managed memory; C's malloc() returns unmanaged memory and so must be explicitly freed by the user.