dynamic-memory-here

Dynamic memory allocation in the data space region



dynamic-memory-here

Dynamic memory allocation in the data space region, using here and allot to allocate and free storage.

Jim Peterson <elkniwt@gmail.com>

Version 1.0.0 - 2021-05-04

In constrained systems, allocating a fixed-size heap for dynamic allocation which may or may not be completely used during run-time can be prohibitively expensive compared to using the existing data space memory managed by here and allot. This package creates the words malloc, mfree, mresize, and msize to create, delete, adjust, and query the size of dynamically allocated regions of memory in the data space region pointed to be here.

Dynamically allocated regions can become interleaved with other, traditionally-created regions within the data space, such as when calling allot, or general creating words. Although this may leave bubbles in the data space when freeing the dynamic regions, these holes will then be reallocated, when possible, with subsequent calls to malloc or mresize.

Installation

To use, just INCLUDE dynamic-memory-here.fs on any standard system.

Documentation

The following words are defined (other defined words, starting with a leading underscore, should be considered internal).

malloc ( size -- a-addr )

Allocate a memory region of the specified number of address units for use and return a pointer to the first address of that space, which will be cell-aligned. The allocated region from a-addr to a-addr + size - 1 is then available for the user to store data. Data within the allocated region has not been initialized.

mfree ( a-addr -- )

Free the space used by a previously allocated memory region.

mresize ( a-addr size -- a-addr' )

Resize the amount of space used by a previously allocated memory region. Its original bytes are moved to the new location given by the returned value of a-addr' (if, indeed, the location is even new), up to the minimum of size and the original size of the region at a-addr. If a-addr is 0, a new object is created (malloc is called). If size is 0, a-addr is freed (mfree is called) and 0 is returned.

msize ( a-addr -- size )

Get the number of address units allocated for this memory region. This is a courtesy function, since we have the information and the user may not wish to remember it manually.

A region address is only "valid" from the point in time when it has been returned from malloc or mresize until the point in time when it is passed to mfree or mresize. A region address that becomes "invalid" by being passed to mfree or mresize may become "valid" again by being returned at a later time from malloc or mresize. In some instances, mresize may return the same address that was passed into it (in fact, it strives to do so). In these instances, the region address remains "valid".

Do not pass an "invalid" region address to mfree or mresize (e.g., by passing the same address to mfree twice).

The behavior of malloc/mresize/mfree are meant to mimic that of the standard words allocate, resize and free with the exception that the guarantee of not changing the data space pointer is very much invalidated, and no ior codes are returned. Moreover, mresize is the only necessary word, given that it calls malloc or mfree when passed a 0 for a-addr or size.

User code could include:

[UNDEFINED] mresize [IF]

\ a one-stop shop of exception-throwing allocate/resize/free:
: mresize  ( a-addr1 u -- a-addr2 )
  over 0= if
    dup 0= if
      drop
    else
      nip allocate throw
    then
    exit
  then

  dup 0= if
    swap free throw
    exit
  then

  resize throw
;

[THEN]

and subsequently only use mresize in order to not only remain portable but also take advantage of this package when it exists. The above definition is also included in this package in the file mresize.fs.

Example Usage

Below is an example of use:

\ make an object and its "variable" storage:
variable pObj1
100 malloc pObj1 !  \ 100 address units have been allocated at 'here'

\ make a second "variable":
variable pObj2

\ define some words to dump state:
: dd dup . ." -> " @ . cr ;
: d(
  cr postpone .( cr
  base @ hex
  ." pObj1: @" pObj1 dd
  ." pObj2: @" pObj2 dd
  ."  here: @" here . cr
  ." bubbles:" cr
  _bub_list
  begin
    @ dup
  while
    dup . ." -> " dup cell+ @ . cr
  repeat
  drop
  base !
;
d( Allocated Obj1: )

At this point, data space storage for the variable pObj2, as well as definitions for the debug words, dd and d, likely come after the space that had been allocated by the call to malloc. When pObj1 is moved or freed, there will be a "bubble" in the data space of more than 100 address units. This is fine, it is remembered and can be reused later.

\ space for Obj2:
200 malloc pObj2 !
d( Allocated Obj2: )

\ grow Obj1
pObj1 @ 200 mresize pObj1 !
d( Grew Obj1: )

\ shrink Obj2
pObj2 @ 50  mresize pObj2 !
d( Shrank Obj2: )

\ free the second (and forget its pointer)
pObj2 @ mfree
0 pObj2 !
d( Freed Obj2: )

\ free the first (again, forgetting)
pObj1 @ mfree
0 pObj1 !

The output from the debugging printouts made with d(, when running the above in gforth, are as follows:

Allocated Obj1: 
pObj1: @7F3D0212D8B0 -> 7F3D0212D8C0 
pObj2: @7F3D0212D950 -> 0 
 here: @7F3D0212DD30 
bubbles:

Allocated Obj2: 
pObj1: @7F3D0212D8B0 -> 7F3D0212D8C0 
pObj2: @7F3D0212D950 -> 7F3D0212DD38 
 here: @7F3D0212DE00 
bubbles:

Grew Obj1: 
pObj1: @7F3D0212D8B0 -> 7F3D0212DE08 
pObj2: @7F3D0212D950 -> 7F3D0212DD38 
 here: @7F3D0212DED0 
bubbles:
7F3D0212D8B8 -> 7F3D0212D928 

Shrank Obj2: 
pObj1: @7F3D0212D8B0 -> 7F3D0212DE08 
pObj2: @7F3D0212D950 -> 7F3D0212DD38 
 here: @7F3D0212DED0 
bubbles:
7F3D0212D8B8 -> 7F3D0212D928 
7F3D0212DD70 -> 7F3D0212DE00 

Freed Obj2: 
pObj1: @7F3D0212D8B0 -> 7F3D0212DE08 
pObj2: @7F3D0212D950 -> 0 
 here: @7F3D0212DED0 
bubbles:
7F3D0212D8B8 -> 7F3D0212D928 
7F3D0212DD30 -> 7F3D0212DE00 

Freed Obj1: 
pObj1: @7F3D0212D8B0 -> 0 
pObj2: @7F3D0212D950 -> 0 
 here: @7F3D0212DD30 
bubbles:
7F3D0212D8B8 -> 7F3D0212D928 

Notice, when Obj1 grows, it leapfrogs Obj2, going from xxx8C0 to xxxE08, creating a bubble where it once was. When Obj2 is then shrunk, it does so in-place, making a second bubble past its new end. Meanwhile, here goes from xxxD30 to xxxE00 and then to xxxED0, but in the end, once both objects are freed, it drops back down to its original xxxD30. If any more space had been allocated with allot or other word creation, here would not have been able to drop back down, and more memory space bubbles would be remembered and reused much like the space between xxx8B8 and xxx928. This example code is included in example.fs.

Bug Reports

Please send bug reports, improvements and suggestions to Jim Peterson <elkniwt@gmail.com>

Conformance

This program conforms to Forth-94 and Forth-2012.

References

(I blatantly copied Ulrich Hoffmann's README.md format for this.)

May the Forth be with you, as well!

by JimPeterson

avatar of JimPeterson

Versions

1.0.0

Download current as zip

Tags

forth-2012, memory, allocation

Dependencies

None

Dependents

None