need help answering an assembly question

[nameless_centurian]

so i was digging through some books at home trying to answer some questions. i even found some books that belong to my dad.

i was curious how dynamic memory allocation worked.

well, as it turns out, allocation is fairly easy. you just do something like

         jump next immediate mode
heaptr: .block of memory the size of a word that keeps track of first available memory spot
somptr: a block the size of a word, used as a pointer to dynamic memory

next: lda with initheap in immediate mode
        sta to heaptr in direct mode

main: call new
         sta somptr in direct mode


         STOP

new:   lda heaptr in direct mode
          adda with wordsize in immediate mode
          sta heaptr

          suba wordsize in immediate mode

       return from new

initheap: .block the size of a  word

now, this is all from memory, and you'll have to forgive my pseudo-assembly... so feel free to correct any errors.


...now i have 2 questions

1) it appears as though the program is treating the memory at the end of the program as kind of a reverse stack.... yet the book called it a heap. what gives?

2) none of the books demonstrated a deletion of dynamic memory and a return to the heap of the allocated memory. how is this accompished?

edit: made some changes in errors that i caught

 

[mikeblas]

Your post is quite hard to respond to, since the code you've provided is without context and completely broken anyway. I can try to guess what I think the author meant to show, but then my response won't have anything to do with the book unless I'm really lucky. We don't even know what the operating environemnt is for this program; a PC running an OS? A processor on a board with some memory and no OS?

If you're curious about how dynamic memory works, I'd get an operating systems book and read-up on it. Or try to correct the code you're showing us, provide some context, and ask a specific question.

Just to prove I'm not trying to arbitrarily harsh your deal, I'll try to answer what I think is going on in the code you've provided. It looks to me like it's meant to run on a computer with no operating system. If there was an OS, the "memory after the program" wouldn't belong to the program, and would cause a fault if you touched it.

So say you have this computer with 64K of memory. Your little program takes up 4K. That leaves 60K of memory "after the program". If you get your program to be placed starting at address 0, you have unused memory from addres 4096 to address 65535. 65535-4096+1 = 61440, which is 60k.

