Memory allocation

Memory allocation
You are encouraged to solve this task according to the task description, using any language you may know.

Show how to explicitly allocate and deallocate blocks of memory in your language. Show access to different types of memory (i.e., heap, stack, shared, foreign) if applicable.

Ada

Stack

Stack in Ada is allocated by declaration of an object in some scope of a block or else a subprogram: <lang ada> declare

  X : Integer; -- Allocated on the stack

begin

  ...

end; -- X is freed </lang>

Heap

Heap is allocated with the allocator new on the context where a pool-unspecific pointer is expected: <lang ada> declare

  type Integer_Ptr is access Integer;
  Ptr : Integer_Ptr := new Integer; -- Allocated in the heap

begin

  ...

end; -- Memory is freed because Integer_Ptr is finalized </lang> The memory allocated by new is freed when:

• the type of the pointer leaves the scope;
• the memory pool is finalized
• an instance of Ada.Unchecked_Deallocation is explicitly called on the pointer

<lang ada> declare

  type Integer_Ptr is access Integer;
  procedure Free is new Ada.Unchecked_Deallocation (Integer, Integer_Ptr)
  Ptr : Integer_Ptr := new Integer; -- Allocated in the heap

begin

  Free (Ptr); -- Explicit deallocation
  ...

end; </lang>

User pool

The allocator new also allocates memory in the user-defined storage pool when the pointer bound to the pool.

External memory

An object can be specified as allocated at the specific memory location, see machine address.

Implicit allocation

Elaboration of compilation units may result in allocation of the objects declared in these units. For example: <lang ada> package P is

  X : Integer; -- Allocated in the result the package elaboration

end P; </lang> The memory required by the object may be allocated statically or dynamically depending on the time of elaboration and its context. Objects declared in the library level packages are equivalent to what in some languages is called static object.

AutoHotkey

<lang AutoHotkey> VarSetCapacity(Var, 10240000)  ; allocate 10 megabytes VarSetCapacity(Var, 0)  ; free it </lang>

C

The functions malloc, calloc and realloc take memory from the heap. This memory should be released with free and it's suitable for sharing memory among threads.

<lang c>#include <stdlib.h>

/* size of "members", in bytes */

1. define SIZEOF_MEMB (sizeof(int))
2. define NMEMB 100

int main() {

 int *ints = (int *)malloc(SIZEOF_MEMB*NMEMB);
 /* realloc can be used to increase or decrease an already
    allocated memory (same as malloc if ints is NULL) */
 ints = (int *)realloc(ints, sizeof(int)*(NMEMB+1));
 /* calloc set the memory to 0s */
 int *int2 = (int *)calloc(NMEMB, SIZEOF_MEMB);
 /* all use the same free */
 free(ints); free(int2);
 return 0;

}</lang>

Variables declared inside a block (a function or inside a function) take room from the stack and survive until the "block" is in execution (and their scope is local).

<lang c>int func() {

 int ints[NMEMB]; /* it resembles calloc ... */
 int *int2;       /* here the only thing allocated on the stack is a pointer */
 char intstack[SIZEOF_MEMB*NMEMB]; /* to show resemblance to malloc */
 int2 = (int *)intstack;           /* but this is educative, do not do so unless... */

 {
   char *pointers_to_char[NMEMB];
   /* use pointers_to_char */
   pointers_to_char[0] = "educative";
 } /* outside the block, the variable "disappears" */

 /* here we can use ints, int2, intstack vars, which are not seen elsewhere of course */

 return 0;

}</lang>

Works with: gcc

The libc provided by gcc (and present on other "systems" too) has the alloca function which allows to ask for memory on the stack explicitly; the memory is deallocated when the function that asked for the memory ends (it is, in practice, the same behaviour for automatic variables). The usage is the same as for functions like malloc

<lang c>#include <alloca.h> int *funcA() {

 int *ints = (int *)alloca(SIZEOF_MEMB*NMEMB);
 ints[0] = 0;                                  /* use it */
 return ints; /* BUT THIS IS WRONG! It is not like malloc: the memory
                 does not "survive"! */

}</lang>

Variables declared outside any block and function or inside a function but prepended with the attribute static live as long as the program lives and the memory for them is statically given (e.g. through a .bss block).

