We also NEVER did dynamic memory allocation and never used recursive subroutines.

I understand the 8051 has limited RAM, but why can't we use dynamic memory allocation (like malloc/free) ? how does limited RAM specifically cause problems?

 

Understand that AT89S52 is a relatively simple MCU with only 256 bytes of SRAM.
Don't use dynamic memory allocation like malloc. That is simple asking for trouble.

With only 256 bytes of SRAM, you should be doing memory allocation manually, or at least on pen and paper.

 

I understand the 8051 has limited RAM, but why can't we use dynamic memory allocation (like malloc/free) ? how does limited RAM specifically cause problems?

The overhead of managing a heap is just not worth the effort on such a limited processor. If you want to try it, you can KNOCK YOURSELF OUT!

 

I understand the 8051 has limited RAM, but why can't we use dynamic memory allocation (like malloc/free) ? how does limited RAM specifically cause problems?

Heaps have overheads. They have a start header that describes remaining virgin space, free list(s), etc. every address you get back, actually has an unseen header, likely must be aligned on some 2^n boundary, perhaps 16 bytes maybe more. if you make many small allocations (say, 8, 16 or so bytes) then perhaps 50% of used memory is dedicated to all that housekeeping.

See

https://www3.nd.edu/~pbui/teaching/cse.30341.fa18/project04.html

 

But the real reason is: Dynamic memory is useful for programs that have multiple data structures with unknown sizes that come and go during execution. This would be very atypical for an app on an 8-bit microcomputer having 256 bytes of RAM. Typically, these systems would have a small fixed amount of data. There is no need for dynamic memory.

To counter what @Futurist said, I could easily implement a heap using 1-byte headers and no alignment required on a system that has only 128B of heap available. (or 256B with 2 byte alignment.).

 

To counter what @Futurist said, I could easily implement a heap using 1-byte headers and no alignment required on a system that has only 128B of heap available. (or 256B with 2 byte alignment.).

That would certainly be an interesting problem to explore. In most heaps when we free an allocation, the heap logic does this

1. Decrement supplied user ptr to get to block header.
2. Examine header to see if block already free, exit if it is.
3. Using the size in header, get ptr to following block.
4. See if that block is free, if it is
5. ...remove it from free list.
6. ...adjust size of user block by combining the two sizes.
7. Using prev size in user block, get ptr to previous block.
8. See if that block is free, if it is
9. ...remove it from free list.
A. ...adjust size of prev block by combining the two sizes.
B. .../* we now have a (potentially) large single block, coalesced */
C. Examine heap header to see if block can be coalesced with virgin space, if so do it and exit.
E. Tag the current block as "free".
F. insert the block onto free list, exit.

So you need a block header that can represent "free" or "busy", and represent block size and represent preceding block size.

If you can do that with one byte id be fascinated because the max size of a block would be 4 bits, you can't merge many blocks when 4 bits size is all you have (storing prev size is worse, you only have 3 bits left).

 

That would certainly be an interesting problem to explore. In most heaps when we free an allocation, the heap logic does this

I don't give a damn what most memory allocators do. They are generally written for systems with WAY more than 256 bytes.

Here are two ways to do it:

1. With a header and 2-byte alignment:

A one byte header is used. It is the size/2 of the block in upper 7 bits and the low bit indicates it is allocated.

malloc: Scan through the heap looking for a free block large enough. if found, mark it as allocated and set the new length. If there is more than 1 byte left over after the requested amount, make a new free block from the remaining bytes. Return the address of the header + 1. If none found, return NIL.

Free: simply back up one and mark the block as free by setting the high bit. If you want to get fancy, check for next block free and combine them.

2. Bitmap.

Allocate 16 bytes as a bitmap for the heap. 0 indicates a free block 1 an allocated block.

malloc: Look for a string of 1 bits large enough for the request + 1. Set the size in the first byte, mark it allocated, and return the address + 1;
free: back up by one and get the size (0-255). Mark all the corresponding bits in the bitmap as free.

The reason for not using dynamic allocation on small memory systems has nothing to do with difficulty of implementing it.

 

I don't give a damn what most memory allocators do. They are generally written for systems with WAY more than 256 bytes.
...
The reason for not using dynamic allocation on small memory systems has nothing to do with difficulty of implementing it.

Exactamente!
In over half a century of embedded systems development I never encountered the need for dynamic memory utilization. Maybe I just wasn't trying hard enough or maybe I just wasn't creative enough.

 

Agreed.
I have never used malloc in my whole career!

 

I don't give a damn what most memory allocators do. They are generally written for systems with WAY more than 256 bytes.

Here are two ways to do it:

1. With a header and 2-byte alignment:

A one byte header is used. It is the size/2 of the block in upper 7 bits and the low bit indicates it is allocated.

malloc: Scan through the heap looking for a free block large enough. if found, mark it as allocated and set the new length. If there is more than 1 byte left over after the requested amount, make a new free block from the remaining bytes. Return the address of the header + 1. If none found, return NIL.

Free: simply back up one and mark the block as free by setting the high bit. If you want to get fancy, check for next block free and combine them.

2. Bitmap.

Allocate 16 bytes as a bitmap for the heap. 0 indicates a free block 1 an allocated block.

malloc: Look for a string of 1 bits large enough for the request + 1. Set the size in the first byte, mark it allocated, and return the address + 1;
free: back up by one and get the size (0-255). Mark all the corresponding bits in the bitmap as free.

The reason for not using dynamic allocation on small memory systems has nothing to do with difficulty of implementing it.

That could work, but freeing necessitates examining the preceding block too, in this design you'd need to scan all blocks from the start (since you don't record prev_block_size in your block header) in order to identify the preceding block.

The bitmap idea is good, (malloc would scan for contiguous 0 bits though, not 1) I like that, I said it would be interesting!

Searching the 16 byte block for the position of the first 'n' zero bits would be interesting...