You could use a word of memory (in your code, I guess it's "init heap") to indicate how much memory is in use. If you need more memory, you can increment initheap, do some math, and end up with a pointer into that 60k memory block.

This works okay, until it's time to free memory. Say you allocate memory twice. At the beginin, initheap points at addres 4096. so you call

Block1 = GetMemory(100);

and now Block1 points at 100 bytes starting at 4096. initheap gets bumped to 4196, so that when you call

Block2 = GetMemory(250);

you find that block2 points at 4196, and now initheap points at 4446.

Suppose further that you're done using Block1 and wish to get rid of it. But you're still using Block2. You call

ReleaseMemory(Block2);

and you're done.

What can happen? Nothing! InitHeap can't point at 4096 again, because the memory from 4196 to 4446 is still in use, so InitHeap has to sit where it's at. What if you later call ReleaseMemory(Block1)? ReleaseMemory() still can't do anything interesting, because it hasn't made any note of the memory before InitHeap=4446 being free, all the way back to 4196.

You need a little more than what you've shown here to make even a simple dynamic allocation scheme work, though you could use it as a stack. You need a lot more here if you want a good, robust scheme -- or have other requirements like overrun protection and detection, multithread access, and so on.

If you can show some real code and ask some specific questions, I'll be happy to help out; but what you've provided gives nothing concrete to go on.

 

[nameless_centurian]

actually, you've answered all my questions, and you were correct about all of the things you had to assume because of my "broken" post.

the book i drew from was a book teaching basic assembly on a machine that doesn't actually exist, without an OS. because i don't know the assembly for it, i had to do the crap that i did above.

i was curious how in the world you could free the memory because of the precise reason you stated.

so i guess i DO need to pick up an OS book to learn.

if you could list any cheap resources for the EXTREME beginner to OS programming, i'd appreciate it.

 

[mikeblas]

actually, you've answered all my questions, and you were correct about all of the things you had to assume because of my "broken" post.

Awesome. I'm going to add "I'm psychic" to my resume.

if you could list any cheap resources for the EXTREME beginner to OS programming, i'd appreciate it.

The two OS books I have are Operating System Concepts (Sixth Edition), Silberschatz, Galvin, Gagne; and Operating Systems (Fourth Edition), Stallings.

There's also MicroC OS II: The Real Time Kernel (With CD-ROM) (Hardcover) by Jean Labrosse. If you've read my other posts about small computers being the best way to learn the hard stuff, then you'll understand why I recommend a book like this. Labrosse is one of the few good speakers I saw at the Embedded Systems Conference a couple years ago, too; he is good at answering questions and knows his stuff. Embedded guys eschew dynamic memory management, but his OS does implement a heap.

I'm feeling pretty snide today. So: if open source is so fucking great, why don't you just download the sources for Linux and read them? Heh, man, I feel better already.

Or, just approach it as a data structures problem. Say you have 64K of memory. How can you chop it up so you have a bunch of free memory, and a bunch of used memory? How can you know if you have enough free memory to satisfy a request for a certain number of bytes? What should you do if someone frees memory that they are done using?

 

[nameless_centurian]

Awesome. I'm going to add "I'm psychic" to my resume.


The two OS books I have are Operating System Concepts (Sixth Edition), Silberschatz, Galvin, Gagne; and Operating Systems (Fourth Edition), Stallings.

There's also MicroC OS II: The Real Time Kernel (With CD-ROM) (Hardcover) by Jean Labrosse. If you've read my other posts about small computers being the best way to learn the hard stuff, then you'll understand why I recommend a book like this. Labrosse is one of the few good speakers I saw at the Embedded Systems Conference a couple years ago, too; he is good at answering questions and knows his stuff. Embedded guys eschew dynamic memory management, but his OS does implement a heap.

cool. if i get the money i'll look into buying the books (the school's library doesn't have them).

I'm feeling pretty snide today. So: if open source is so fucking great, why don't you just download the sources for Linux and read them? Heh, man, I feel better already.

alas, because i am a dunce when it comes to this stuff!

i like most open source because i dont have to pay 750 dollars for compliance to a license in order to build a server for a non-profit organization or my own hobbies

i have no beef with closed-source stuff as long as it works for me, which most of it does. i just can't afford it usually, so i try the open-source stuff.

Or, just approach it as a data structures problem. Say you have 64K of memory. How can you chop it up so you have a bunch of free memory, and a bunch of used memory? How can you know if you have enough free memory to satisfy a request for a certain number of bytes? What should you do if someone frees memory that they are done using?

it occurs to me that the programmer should populate a list or something containing the unused memory, or keep a list populated with the addresses of the used memory. i'll stick with keeping a list of unused memory.

when you're done using memory, return it to that structure.

but the wall i hit is: "how do i represent the memory that i am talking about?"
a structure needs memory to work, so if i am storing 32-bit values (the addresses of the memory in question), then i will run out of available memory by simply trying to store this information because every 4 bytes used to store a 32 bit address must be removed from the available memory.... and this would occure infinitey

the best thing i can think of would be to store ranges of addresses ina structure. the entire sie of the information stored in the nodes of the structure would be 64 bits, one number for the starting address range, one for the ending address range. when memory needs to be allocated, simply find the smallest range that suites your needs and take a chunk out of it and update the ranges in that node.

when freeing memory, send the address of each byte of mem being freed. then, insert these addresses back into the tree, altering the ranges as necessary.

the problems i find with this:

1) needing to impose "pages" or something.. basically at the beginning of run-time, the range has to be a set amount for each node, say 4k or something. so each node would have something like

address1: 0000
address2: 03E7

the next ordered node would have

address1: 0FA0
address2: 07CF

2) you'd have to create nodes as you go along for when the ranges don't match up perfectly for the node with the correct range.

node1: 0200
03FB

we want to return/deallocate 4 bytes, range 0208-020B

well, darn. that doesn't fit into the node in the proper way because 0208 does not succeed 0200 by 1 and 020B does not precede 03FB by one... i'll have to create a new node:

address1:0208
address2:020B

the size of the structure has potential to grow too large, you'd have to limit this.. eating up CPU... and the only way i can think to limit it is check after any allocation or deallocation if any nodes have back to back ranges, like 1 node's range ends where one begins. if this happens, merge the two and delete the smaller node. however, this might not be good enough!

at any rate, might this also give me the problem of "recursively" eating up memory if the ranges got to be too small?

edit: am i even close?
edit II: fixed an error

 

[mikeblas]

it occurs to me that the programmer should populate a list or something containing the unused memory, or keep a list populated with the addresses of the used memory. i'll stick with keeping a list of unused memory.

when you're done using memory, return it to that structure.

but the wall i hit is: "how do i represent the memory that i am talking about?"
a structure needs memory to work, so if i am storing 32-bit values (the addresses of the memory in question), then i will run out of available memory by simply trying to store this information because every 4 bytes used to store a 32 bit address must be removed from the available memory.... and this would occure infinitey