<lang c>/* this is global */ int integers[NMEMB]; /* should be initialized with 0s */

int funcB() {

 static int ints[NMEMB]; /* this is "static", i.e. the memory "survive" even
                            when the function exits, but the symbol's scope is local */ 
 return integers[0] + ints[0];

}

void funcC(int a) {

 integers[0] = a;

}</lang>

C++

While the C allocation functions are also available in C++, their use is discouraged. Instead, C++ provides new and delete for memory allocation and deallocation. Those function don't just allocate memory, but also initialize objects. Also, deallocation is coupled with destruction. <lang cpp>

1. include <string>

int main() {

 int* p;

 p = new int;    // allocate a single int, uninitialized
 delete p;       // deallocate it

 p = new int(2); // allocate a single int, initialized with 2
 delete p;       // deallocate it

 std::string p2;

 p2 = new std::string; // allocate a single string, default-initialized
 delete p2;            // deallocate it

 p = new int[10]; // allocate an array of 10 ints, uninitialized
 delete[] p;      // deallocation of arrays must use delete[]

 p2 = new std::string[10]; // allocate an array of 10 strings, default-initialized
 delete[] p2;              // deallocate it

} </lang> Note that memory allocated with C allocation functions (malloc, calloc, <coderealloc) must always be deallocated with free, memory allocated with non-array new must always be deallocated with delete, and memory allocated with array new must always deallocated with delete[]. Memory allocated with new also cannot be resized with realloc.

Note that use of the array form is seldom a good idea; in most cases, using a standard container (esp. std::vector) is a better idea, because it manages the memory for you, it allows you to define an initial value to set in the array (new[] always default-initializes), and like malloc, but unlike array new, it allows resizing (and unlike realloc, it correctly handles construction/destruction when resizing).

Besides the new expressions shown above, pure memory allocation/deallocation without object initialization/destruction can also be done through operator new: <lang cpp> int main() {

 void* memory = operator new(20); // allocate 20 bytes of memory
 operator delete(memory);         // deallocate it

} </lang>

There's also a placement form of new, which allows to construct objects at an arbitrary adress (provided it is correctly aligned, and there's enough memory): <lang cpp>

1. include <new>

int main() {

 union
 {
   int alignment_dummy; // make sure the block is correctly aligned for ints
   char data[2*sizeof(int)]; // enough space for 10 ints
 };
 int* p = new(&data) int(3); // construct an int at the beginning of data
 new(p+1) int(5); // construct another int directly following

} </lang> Indeed, code like int* p = new int(3); is roughly (but not exactly) equivalent to the following sequence: <lang cpp> void* memory_for_p = operator new(sizeof(int)); int* p = new(memory_for_p) int(3); </lang>

Normally, new throws an exception if the allocation fails. there's a non-throwing variant which returns a null pointer instead: <lang cpp>

1. include <new>

int* p = new(std::nothrow) int(3); </lang> Note that the nothrow variant does not prevent any exceptions to be thrown from the constructor of an object created with new. It only prevents exceptions due to memory allocation failure.

It is also possible to implement user-defined variations of operator new. One possibility is to define class-based operator new/operator delete: <lang cpp>

1. include <cstddef>
2. include <cstdlib>
3. include <new>

class MyClass { public:

 void* operator new(std::size_t size)
 {
   void* p = std::malloc(size);
   if (!p) throw std::bad_alloc();
   return p;
 }
 void operator delete(void* p)
 {
   free(p);
 }

};

int main() {

 MyClass* p = new MyClass; // uses class specific operator new
 delete p;                 // uses class specific operator delete

 int* p2 = new int; // uses default operator new
 delete p2;         // uses default operator delete

} </lang>

Another possibility is to define new arguments for placement new syntax, e.g. <lang cpp> class arena { /* ... */ };

void* operator new(std::size_t size, arena& a) {

 return arena.alloc(size);

}

void operator delete(void* p, arena& a) {

 arena.dealloc(p);

}

arena whatever(/* ... */);

int* p = new(whatever) int(3); // uses operator new from above to allocate from the arena whatever </lang> Note that there is no placement delete syntax; the placement operator delete is invoked by the compiler only in case the constructor of the newed object throws. Therefore for placement newed object deletion the two steps must be done explicitly: <lang cpp> class MyClass { /*...*/ };

