A site 'Memory Allocation' that explains how memory is allocated and released when running a program with an image image that is easy to understand
Memory is required to run programs on your computer. Of course, the program itself needs to be loaded into memory, and it is no exaggeration to say that most of the operations performed by the program are ``fetching values from memory, calculating, and storing them in memory''. Sam Rose, a veteran programmer, explains on his blog how memory is managed when the program runs.
Memory Allocation
The C language standard library provides two functions, 'malloc' and 'free'. These two functions have existed since Unix v7 in 1979. malloc is responsible for allocating memory and free is responsible for freeing memory. Sam Rose's commentary will proceed with the idea of ``implementing the contents of these two functions yourself''.
And the figure below is an image image of the memory. One square corresponds to one byte, and numbers from 0 to 255 can be stored in each square. In order to simplify the story this time, we will consider the state where the memory is only 32 bytes in total.
I'll also use dark orange to represent memory allocated by the program. The figure below shows that 4 bytes of memory are reserved. On the other hand, the light orange color represents unallocated memory.
If you pass 'how many bytes of memory you want to allocate' to the malloc function, it will allocate that amount of memory. For example, malloc(4) left the first 4 bytes of memory in use.
Furthermore, executing malloc(5) and malloc(6) will make the corresponding memory in use.
For malloc, it was OK to pass 'how many bytes of memory should be allocated', but for free, which releases memory, it is necessary to point to the first address of memory.
Executing free(0x4) or free(0x9) freed the corresponding location.
This '0x' notation is a prefix that indicates that it is a hexadecimal notation. Numbers up to 9 have the same representation in normal decimal notation and hexadecimal notation.
'10' has two digits in decimal, but is represented as 'a' in hexadecimal.
Similarly, numbers up to 15 are written in the alphabet.
And when it reaches 16, the digits will increase and it will be written as '10'.
Expressing the memory address in hexadecimal is like this. Originally, it would be better to prefix all squares with '0x', but it was omitted for space reasons.
Now, with the knowledge so far, you will be able to implement the 'malloc' function on your own. As the simplest implementation, consider an implementation that 'stores the first address of an empty block, allocates the necessary amount of memory from there, and stores the address next to the last memory allocated'. I'll try. First, malloc(4) was executed to allocate 4 bytes of memory and then move the marker to the next address.
In this implementation, although there is no problem when allocating memory, it is not possible to release the memory because there is no information 'from where to where is one block'. It seems to be a flawed implementation because the amount of memory used increases endlessly while the program is in use. It is said that it may become.
However, the ability to free memory is essential when implementing a general memory allocator. Now try to save the address and size of all allocated and free memory in the 'allocated list' and 'free list'. At first, the free list contains information '0x0 address, 32 bytes'. Of course, memory is also required to save the 'allocated list' and 'free list', but this time I think that they are saved in a different place.
When malloc is called, it searches the free list from top to bottom until the required amount of memory can be allocated, allocates memory, and registers it in the allocation list.
Free can now be executed because the allocation list tells you how many bytes to free. The freed memory is registered in the free list.
In this implementation, when memory is allocated and freed repeatedly, the size of one block becomes smaller and smaller, and there is a problem that memory cannot be allocated even though there is a large amount of free memory when viewed as a whole.
Therefore, I checked the free list when releasing memory, and fixed it so that if the adjacent block was free, it would be coalesced.
I thought I had a perfect memory allocator, but I still have a problem. As shown in the figure below, if you repeatedly allocate and free memory, blocks that are 'too small to use' will appear. This is called memory fragmentation. Since the address of the memory allocated when mallocing is saved in the program and used to specify free, the memory allocation cannot be changed arbitrarily on the memory allocator side.
Various techniques have been developed to prevent such fragmentation. For example, the figure below shows that 'at least 4 bytes will be secured when there is an instruction that secures a small number of bytes of memory'. Fragmentation is less likely to occur, but the disadvantage is that the amount of memory required is greater than the amount of memory actually used.
Another approach exists to reserve a separate area for smaller allocations. This technique also reduces fragmentation, but has the disadvantage of leaving less space available when large batches of allocations are needed. Allocators that use this approach are called slab allocators. In fact, not only two types of large and small areas, but also areas corresponding to various sizes are prepared and used.
Although not discussed so far, let's consider the case where 0 is specified in malloc. In the case of a simple implementation that allocates at least 4 bytes, a 4-byte area is allocated as many times as malloc(0) is called, and a considerable amount of memory is wasted. On the other hand, some memory allocator implementations consistently return a 'null pointer' when malloc (0) is executed. It states that you shouldn't use 'malloc(0)' in either case, as it will crash if your program tries to read or write to a null pointer.
So far, memory allocator implementations have used 'allocation lists' and 'free lists' stored in different areas of memory. There are also approaches that do not use such lists. For example, the figure below shows an unallocated free space, but information about that space is stored before and after the free space. The '29' at the beginning and end is the number of bytes in the area, and the '1' in the second square indicates that the area is unused. At first glance, it seems wasteful that the number of bytes in the area is saved at the beginning and end, but it will be important when combining areas.
If you allocate 4 bytes of memory here, the memory allocator checks the area from the beginning of the memory, and if it finds enough free space, it creates a new area there.
If you allocate a 4-byte area again, it will look like the figure below.
The advantage of this approach is that you only need to set the flag at address +1 to '1' when freeing the memory.
When releasing memory, it is necessary to check the usage status of the memory before and after, and combine if there is free space. By saving the size of the area at the end as well, you can see where in the previous area you can check the memory usage status.
Since all the regions are free, they are merged back to the initial state.
Sam Rose has published a tool called
Related Posts:
in Software, Posted by log1d_ts