Not exactly infinitely; just as many times for each block you have. Say I ask you for 40 bytes. You know your overhead is 4 bytes. So why not allocate 44, use the 4 you need, and give me back the remaining forty?

the best thing i can think of would be to store ranges of addresses ina structure. the entire sie of the information stored in the nodes of the structure would be 64 bits, one number for the starting address range, one for the ending address range. when memory needs to be allocated, simply find the smallest range that suites your needs and take a chunk out of it and update the ranges in that node.

when freeing memory, send the address of each byte of mem being freed. then, insert these addresses back into the tree, altering the ranges as necessary.

Each byte? Why do need the address of each individual byte?

the problems i find with this:

1) needing to impose "pages" or something.. basically at the beginning of run-time, the range has to be a set amount for each node, say 4k or something. so each node would have something like

address1: 0000
address2: 03E7

the next ordered node would have

address1: 0FA0
address2: 07CF

Why is the ending address lower than the beginning address?

2) you'd have to create nodes as you go along for when the ranges don't match up perfectly for the node with the correct range.

node1: 0200
03FB

we want to return/deallocate 4 bytes, range 0208-020B

well, darn. that doesn't fit into the node in the proper way because 0208 does not succeed 0200 by 1 and 020B does not precede 03FB by one... i'll have to create a new node:

I've lost you by this point.

the size of the structure has potential to grow too large, you'd have to limit this.. eating up CPU... and the only way i can think to limit it is check after any allocation or deallocation if any nodes have back to back ranges, like 1 node's range ends where one begins. if this happens, merge the two and delete the smaller node. however, this might not be good enough!

That's a good idea; coalescing free blocks helps you avoid internal fragmentation.

 

[drizzt81]

The two OS books I have are Operating System Concepts (Sixth Edition), Silberschatz, Galvin, Gagne; and Operating Systems (Fourth Edition), Stallings.

While I am no OS guru, may I second the recommendation for these books. Very good choices imho.

 

[nameless_centurian]

Not exactly infinitely; just as many times for each block you have. Say I ask you for 40 bytes. You know your overhead is 4 bytes. So why not allocate 44, use the 4 you need, and give me back the remaining forty?

the overhead i was talking about wasn't from the allocation of the actual memory, it was in representing the mem that's been allocated... it's okay, though. i think the point is moot.

Each byte? Why do need the address of each individual byte?

or you could just send the starting address and an offset. remember, i am brand-new to this... i'll keep making dumb mistakes.

Why is the ending address lower than the beginning address?

one of those dumb mistakes, i guess. the second one should have been 1F3F

I've lost you by this point.

i might be way off, but wouldn't it be a problem if i wanted to return, say, 4 bytes to the structure and though it fell within one of the original ranges in one of the nodes, it does not match up perfectly?

for instance, let's say we JUST began our program. no dynamic mem was allocated yet, only stack mem. then the program comes to the first request for dynamic mem. llet's say it needs 4 bytes.

the program checks the structure for the smallest range of addresses in the entire structure. if the smallest range is large enough, take a 4-byte chunk out of the beginning of the range carved out in the node, starting at the first address in the node. adjust the range as necessary. if all the memory is used in the node after the allcation of this memory, delete the node.

let's say we do the same thing again, taking memory from the same node.

let's say we do this 3 more times.

when i go to deallocate the 2nd memory allocation, i'll have to create a new node because the ranges won't mesh. the first address in the range in the node is 12 bytes beyond the 4th byte of mem i am returning, not one byte beyond like i need.

