Your methodology for the input buffer does make sense - I know that the Apple ][ allocates a 256 byte input buffer which the system parses after Return is pressed. And since only one program is going to be using the input buffer at a time, there really is no point of dynamically allocating it if you don't want to.
Also, I have read some of those readings that Ashbad posted, and I agree that they will be helpful to you. I'll try to explain dynamic memory allocation concisely so that you'll understand what you'd have to do.
1. At the beginning, you know that you have access to some large chunk of memory. You know its position and size, and you want to be able to dynamically allocate that block of memory to any program that requires it. So, you start by setting aside some data to tell you where that is.
2. Sooner or later, someone will ask for some memory. You go into your data that tells you about your memory and see if you have enough space to give them. If you do, you subtract that off the end of your block and hand the pointer to the requested memory back to them. If you don't, return NULL to indicate that there is no memory for them to use.
3. The hard part of this is when someone says that they're done with the memory you gave them. This immediately raises two problems:
- First, there is the problem of how large that memory was in the first place. One option would be to force the system to remember how big its allocations were. While that is workable in some situations, it would be much more convenient to just free the pointer in question. Thus, when handing memory back to the user, you not only need to subtract off the memory they're taking, but also two extra bytes before the pointer to store the size of the allocation (which you write in at the time). Then, when they're done with the memory, you simply go back a little, read those two bytes, and give yourself all that memory back.
- Then comes the much more obvious problem of fragmentation. The allocation they gave back may well be in between two other outstanding allocations, so we need to resolve that problem. The way we do this is add a field to our block data (the one that told us the position and size of our original block) that can point to another piece of data indicating where a viable block is. This modification involves several modifications (and opportunities) in both getting and giving memory:
- When freeing some memory, you need to check if that memory is adjacent to some other free memory (one or two blocks).
- If it's adjacent to just the end of one, you just add the size back.
- If it's adjacent to just the beginning of one, you add the size back and subtract the position back.
- If it's adjacent to neither, you allocate a new block (using your dynamic allocation call you already have), and attach it to one of the blocks you already have.
- If it's adjacent to both, you delete the later block (using the deallocation call you're in the middle of writing) and add its size plus the size of the allocation you just got back to the size of the earlier block. (NOTE that this is not implemented in my code piece above).
- When searching for a desired block (either for one that's big enough or one that's adjacent), you do the following:
- Keep track of where you currently are (this tracking will be persistent over multiple searches)
- Look at each block, one by one. If it fits your conditions, follow through with them. If it doesn't, go on by setting the current pointer to the "next" pointer on the node you're currently looking at.
- If you got back to where you started, abort your search.
- When inserting a new node into the list, you decide which node you want to put it after (any node will do, let's call it the current node). Set your new node's next pointer to the current node's next node, and then set your current node's next pointer to the new node.
- When creating your initial node, set it's "next" to itself. That way the list will always go in a loop, even when inserting new nodes. (NOTE that my memory allocator does NOT do this, but works the same nonetheless)
- And you will note that the only list node you have stored statically is the one at the very beginning, which tells you where your master block is. All of the other nodes are stored happily in your dynamic memory, allowing you to have as many nodes as you want.
- (For more on these semantics, see http://en.wikipedia.org/wiki/Linked_list, since this data structure follows that pattern)
- And now that you're using this linked list structure, you can go ahead and take advantage of that by starting your system with as many blocks of memory as you want, which may or may not be contiguous. For instance, you can make one for each and every page of RAM.
Essentially, when the system is used properly, it keeps careful track of what memory is free for you to use, and programs can go on allocating and deallocating new pieces of memory freely.
In your case, you would want to extend this by having two separate lists - one for RAM for general purpose allocations, and one for Archive memory for saving files. Since you can't easily write to Flash, you should store enough data with your files (at least being able to mark them dirty) to reconstruct your Archive nodes by parsing it, so you don't lose your filesystem to a RAM clear.
Also, I have read some of those readings that Ashbad posted, and I agree that they will be helpful to you. I'll try to explain dynamic memory allocation concisely so that you'll understand what you'd have to do.
1. At the beginning, you know that you have access to some large chunk of memory. You know its position and size, and you want to be able to dynamically allocate that block of memory to any program that requires it. So, you start by setting aside some data to tell you where that is.
2. Sooner or later, someone will ask for some memory. You go into your data that tells you about your memory and see if you have enough space to give them. If you do, you subtract that off the end of your block and hand the pointer to the requested memory back to them. If you don't, return NULL to indicate that there is no memory for them to use.
3. The hard part of this is when someone says that they're done with the memory you gave them. This immediately raises two problems:
- First, there is the problem of how large that memory was in the first place. One option would be to force the system to remember how big its allocations were. While that is workable in some situations, it would be much more convenient to just free the pointer in question. Thus, when handing memory back to the user, you not only need to subtract off the memory they're taking, but also two extra bytes before the pointer to store the size of the allocation (which you write in at the time). Then, when they're done with the memory, you simply go back a little, read those two bytes, and give yourself all that memory back.
- Then comes the much more obvious problem of fragmentation. The allocation they gave back may well be in between two other outstanding allocations, so we need to resolve that problem. The way we do this is add a field to our block data (the one that told us the position and size of our original block) that can point to another piece of data indicating where a viable block is. This modification involves several modifications (and opportunities) in both getting and giving memory:
- When freeing some memory, you need to check if that memory is adjacent to some other free memory (one or two blocks).
- If it's adjacent to just the end of one, you just add the size back.
- If it's adjacent to just the beginning of one, you add the size back and subtract the position back.
- If it's adjacent to neither, you allocate a new block (using your dynamic allocation call you already have), and attach it to one of the blocks you already have.
- If it's adjacent to both, you delete the later block (using the deallocation call you're in the middle of writing) and add its size plus the size of the allocation you just got back to the size of the earlier block. (NOTE that this is not implemented in my code piece above).
- When searching for a desired block (either for one that's big enough or one that's adjacent), you do the following:
- Keep track of where you currently are (this tracking will be persistent over multiple searches)
- Look at each block, one by one. If it fits your conditions, follow through with them. If it doesn't, go on by setting the current pointer to the "next" pointer on the node you're currently looking at.
- If you got back to where you started, abort your search.
- When inserting a new node into the list, you decide which node you want to put it after (any node will do, let's call it the current node). Set your new node's next pointer to the current node's next node, and then set your current node's next pointer to the new node.
- When creating your initial node, set it's "next" to itself. That way the list will always go in a loop, even when inserting new nodes. (NOTE that my memory allocator does NOT do this, but works the same nonetheless)
- And you will note that the only list node you have stored statically is the one at the very beginning, which tells you where your master block is. All of the other nodes are stored happily in your dynamic memory, allowing you to have as many nodes as you want.
- (For more on these semantics, see http://en.wikipedia.org/wiki/Linked_list, since this data structure follows that pattern)
- And now that you're using this linked list structure, you can go ahead and take advantage of that by starting your system with as many blocks of memory as you want, which may or may not be contiguous. For instance, you can make one for each and every page of RAM.
Essentially, when the system is used properly, it keeps careful track of what memory is free for you to use, and programs can go on allocating and deallocating new pieces of memory freely.
In your case, you would want to extend this by having two separate lists - one for RAM for general purpose allocations, and one for Archive memory for saving files. Since you can't easily write to Flash, you should store enough data with your files (at least being able to mark them dirty) to reconstruct your Archive nodes by parsing it, so you don't lose your filesystem to a RAM clear.
