flat assembler
Message board for the users of flat assembler.

Index > Main > Memory fragmentation

Author
Thread Post new topic Reply to topic
Apos



Joined: 11 Jan 2012
Posts: 17
Location: Paris, France (I'm not from France though.)
Apos
Hello everyone! I've lurked enough, now it's the time I ask one more question. Very Happy

I've been pondering on this for months, and I didn't feel ready to ask until now.

Basically, when I allocate a new variable, I just have to move the stack pointer in order to leave some room for it in the stack. When I want to remove the last variable in the stack, I can move the stack pointer in the opposite direction in order for the variable to be outside of the stack range.

This is good, since you just need to initialize variables in the reverse order that you will want to remove them.

The fragmentation problem arises when you want to create a variable type that can grow without having to be continuous such as a linked list.

Just to be sure we are on the same page, here is the definition of a linked list:
Quote:
"An ordered set of data elements, each containing a link to its successor (and sometimes its predecessor)."

More info: http://en.wikipedia.org/wiki/Linked_list

Once you start introducing linked lists, it becomes impossible to remove variables in a general way for all programs since there is no real way of knowing which variable will be last in the stack at compile time.

The only thing I can think of to fix this problem is to have a sort of garbage collector. Is that were a garbage collector comes in? Or is there something simpler that wouldn't have a too big performance impact?
_______________
Example code snippets are welcome, but what I am looking to find is the theory explaining how it should be done.

Hopefully this won't be too hard to understand. I've tried to explain this as best as I could.

_________________
"A designer knows he has achieved perfection not when there is nothing left to add, but when there is nothing left to take away." - Antoine de Saint-Exupéry


Last edited by Apos on 07 Jul 2012, 15:35; edited 1 time in total
Post 07 Jul 2012, 12:54
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17287
Location: In your JS exploiting you and your system
revolution
Linked lists are really easy to handle. For my systems I use two list head pointers where one list is "used" sections and the other is "free" sections. As the memory is used or freed it just moves sections from one list to the other. You can also compact the lists occasionally to bring all sections of the same type into contiguous memory locations and then realloc the memory to free up space and return it to the OS.

Garbage collectors are very different things and work in an entirely different way. They usually end up being very complicated (as with most HLL related things) and I would hesitate before deciding upon such a complex solution.
Post 07 Jul 2012, 13:04
View user's profile Send private message Visit poster's website Reply with quote
hopcode



Joined: 04 Mar 2008
Posts: 563
Location: Germany
hopcode
revolution wrote:
...one list is "used" sections and the other is "free" sections...
one of the best solutions.
in my ART (Assembly RunTime) you will find one of my dozens implementations of something concerning the method above, from line 227:
http://code.google.com/p/x64lab/source/browse/develop/shared/art.asm

that works very good and fast, using size of chunks from the equates here:
http://code.google.com/p/x64lab/source/browse/develop/shared/art.equ
but i dont use it anymore because i have now one even faster and better
(but no open source sorry) i called memmuth (tm) Smile for the record.
this is but the ancestor of it.

Cheers,

_________________
⠓⠕⠏⠉⠕⠙⠑
Post 07 Jul 2012, 15:53
View user's profile Send private message Visit poster's website Reply with quote
Apos



Joined: 11 Jan 2012
Posts: 17
Location: Paris, France (I'm not from France though.)
Apos
Thanks a lot so far! I think my synapses are connecting. Cool

If I understand correctly, when there is an element from the "free" sections at the end of the stack, then it is safe to remove it from the stack range.

I've done a few diagrams to make sure I get this right:

General case:
Image

General case with the "free" sections:
Image

I'm guessing this next case would be when I would be required to move the "Used List Element 3" above the variables that need to be removed? (Or overwriting them.)
Image

Note: The left stack is before the stack pointer has been moved and the right stack is after.

In other words, the "free" sections can only be removed when they are at the end of the stack. If I would want to remove them when they are in the middle, I would have to move all the other variables up and overwrite it doing so.

Am I getting this right?

_________________
"A designer knows he has achieved perfection not when there is nothing left to add, but when there is nothing left to take away." - Antoine de Saint-Exupéry
Post 07 Jul 2012, 17:07
View user's profile Send private message Reply with quote
hopcode



Joined: 04 Mar 2008
Posts: 563
Location: Germany
hopcode
Apos wrote:
Am I getting this right?
basically yes.
but it seems you are trying to stack linked lists of mem-chunks.
i.e. mixing stack+lists.
if so, well, this is not suggestable because a very complex management of the stack pointer
is required. anyway that stack size of your allocator would result not growable, and consequently by reserving/using the maximum of it
(on Win 64bit max stack size is ~1Gb),
your allocator should do acrobatics to distinguish/trace the areas marked free/used from those stack areas used by the client app for itself,
and those the client app requires from your allocator.
ergo: memory becomes very fragmented and allocator slow because it accesses very distant areas/pages. exactly what we want to avoid.
(reducing the reloading of memory pages into the cache is an imprtant goal too)

here explained some methods,
http://www.memorymanagement.org/articles/alloc.html
http://gee.cs.oswego.edu/dl/html/malloc.html

Cheers,

_________________
⠓⠕⠏⠉⠕⠙⠑
Post 07 Jul 2012, 20:15
View user's profile Send private message Visit poster's website Reply with quote
AsmGuru62



Joined: 28 Jan 2004
Posts: 1412
Location: Toronto, Canada
AsmGuru62
Why not use the heap for the allocation?

1. call HeapCreate as your function begins
2. in the function call HeapAllocate as many times as you need
3. call HeapDestroy as your function ends (no need to call HeapFree)
Post 08 Jul 2012, 11:59
View user's profile Send private message Send e-mail Reply with quote
hopcode



Joined: 04 Mar 2008
Posts: 563
Location: Germany
hopcode
AsmGuru62 wrote:
Why not use the heap for the allocation?
mmh, yes but once you have malloc why avoid it ? anyway for an allocator i suggest VirtualAlloc because very flexible.
other case is under portability restrictions wher i cannot see other methods than LIBC-ing it.
some quasi-benchmarks here
http://f0dder.reteam.org/memalloc.htm

Cheers,

_________________
⠓⠕⠏⠉⠕⠙⠑
Post 09 Jul 2012, 05:40
View user's profile Send private message Visit poster's website Reply with quote
Apos



Joined: 11 Jan 2012
Posts: 17
Location: Paris, France (I'm not from France though.)
Apos
Well... my mind just got blown! This thread is really amazing already. Shocked

Sorry not to have responded earlier, I was still processing all that I had learned. I have gone through everything that was posted here a couple times, reading the articles that were linked. I also found a book about memory allocation which seems pretty good by Charles Weir and James Noble (http://www.smallmemory.com/book.html) (mostly chapter 6). It had this nice analogy:
Quote:
What goes up must come down; what is allocated must be deallocated.

Changing the subject slightly, there is one question that came to my mind after seeing the stack memory limit, does it mean there is something else than the stack that I can use to store my program's memory? Does it have to do with the heap? (Or is the heap separated from the stack?)

(I probably could have looked up these questions easily, but I thought it was appropriate to ask them here.)

_________________
"A designer knows he has achieved perfection not when there is nothing left to add, but when there is nothing left to take away." - Antoine de Saint-Exupéry
Post 09 Jul 2012, 11:25
View user's profile Send private message Reply with quote
hopcode



Joined: 04 Mar 2008
Posts: 563
Location: Germany
hopcode
Apos wrote:
...I thought it was appropriate to ask them here
yes, why not. and the matter is not so obvious as it seems.
i will try using some guidelines and hints instead of
explaining one more time how the wheel works.

because everything has a limit in size,
- the stack
- the process space

and in hardware speed:
- the BUS
- the DRAM modules
- the cache

your app should have what i call magnitudo
i.e. an awareness of data quantities it manages.
this awareness should be a MUST, a policy

1) by design
2) if you want your app to work better than other software
3) if your app is "Umweltfreundlich" i.e it tries to reduce
damages against the environment.

you choose a memory system,(or an OS) accordingly.
when you say, for example

format PE64 GUI 5.0
heap 2000000h
stack 100000h

you'll agree to
a) the process rules assigned to your app by windows
b) the OS loader will try to reserve your app that sizes of heap and stack
c) debugger consequently will try to adjust debugging to those values.

then further knowledge about those params on windows PE tell us how
behave stack and heap of your app on windows, according its process-rules.

anyway the question again is wether your app is
aware of the quantities it manages. because if your app
manages movies in the size-order of Gbytes, well, an alternative
memory system should apply here, whenever keeping those above
stack-heap values of your app constant.
an alternative for big files may be by using memory mapped files
or Virtual allocation.

also, different memory systems may live together (and most do in the
best software) and co-operate together for better performances.

thus definitions of heap, stack, virtual spaces, etc.,
you can find it everywhere on the net, OS accordingly.

Cheers,

_________________
⠓⠕⠏⠉⠕⠙⠑
Post 09 Jul 2012, 15:48
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.