on top of that, the last address in the next smallest node (small being measured by last address value in the range, not by number addresses present in the node's range) is 4 bytes before the first address of memory that i am returning. i can't put the returned memory there, either.

so i create a new node for the 4-byte range.... and if i do this many, many times there will be tons of fragmentation.

 

[mikeblas]

or you could just send the starting address and an offset. remember, i am brand-new to this... i'll keep making dumb mistakes.

Remember, when you're new to something, one way to learn is to have someone who knows the subject identify and correct your mistakes. It's nothing personal; I just thought you wanted help.

i might be way off, but wouldn't it be a problem if i wanted to return, say, 4 bytes to the structure and though it fell within one of the original ranges in one of the nodes, it does not match up perfectly?

I don't understand this one.

Let's start from the beginning; what's a "node"? What is in it, how big is it, what information is stored in it, and what does it represent?

for instance, let's say we JUST began our program. no dynamic mem was allocated yet, only stack mem. then the program comes to the first request for dynamic mem. llet's say it needs 4 bytes.

the program checks the structure for the smallest range of addresses in the entire structure. if the smallest range is large enough, take a 4-byte chunk out of the beginning of the range carved out in the node, starting at the first address in the node. adjust the range as necessary. if all the memory is used in the node after the allcation of this memory, delete the node.

Okay. So, your client comes along and frees some of the allocated memory. How do you know that you really allocated it to them if you've deleted the node? If you have to free the memory, won't you just have to reconstruct the node again? So why delete it?

so i create a new node for the 4-byte range.... and if i do this many, many times there will be tons of fragmentation.

Fragmentation is an interesting problem. You could argue that, no matter what scheme you come up with, you can't avoid fragmentation:

void* pstr[1000];

for (int n = 0; n < 1000; n++)
{
	// get a megabyte a thousand times, for a gig, total
	pv[n] = malloc(1024*1024);
}

for (int n = 0; n < 1000; n += 2)
{
	// free every other megabyte
	free(pv[n]);
	pv[n] = NULL;
}

// now, ask for two megabytes
void* pvExtra = malloc(1024*1024 * 2);

Whatever algorithm you cook up, I can probably come up with some access pattern that makes it sick. The better algorithm you have, the more pedantic my access patern has to be -- but it's still going to be possible.

So maybe you should neglect fragmentation for now and get the basic algorithm squared away.

 

[nameless_centurian]

Remember, when you're new to something, one way to learn is to have someone who knows the subject identify and correct your mistakes. It's nothing personal; I just thought you wanted help.

and i do! i'm sorry if i sounded offended, i was just explaining why i messed up.

my apologies. you've been the best teacher on this board for me so far, i certainly don't want you to stop.

Let's start from the beginning; what's a "node"? What is in it, how big is it, what information is stored in it, and what does it represent?

this "node" we speak of is the best that i can come up with in my limited thinking. each node in the structure i am speaking of contains 2 word-sized integers and a word-sized pointer to the next node in the structure (assuming that the structure is implemented with pointers instead of as an array or something). the first integer in the node represents the first address in the range. the second integer in the node represents the last address in the range. the range in question is the range of unallocated memory in that "page." if a node contains the inters 5 and A, we can say that the node tells us that addresses 5 through A are unallocated. the structure is composed of a number of these nodes.

i think the structure ought to be a heap ordered by smallest range of addresses, reordered after every allocation and deallocation. this way you can tell very quickly the smallest ranges. i'm not sure how to represent an empty range. perhaps the same number listed twice, where that same number was the last address you gave out as an allocation?

Okay. So, your client comes along and frees some of the allocated memory. How do you know that you really allocated it to them if you've deleted the node? If you have to free the memory, won't you just have to reconstruct the node again? So why delete it?

good point.

Fragmentation is an interesting problem. You could argue that, no matter what scheme you come up with, you can't avoid fragmentation:

void* pstr[1000];

for (int n = 0; n < 1000; n++)
{
	// get a megabyte a thousand times, for a gig, total
	pv[n] = malloc(1024*1024);
}

for (int n = 0; n < 1000; n += 2)
{
	// free every other megabyte
	free(pv[n]);
	pv[n] = NULL;
}

// now, ask for two megabytes
void* pvExtra = malloc(1024*1024 * 2);

Whatever algorithm you cook up, I can probably come up with some access pattern that makes it sick. The better algorithm you have, the more pedantic my access patern has to be -- but it's still going to be possible.

So maybe you should neglect fragmentation for now and get the basic algorithm squared away.

okay, i'll take your advice.

 

[mikeblas]

this "node" we speak of is the best that i can come up with in my limited thinking. each node in the structure i am speaking of contains 2 word-sized integers and a word-sized pointer to the next node in the structure (assuming that the structure is implemented with pointers instead of as an array or something). the first integer in the node represents the first address in the range. the second integer in the node represents the last address in the range. the range in question is the range of unallocated memory in that "page." if a node contains the inters 5 and A, we can say that the node tells us that addresses 5 through A are unallocated. the structure is composed of a number of these nodes.

Okay. So say we have this 64K block of memory, and we're just getting started, so it is uninitialized. Your structure:

struct tagMemoryBlock
{
   void* pLow;
   void* pHigh;
   struct tagMemoryBlock* pNext;
};

would describe one huge block of memory -- all 64K isn't in use. So I guess pLow would be 0, and pHigh would be 64K-1 (65535), and pNext would be NULL.

Is that correct?

Say I call your allocator and ask for 1024 bytes of memory. What happens?

Say, starting from the same initial state, I call your allocator and ask for 3022033 bytes of memory. What happens?

i think the structure ought to be a heap ordered by smallest range of addresses, reordered after every allocation and deallocation. this way you can tell very quickly the smallest ranges. i'm not sure how to represent an empty range. perhaps the same number listed twice, where that same number was the last address you gave out as an allocation?

Sorting the whole heap seems like a lot of work to do every allocation and deallocation. Wouldn't that add up to be very expensive very quickly?

Why do you need an empty range? What's interesting about it? It's not going to give you any memory, since it is empty. Nobody is going to free it, since it has no memory and they couldn't have allocated zero memory, right?

 

[nameless_centurian]

Okay. So say we have this 64K block of memory, and we're just getting started, so it is uninitialized. Your structure:

struct tagMemoryBlock
{
   void* pLow;
   void* pHigh;
   struct tagMemoryBlock* pNext;
};

would describe one huge block of memory -- all 64K isn't in use. So I guess pLow would be 0, and pHigh would be 64K-1 (65535), and pNext would be NULL.

Is that correct?

looks good enough. it's about what i was picturing.

Say I call your allocator and ask for 1024 bytes of memory. What happens?

we check to see that pLow isn't NULL and that pHigh isn't NULL. if they aren't NULL we see if we have enough memory. if we do, we return a pointer to it. if we don't, we return null

if ((pLow && pHigh) && pHigh-pLow) >=(void*) amount_requested){
   pLow += amount_requested;
   return  (*pLow) - (void*) 4;
}

