Jump to content

c dynamic memory allocation

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by NicM (talk | contribs) at 13:54, 25 August 2006 (→‎Allocation failure: kill --). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.


In computing, malloc is a subroutine provided in the C programming language's standard library for performing dynamic memory allocation.

Rationale

The C programming language normally manages memory either statically or automatically. Static-duration variables are allocated in main (fixed) memory and persist for the lifetime of the program; automatic-duration variables are allocated on the stack and come and go as functions are called and return. However, both these forms of allocation are somewhat limited, as the size of the allocation must be a compile-time constant. If the required size will not be known until run-time — for example, if data of arbitrary size is being read from the user or from a disk file — using fixed-size data objects is inadequate.

The lifetime of allocated memory is also a concern. Neither static- nor automatic-duration memory is adequate for all situations. Stack-allocated data can obviously not be persisted across multiple function calls, while static data persists for the life of the program whether you need it to or not. In many situations the programmer requires greater flexibility in managing the lifetime of allocated memory.

These limitations are avoided by using dynamic memory allocation in which memory is more explicitly but more flexibly managed, typically by allocating it from a heap, an area of memory structured for this purpose. In C, one uses the library function malloc to allocate a block of memory on the heap. The program accesses this block of memory via a pointer which malloc returns. When the memory is no longer needed, the pointer is passed to free which deallocates the memory so that it can be reused by other parts of the program.

Dynamic memory allocation in C

The malloc function is the basic function used to allocate memory on the heap in C. Its prototype is 

void *malloc(size_t size)

which allocates size bytes of memory. If the allocation succeeds, a pointer to the block of memory is returned.

malloc returns a void pointer (void *), which indicates that it is a pointer to a region of unknown data type. This pointer is typically cast to a more specific pointer type by the programmer before being used. However, these days casting malloc return value is discouraged; originally, malloc returned a char *, which usually required casting, but void * needs not be cast, and may lead to ambiguities. [1] [2]

Memory allocated via malloc is persistent: it will continue to exist until the program terminates or the memory is explicitly deallocated by the programmer (that is, the block is said to be "freed"). This is achieved by use of the free function. Its prototype is 

void free(void *pointer)

which releases the block of memory pointed to by pointer. pointer must have been previously returned by malloc or calloc, (or a function which uses one of these, eg strdup), and must only be passed to free once.

Usage example

The standard method of creating an array of ten integers on the stack is: 

int array[10];

To allocate a similar array dynamically, the following code could be used: 

#include <stdlib.h>

/* Allocate space for an array with ten elements of type int. */
int *ptr = malloc(sizeof (int) * 10);
if (ptr == NULL)
   exit(EXIT_FAILURE); /* Memory could not be allocated, so exit. */

/* Allocation succeeded. */

malloc returns a block of memory that is allocated for the programmer to use, but is uninitialized. The memory is usually initialized by hand if necessary -- either via the memset function, or by one or more assignment statements that dereference the pointer. An alternative is to use the calloc function, which allocates memory and then initializes it. Its prototype is 

void *calloc(size_t nelements, size_t bytes)

which allocates a region of memory large enough to hold nelements of size bytes each. The allocated region is initialized to zero.

It is often useful to be able to grow or shrink a block of memory. This can be done using malloc and free: a new block of the appropriate size can be allocated, the content can be copied over, and then the old block can be freed. However, this is somewhat awkward; instead, the realloc function can be used. Its prototype is 

void *realloc(void *pointer, size_t bytes)

realloc returns a pointer to a memory region of the specified size. If the new size is greater than the old size, the block is grown, otherwise it is shrunk.

valloc is identical to malloc, except that the allocated memory is aligned to a page boundary. Pointers allocated with valloc cannot be passed to realloc.[3]

Common errors

Some programmers find that the improper use of malloc and related functions in C can be a frequent source of bugs.

Allocation failure

malloc is not guaranteed to succeed — if there is no memory available, or if the program has exceeded the amount of memory it is allowed to reference, malloc will return a NULL pointer. Depending on the nature of the underlying environment, this may or may not be a likely occurrence. Many programs do not check for malloc failure. Such a program would attempt to use the NULL pointer returned by malloc as if it pointed to allocated memory, and the program would crash. This has traditionally been considered an incorrect design, although it remains common, as memory allocation failures only occur rarely in most situations, and the program frequently can do nothing better than to exit anyway. Checking for allocation failure is more important when implementing libraries — since the library might be used in low-memory environments, it is usually considered good practice to return memory allocation failures to the program using the library and allow it to choose whether to attempt to handle the error.

