3

In C++, how may operator new save information that a piece of memory is allocated? AFAIK, it does not work for constant time and have to search for free memory in heap. Or, maybe, it is not about C++, but about OS?

P.S. I do not know whether it is specified by standard or not, whether it is managed by OS or by C++, but how may it in fact be implemented?

Improve this question
10
  • 6
    How new allocates memory is an implementation detail by the compiler vendor. Some new implementations use malloc() internally, some don't. But rarely do any of them go directly to the OS, there is usually a runtime library in between, managing memory allocations (amongst other things). Code should not care on way or the other. It asks the compiler to new some memory, and gets a pointer in return. How the memory is managed is up to the compiler to decide. Commented Feb 28, 2015 at 20:42
  • 1
    I don't think that the C++ language standard defines it, but the easiest way is to allocate a few more bytes, and store inside them the address of the next available block of memory (so the heap is generally implemented as a linked-list). Commented Feb 28, 2015 at 20:43
  • The memory management done by the OS. Commented Feb 28, 2015 at 20:45
  • The short answer is that it may well not do so at all. A memory manager mostly keeps track of blocks of memory that are available for allocation. Blocks that are currently allocated are simply removed from its list of blocks that are available. When you call delete, the block is added back to the free list. Commented Feb 28, 2015 at 20:54
  • 1
    @Juergen There's no reason why an OS can't manage small memory chunks; I've actually used one implementation of C where malloc and free were just requests to the OS. Most can't do it very efficiently, however, so for efficiency reasons, malloc and free typically allocate from large, in process memory blocks. Unless you request something very big; it's not unusual for malloc to go directly to the OS for something like a couple of mega. Commented Feb 28, 2015 at 21:37

3 Answers 3

Reset to default
2

There's no simple, standard answer. Most implementations of operator new/operator delete ultimately forward to malloc/free, but there are a lot of different algorithms which can be used for those. The only thing that's more or less universal is that allocation will typically allocate a little bit more than requested, and use the extra memory (normally in front of the address actually returned) to maintain some additional information: either the actual size allocated or a pointer to the end of the block (or the start of the next block). Except that some algorithms will keep allocations of the same size together, and be able to determine the size from the address. There is no single answer to your question.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

new is oftentimes implemented on basis of malloc/free.

How does malloc/free implement it? The answer is: It depends on the implementation. Surprisingly: Malloc oftentimes does not keep track of the allocated blocks at all! The only thing, malloc is doing most of the time, is adding a little bit of information containing the size of the block "before" the allocated block. Meaning, that when you allocate 40 bytes, it will allocate 44 bytes (on 32bit machines) and writes the size in the first 4 bytes. It will return the address of this chunk+4 to you.

Malloc/free keeps track of a freelist. A freelist is a list of freed memory chunks that is not (yet) be given back to the operating system. Malloc searches the freelist, when a new block is needed and when a fitting block is available uses that.

But a more exhausting answer about malloc/free, I have given here: How do malloc() and free() work?

One additional information:

One implication of the fact, that many allocators don't track allocated blocks: When you return memory by free or delete and pass a pointer in, that was not allocated before, you will corrupt your heap, since the system is not able to check if the pointer is valid. The really ugly thing about it is, that in such a case, your program will not dump immediately, but any time after the error-cause occured ... and thus this error would be really ugly to find. That is one reason, memory handling in C/C++ is so hard!

Improve this answer

5 Comments

"Malloc oftentimes does not keep track of the allocated blocks at all!" But free() does not take a size of block, how can it know it?
Ok, that is right. I forgot about that -- and will add in my answer.
At least one widespread implementation kept both allocate and free blocks in the same list. The list was ordered, which made coalescing free blocks (which didn't take place until the search in malloc arrived at the free block) very simple. (Modern implementations are, I suspect, a lot more complicated, with optimizations for small blocks, etc.)
@JamesKanze: I am not familiar with all implementations, of course and also the newest implementation, I don't know. That is the reason, I tried to answer carefully. Also with special security functions, included today, there are always new developments of course. But as developer it is better not depend on the fact, that malloc/new will save your corrupt pointers.
But that's true even with implementations that keep the allocated blocks in the list. The only issue is that you are describing one particular possible implementation (which has probably actually been used, even if I've never seen it). There are many, many others, and I suspect the one you describe is not particularly common.
0

new maintains a data structure to keep track of individually allocated blocks. There are plenty of ways for doing that. Usually, some kind of linked list is used.

Here a small article to illustrate this.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.