else
   return NULL;

Say, starting from the same initial state, I call your allocator and ask for 3022033 bytes of memory. What happens?

well, if we're only working with 64K, then it returns NULL

Sorting the whole heap seems like a lot of work to do every allocation and deallocation. Wouldn't that add up to be very expensive very quickly?

i think it would be, but is this worse than doing an inefficient search every time to find the smallest range of unallocated memory to draw from? i really don't know.

Why do you need an empty range? What's interesting about it? It's not going to give you any memory, since it is empty. Nobody is going to free it, since it has no memory and they couldn't have allocated zero memory, right?

i think the empty range is needed to show that all memory represented by that node is in use. it's for the algorithm.

 

[mikeblas]

we check to see that pLow isn't NULL and that pHigh isn't NULL. if they aren't NULL we see if we have enough memory. if we do, we return a pointer to it. if we don't, we return null

if ((pLow && pHigh) && pHigh-pLow) >=(void*) amount_requested){
   pLow += amount_requested;
   return  (*pLow) - (void*) 4;
}

else
   return NULL;

What is it that ever sets pLow or pHigh to NULL?

So we've got our one single node:

pLow = 0
pHigh = 65535
pNext = NULL

and you run the above code with amount_requested == 1024. That sets:

pLow = 1024
pHigh = 65535
pNext = NULL

and returns to me 1020. That doesn't seem right.

 

[nameless_centurian]

What is it that ever sets pLow or pHigh to NULL?

So we've got our one single node:

pLow = 0
pHigh = 65535
pNext = NULL

and you run the above code with amount_requested == 1024. That sets:

pLow = 1024
pHigh = 65535
pNext = NULL

and returns to me 1020. That doesn't seem right.

dah! you're right. i was thinking in terms of single integers. it shouldn't be 4, it should be amount_requested.

how is this for a fix and answering how the pointers get changed to NULL?

if ((pLow && pHigh) && pHigh-pLow >=(void*) amount_requested){
   pLow += amount_requested;
   if (pLow == pHigh){
      pLow = NULL; pHigh = NULL;
   }
   return  pLow - (void*) amount_requested;
}

else
   return NULL;

 

[mikeblas]

if ((pLow && pHigh) && pHigh-pLow >=(void*) amount_requested){
   pLow += amount_requested;
   if (pLow == pHigh){
      pLow = NULL; pHigh = NULL;
   }
   return  pLow - (void*) amount_requested;
}

else
   return NULL;

Okay, so I make my call with 1024. You set:

pLow = 1024
pHigh = 65535
pNext = NULL;

and return to me 0. I guess that works. Now, I call you to free(0), which is the pointer you gave me. What do you do?

What if I call your allocation routine with 65535? You set:

pLow = NULL;
pHIgh = NULL;
pNext= NULL;

and return to me -65535. That doesn't seem right.

 

[nameless_centurian]

i'm running out of time for now.

perhaps it isn't the best idea to change the pointers to null, and thus that check wuld be unneccesary. i'm not certain. i'll think on it.

at any rate, thanks for your help. i need to get going.

i'll probably resurrect this thread i a couple days