Memory leaks

The return value of malloc, calloc, and realloc should be passed to the free function before all well-defined accessible references to it are lost so that it can be released. If this is not done, the allocated memory is not released before the process exits — in other words, a memory leak will occur.

Use after free

After a pointer has been passed to free, it references a region of memory with undefined content, which may not be available for use. However, the pointer may still be used, for example: 

 int *ptr = malloc(sizeof *ptr);
 free(ptr);
 *ptr = 0; /* Undefined behavior! */

Code like this may have unpredictable behavior — after the memory has been freed, the system may reuse that memory region for storage of unrelated data. Therefore, writing through a pointer to a deallocated region of memory may result in overwriting another piece of data somewhere else in the program. Depending on what data is overwritten, this may cause data corruption or cause the program to crash at a later time. A particularly bad example of this problem is if the same pointer is passed to free twice, known as a double free. To avoid this, some programmers set pointers to NULL after freeing them, as free(NULL) is safe—it does nothing.

Implementations

The implementation of memory management depends greatly upon operating system and architecture. Some operating systems supply an allocator for malloc, while others supply functions to control certain regions of data.

The same dynamic memory allocator is often used to implement both malloc and operator new in C++. Hence, we will call this the allocator rather than malloc.

Heap-based

Implementation of the allocator on IA-32 architectures is commonly done using the heap, or data segment. The allocator will usually expand and contract the heap to fulfill allocation requests.

The heap method suffers from a few inherent flaws, stemming entirely from fragmentation. 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. However, due to performance it can be impossible to use an allocator in a real time system and a memory pool must be deployed instead.

The major problem with this method is that the heap has only two significant attributes: base, or the beginning of the heap in virtual memory space; and length, or its size. The heap requires enough system memory to fill its entire length, and its base can never change. Thus, any large areas of unused memory are wasted. The heap can get "stuck" in this position if a small used segment exists at the end of the heap, which could waste any magnitude of address space, from a few megabytes to a few hundred.

The glibc allocator

The GNU C library, glibc, uses both brk and mmap on the Linux operating system. The brk system call will change the size of the heap to be larger or smaller as needed; while the mmap system call will be used when extremely large segments are allocated. The heap method suffers the same flaws as any other, while the mmap method may avert problems with huge buffers trapping a small allocation at the end after their expiration.

The mmap method has its own flaws. It always allocates a segment by mapping pages. Only one set of mapped pages exists for each allocated segment. Mapping a single byte will use an entire page, usually 4096 bytes, on IA-32; however, large pages are 4MiB, 1024 times larger, and so this method could be particularly devastating if userspace uses only large pages. The advantage to the mmap method is that when the segment is freed, the memory is returned to the system immediately.

OpenBSD's malloc

OpenBSD's implementation of the malloc function makes use of mmap. For requests greater in size than one page, the entire allocation is retrieved using mmap; smaller sizes are assigned from memory pools maintained by malloc within a number of "bucket pages," also allocated with mmap. On a call to free, memory is released and unmapped from the process address space using munmap. This system is designed to improve security by taking advantage of the address space layout randomization and gap page features implemented as part of OpenBSD's mmap system call, and to detect use-after-free bugs—as a large memory allocation is completely unmapped after it is freed, further use causes a segmentation fault and termination of the program.

Maximum allocation size

The largest possible memory block malloc can allocate depends on the host system, particularly the size of physical memory and the operating system implementation. Theoretically, the largest number should be the maximum value that can be held in a size_t type, which is an implementation-dependent unsigned integer representing the size of an area of memory. The maximum value is (size_t) −1, or the constant SIZE_MAX in the C99 standard. The C standards guarantee that a certain minimum (0x7FFF in C90, 0xFFFF in C99) for at least one object can be allocated.

See also

Retrieved from "https://en.wikipedia.org/w/index.php?title=C_dynamic_memory_allocation&oldid=71808064"