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?

user229044
  • 232,980
  • 40
  • 330
  • 338
statnik
  • 61
  • 4
  • 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. – Remy Lebeau Feb 28 '15 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). – barak manos Feb 28 '15 at 20:43
  • The memory management done by the OS. – SHR Feb 28 '15 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. – Jerry Coffin Feb 28 '15 at 20:54
  • Operator new is typically a library function provided by libstdc++, which in turn uses sbrk and mmap to allocate larger chunks of memory from the OS. – smossen Feb 28 '15 at 20:54
  • @SHR: The OS does some basic memory management, but can't manage small memory chunks which you can allocate with new/malloc. – Juergen Feb 28 '15 at 21:03
  • 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. – James Kanze Feb 28 '15 at 21:37
  • @barakmanos That's definitely the simplest solution, and was actually used on systems some thirty years ago. On modern systems, I'm afraid it would be too slow, and more complicated algorithms are used. – James Kanze Feb 28 '15 at 21:39
  • @JerryCoffin And of course, there is some logic to coalesce adjacent freed blocks. And to keep small allocations more or less adjacent, so that they don't fragment the memory any more than necessary. And to ensure that the address returned from larger blocks is page aligned. And who knows what additional issues the implementers thought important. – James Kanze Feb 28 '15 at 21:41
  • `new` doesn't always involve `malloc`, but I'm confident that the dupe is what you're really trying to ask. – Lightness Races in Orbit Feb 28 '15 at 22:24

3 Answers3

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!

Community
  • 1
  • 1
Juergen
  • 12,378
  • 7
  • 39
  • 55
  • "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? – statnik Feb 28 '15 at 21:16
  • Ok, that is right. I forgot about that -- and will add in my answer. – Juergen Feb 28 '15 at 21:18
  • 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.) – James Kanze Feb 28 '15 at 21:27
  • @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. – Juergen Feb 28 '15 at 21:31
  • 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. – James Kanze Feb 28 '15 at 23:28
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.

James Kanze
  • 150,581
  • 18
  • 184
  • 329
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.

Christophe
  • 68,716
  • 7
  • 72
  • 138