int main() {

 MyClass* p = new(whatever) MyClass; // allocate memory for myclass from arena and construct a MyClass object there
 // ...
 p->~MyClass(); // explicitly destruct *p
 operator delete(p, whatever); // explicitly deallocate the memory

} </lang>

E

E is a memory-safe language and does not generally work with explicit deallocation. As in Python and Java, you can create arrays of specific data types which will, by any decent implementation, be compactly represented.

<lang e>? <elib:tables.makeFlexList>.fromType(<type:java.lang.Byte>, 128)

1. value: [].diverge()</lang>

The above creates an array with an initial capacity of 128 bytes (1 kilobit) of storage (though it does not have any elements). (The Java type name is left-over from E's Java-scripting history and will eventually be deprecated in favor of a more appropriate name.) The array will be deallocated when there are no references to it.

Forth

Forth has two main bulk memory areas, each with their own word sets and semantics for allocation and deallocation.

Dictionary

All Forth implementations have a stack-like memory space called the dictionary. It is used both for code definitions and data structures. <lang forth> unused . \ memory available for use in dictionary here . \ current dictionary memory pointer

mem, ( addr len -- ) here over allot swap move ;

s, ( str len -- ) here over char+ allot place align ; \ built-in on some forths

," [char] " parse s, ;

variable num create array 60 cells allot create struct 0 , 10 , char A c, ," string" unused . here . </lang>

Dictionary space is meant for static code definitions and supporting data structures, so it is not as easy to deallocate from it. For ad-hoc allocations without intervening definitions, you may give a negative value to ALLOT to reclaim the space. You may also lay down a named MARKER to reclaim the space used by all subsequent definitions. <lang forth> marker foo

temp ... ;

create dummy 300 allot -150 allot \ trim the size of dummy by 150 bytes foo \ removes foo, temp, and dummy from the list of definitions </lang>

Heap

Most Forth implementations also give access to a larger random-access memory heap. <lang forth>

 4096 allocate throw  ( addr )
 dup 4096 erase
 ( addr ) free throw

</lang>

Java

You don't get much control over memory in Java, but here's what you can do: <lang java>//All of these objects will be deallocated automatically once the program leaves //their scope and there are no more pointers to the objects Object foo = new Object(); //Allocate an Object and a reference to it int[] fooArray = new int[size]; //Allocate all spaces in an array and a reference to it int x = 0; //Allocate an integer and set its value to 0 </lang> There is no real destructor in Java as there is in C++, but there is the finalize method. From the Java 6 JavaDocs:

The general contract of finalize is that it is invoked if and when the JavaTM virtual machine has determined that there is no longer any means by which this object can be accessed by any thread that has not yet died, except as a result of an action taken by the finalization of some other object or class which is ready to be finalized. The finalize method may take any action, including making this object available again to other threads; the usual purpose of finalize, however, is to perform cleanup actions before the object is irrevocably discarded. For example, the finalize method for an object that represents an input/output connection might perform explicit I/O transactions to break the connection before the object is permanently discarded. <lang java>public class Blah{

  //...other methods/data members...
  protected void finalize() throws Throwable{
     //Finalization code here
  }
  //...other methods/data members...

}</lang>

Oberon-2

TODO:

Python

Python has the array module: This module defines an object type which can compactly represent an array of basic values: characters, integers, floating point numbers. Arrays are sequence types and behave very much like lists, except that the type of objects stored in them is constrained. The type is specified at object creation time by using a type code, which is a single character. The following type codes are defined:

Type code	C Type	Python Type	Minimum size in bytes
'c'	char	character	1
'b'	signed char	int	1
'B'	unsigned char	int	1
'u'	Py_UNICODE	Unicode character	2
'h'	signed short	int	2
'H'	unsigned short	int	2
'i'	signed int	int	2
'I'	unsigned int	long	2
'l'	signed long	int	4
'L'	unsigned long	long	4
'f'	float	float	4
'd'	double	float	8

The actual representation of values is determined by the machine architecture (strictly speaking, by the C implementation). The actual size can be accessed through the itemsize attribute. The values stored for 'L' and 'I' items will be represented as Python long integers when retrieved, because Python’s plain integer type cannot represent the full range of C’s unsigned (long) integers.

Example <lang python>>>> from array import array >>> argslist = [('l', []), ('c', 'hello world'), ('u', u'hello \u2641'), ('l', [1, 2, 3, 4, 5]), ('d', [1.0, 2.0, 3.14])] >>> for typecode, initializer in argslist: a = array(typecode, initializer) print a del a

array('l') array('c', 'hello world') array('u', u'hello \u2641') array('l', [1, 2, 3, 4, 5]) array('d', [1.0, 2.0, 3.1400000000000001]) >>> </lang>

Tcl

Generally speaking you do not perform memory allocation directly in Tcl; scripts leave that under the control of the runtime (which manages the heap, threaded object pools and stacks automatically for you) and just work with values of arbitrary size. Indeed, the sizes of entities are not guaranteed in any case; the number of bytes per character or number does vary over time as the runtime selects the most efficient representation for it.

However the Machine Address task shows how you can do it directly if necessary. It just happens that it never actually is necessary to directly allocate memory in Tcl scripts in practice.

More commonly, a package written in C will be used to manage the memory on behalf of Tcl, with explicit memory management. Here is an example of such a package: <lang c>#include <tcl.h>

/* A data structure used to enforce data safety */ struct block {

   int size;
   unsigned char data[4];

};

static int Memalloc(

   ClientData clientData,
   Tcl_Interp *interp,
   int objc, Tcl_Obj *const *objv)

{

   Tcl_HashTable *nameMap = clientData;
   static int nameCounter = 0;
   char nameBuf[30];
   Tcl_HashEntry *hPtr;
   int size, dummy;
   struct block *blockPtr;

   /* Parse arguments */
   if (objc != 2) {

Tcl_WrongNumArgs(interp, 1, objv, "size"); return TCL_ERROR;

   }
   if (Tcl_GetIntFromObj(interp, objv[1], &size) != TCL_OK) {

return TCL_ERROR;

   }
   if (size < 1) {

Tcl_AppendResult(interp, "size must be positive", NULL); return TCL_ERROR;

   }

   /* The ckalloc() function will panic on failure to allocate. */
   blockPtr = (struct block *)

ckalloc(sizeof(struct block) + (unsigned) (size<4 ? 0 : size-4));

   /* Set up block */
   blockPtr->size = size;
   memset(blockPtr->data, 0, blockPtr->size);

   /* Give it a name and return the name */
   sprintf(nameBuf, "block%d", nameCounter++);
   hPtr = Tcl_CreateHashEntry(nameMap, nameBuf, &dummy);
   Tcl_SetHashValue(hPtr, blockPtr);
   Tcl_SetObjResult(interp, Tcl_NewStringObj(nameBuf, -1));
   return TCL_OK;

}

static int Memfree(

   ClientData clientData,
   Tcl_Interp *interp,
   int objc, Tcl_Obj *const *objv)

{

   Tcl_HashTable *nameMap = clientData;
   Tcl_HashEntry *hPtr;
   struct block *blockPtr;

   /* Parse the arguments */
   if (objc != 2) {

Tcl_WrongNumArgs(interp, 1, objv, "handle"); return TCL_ERROR;

   }
   hPtr = Tcl_FindHashEntry(nameMap, Tcl_GetString(objv[1]));
   if (hPtr == NULL) {

Tcl_AppendResult(interp, "unknown handle", NULL); return TCL_ERROR;

   }
   blockPtr = Tcl_GetHashValue(hPtr);

   /* Squelch the memory */
   Tcl_DeleteHashEntry(hPtr);
   ckfree((char *) blockPtr);
   return TCL_OK;

}

static int Memset(

   ClientData clientData,
   Tcl_Interp *interp,
   int objc, Tcl_Obj *const *objv)

{

   Tcl_HashTable *nameMap = clientData;
   Tcl_HashEntry *hPtr;
   struct block *blockPtr;
   int index, byte;

   /* Parse the arguments */
   if (objc != 4) {

Tcl_WrongNumArgs(interp, 1, objv, "handle index byte"); return TCL_ERROR;

   }
   hPtr = Tcl_FindHashEntry(nameMap, Tcl_GetString(objv[1]));
   if (hPtr == NULL) {

Tcl_AppendResult(interp, "unknown handle", NULL); return TCL_ERROR;

   }
   blockPtr = Tcl_GetHashValue(hPtr);
   if (Tcl_GetIntFromObj(interp, objv[2], &index) != TCL_OK

|| Tcl_GetIntFromObj(interp, objv[3], &byte) != TCL_OK) { return TCL_ERROR;

   }
   if (index < 0 || index >= blockPtr->size) {

Tcl_AppendResult(interp, "index out of range", NULL); return TCL_ERROR;

   }

   /* Update the byte of the data block */
   blockPtr->data[index] = (unsigned char) byte;
   return TCL_OK;

}

static int Memget(

   ClientData clientData,
   Tcl_Interp *interp,
   int objc, Tcl_Obj *const *objv)

{

   Tcl_HashTable *nameMap = clientData;
   Tcl_HashEntry *hPtr;
   struct block *blockPtr;
   int index, byte;

   /* Parse the arguments */
   if (objc != 3) {

Tcl_WrongNumArgs(interp, 1, objv, "handle index"); return TCL_ERROR;

   }
   hPtr = Tcl_FindHashEntry(nameMap, Tcl_GetString(objv[1]));
   if (hPtr == NULL) {

Tcl_AppendResult(interp, "unknown handle", NULL); return TCL_ERROR;

   }
   blockPtr = Tcl_GetHashValue(hPtr);
   if (Tcl_GetIntFromObj(interp, objv[2], &index) != TCL_OK) {

return TCL_ERROR;

   }
   if (index < 0 || index >= blockPtr->size) {

Tcl_AppendResult(interp, "index out of range", NULL); return TCL_ERROR;

   }

   /* Read the byte from the data block and return it */
   Tcl_SetObjResult(interp, Tcl_NewIntObj(blockPtr->data[index]));
   return TCL_OK;

}

static int Memaddr(

   ClientData clientData,
   Tcl_Interp *interp,
   int objc, Tcl_Obj *const *objv)

{

   Tcl_HashTable *nameMap = clientData;
   Tcl_HashEntry *hPtr;
   struct block *blockPtr;
   int addr;

   /* Parse the arguments */
   if (objc != 2) {

Tcl_WrongNumArgs(interp, 1, objv, "handle"); return TCL_ERROR;

   }
   hPtr = Tcl_FindHashEntry(nameMap, Tcl_GetString(objv[1]));
   if (hPtr == NULL) {

Tcl_AppendResult(interp, "unknown handle", NULL); return TCL_ERROR;

   }
   blockPtr = Tcl_GetHashValue(hPtr);

   /* This next line is non-portable */
   addr = (int) blockPtr->data;
   Tcl_SetObjResult(interp, Tcl_NewIntObj(addr));
   return TCL_OK;

}

int Memalloc_Init(Tcl_Interp *interp) {

   /* Make the hash table */
   Tcl_HashTable *hashPtr = (Tcl_HashTable *) ckalloc(sizeof(Tcl_HashTable));
   Tcl_InitHashTable(hashPtr, TCL_STRING_KEYS);

   /* Register the commands */
   Tcl_CreateObjCommand(interp, "memalloc", Memalloc, hashPtr, NULL);
   Tcl_CreateObjCommand(interp, "memfree", Memfree, hashPtr, NULL);
   Tcl_CreateObjCommand(interp, "memset", Memset, hashPtr, NULL);
   Tcl_CreateObjCommand(interp, "memget", Memget, hashPtr, NULL);
   Tcl_CreateObjCommand(interp, "memaddr", Memaddr, hashPtr, NULL);

   /* Register the package */
   return Tcl_PkgProvide(interp, "memalloc", "1.0");

}</lang> The package would then be used like this: <lang tcl>package require memalloc

set block [memalloc 1000] puts "allocated $block at [memaddr $block]" memset $block 42 79 someOtherCommand [memaddr $block] puts "$block\[42\] is now [memget $block 42]" memfree $block</lang> Other methods of performing things like memory allocation are also possible.

• Using string repeat or lrepeat to make a group of entities that work like a block of memory (despite not being); these need marshalling code to bridge to foreign function interfaces.
• Using SWIG or critcl to write a bridge to a standard C allocator.