What happens when there is a request for a block of memory that does not matter 2?

Question

Suppose we execute a malloc request for a memory block of size n, where 2 ^ k! = N for k> 0. Malloc returns us the space for this requested memory block, but as the remainder buffer is processed from the page. I read "Pages", as a rule, are blocks of memory that are powers of two.

The wiki states the following:

Like any method of memory allocation, the heap will become fragmented; that is, there will be sections of used and unused memory in the allocated space on the heap. A good allocator will attempt to find an unused area of already allocated memory to use before resorting to expanding the heap. 

So my question is how is this tracked?

EDIT: how is unused memory tracked when using malloc?

Answer 1

It really depends on the particular implementation, as Morten Sibur pointed out. In very simple cases, there may be a list of free blocks of a fixed size (possibly having the same size), so unused memory is simply lost. Note that real implementations will never use such simplified algorithms.

This is an overview of some simple features: http://www.osdcom.info/content/view/31/39/

There are several interesting links on this Wikipedia entry, including the ones above: http://en.wikipedia.org/wiki/Dynamic_memory_allocation#Implementations

As a final note, googling "malloc implementation" displays a bunch (pun intended) of valuable links.

Answer 2

The BSD-style standard memory allocation unit basically works as follows:

• It stores a linked list of pre-allocated memory blocks for sizes 2 ^ k for k <= 12 (for example).
• In fact, each list for a given k consists of memory blocks from different areas, see below.
• The malloc request for n bytes is served by computing n ', the closest 2 ^ k> = n, then it scans the first area in the list for k, and then returns the first free block in the free list for that area.
• When there is no allocated memory block for size 2 ^ k, a region is allocated, and the region represents most of the continuous memory, say, 4 KB of memory. Then this piece of memory is divided into pieces of 2 ^ k bytes. At the beginning of the continuous memory area there is accounting information, for example, where you can find a linked list of free blocks within the area. You can also use a bitmap, but the linked list usually has better cache behavior (you want the next allocated block to return memory that is already in the cache).
• The reason for using areas is that free (ptr) can be effectively implemented. ptr and 0xfffff000 in this example points to the beginning of an area that contains accounting structures, and allows you to link the memory block back to the area.
• The BSD allocator will waste space by always returning a 2 ^ k memory block, but it can reuse the block memory to save a free list, which is a good property. Distribution is also fast.

Modifications of the above general idea include:

• Using anonymous mmap for large distributions. This transfers the work to the kernel for processing large mullocks and avoids a large amount of memory in these cases.
• The malloc GNU version has special cases for non-powered slaves. There is nothing in the BSD allocator that requires 2 ^ k memory blocks to be returned only if there are predefined bucket sizes. The GNU distributor has more buckets and therefore less space is wasted.
• Sharing memory between threads is a complex issue. Blocking distribution competition is an important consideration, so in the GNU distributor, for example, it will be willing to create additional areas for different threads for a given bucket size if it ever encounters a distribution lockout conflict.

Answer 3

This varies greatly from implementation to implementation. Some lose space, some pages with delimiters, until they get the required size (or close to it) & c.

If you ask out of curiosity, I suggest you read the source code for the implementation in question,

If this is due to performance issues, try comparing it and see what happens.