MemoryManager

All-terrain Memory Allocator wanted !
It would benefit Orgams, IMPdraw2, AyAy Kpttn, etc, individually and for their cohabitation as well.

Guidelines

The memory manager should obey these good properties :

  1. Not intrusive : meta-data/housekeeping shouldn't be stuck to allocations themselves, to play well with alignment exigences. Also, it would allow allocation of contiguous 64k.
  2. Use pages backward (e.g. start with FC-FF if available instead of C4-C7) to minimize interference with programs using custom allocation scheme.
  3. But use bank 0 (e.g. FC if available, C4 for bare CPC 6128) for internal data, since bank 3 may be required by users for its connexion facilities;
  4. The routines shall not use base RAM (except by the stack, of course).
  5. Firmware friendly (no EXX/EX AF,AF').
  6. All-terrain (mustn't use firmware).
  7. Client code should be able to navigate in the allocation by itself, even if cross-banks (cf allocation type )
  8. Persistent across reset.
  9. House-Keeping data (allocation table etc) should be checked for coherence (checksum). Some soft will write in banks. We want to know if anything is corrupted.

Lexicon

Bank : 16k
Page : 64k
Warning ! It is the other way in SymbOS Doc.

Part : when an allocation is split across banks, we call 'Part' each slice.
       A part is at most 16k long.

AllocID : 16 bits identifier of an allocation. 0000 and 4000-7FFF are reserved.

 Rational :
  * 16 bits is easy to store and manipulate.
  * the number of allocations is limited anyway.
  * In case of reallocation, an ID stands still, whereas the start address of the allocation may change.
  * ID = Intelligent Design.
  * 0000 can be used as nul pointer.
  * 4000-7FFF can be used as direct pointers (cf mem_extend).

PartID : As an AllocID, but used for connecting a specific part. Cannot not be freed independently.
An AllocID *is* a PartID (i.e. it can be used whenever a PartID is required).

Addr32 : 32 bit addresses in external bank (No base RAM support needed).
     0000xxxx points in base RAM (not covered by these allocators).
     yyyyxxxx points address xxxx in page yyyy
E.g. 00016543 amounts to #2543 in #C5 bank connexion.
Cf connect_address for more insight.

Error codes
===========

01 ::Memory corruption. (The internal data has been overwritten)
02 : Memory full.
03 : Invalid alignment constraints.
04 : Unknown allocation type.
05 : Unknown AllocID.

Routines

We tag with [Optional] unneeded routines for a first working version.

+0 mem_initialise

Cold reset : Initialise the memory manager and sets up everything as it is when the computer is first switched on.

This routine shouldn't be called at ROM's initialisation, to preserve the allocated memory across resets (persistence).

In:  N/A
Out: AF, BC, DE, HL corrupted.

+3 mem_initialise_if_needed

Detect if memory manager is already installed.
If so:  run checksum and consistence checks. Call mem_initialise if corruption detected.
If not: call mem_initialise.

This is the routine meant to be called at ROM's initialisation.

Out: If manager was already there:
     If manager was there but corrupted:
     If manager was not found and has been initialized:

A, BC, DE, HL corrupted.

+6 reserved (for tests/hook purpose)

+9 mem_alloc

Allocate DEHL bytes, possibly split in several parts depending on type.
The contiguity is always ensure within each part.

The type represent increasing contiguity constraints :
* For big allocations, type 0 is the most likely to work, since it allows the allocator to use small free zones in arbitrary banks.
* With type 4, allocation is necessarily in one piece.

[Only type 4 shall be coded in first version]
 -------------------------------------------

Type 0 : no constraint, contiguity only assured within each bank.
            Beware, requesting e.g. 6k may gives two 3k parts living in distinct banks.
Type 1 : contiguity only assured within each page. Half-baked.
            The only additional guaranty is that each part (but the last) ends at an xxxxFFFF address.
Type 2 : full contiguity.
            I.e. Octet &7FFF in one bank is followed by octet &4000 in the subsequent bank.
            But still 6k may overlap 2 banks or even 2 pages.
Type 3: Fit in 64k. No page overlap. Thus, size is at most 64k.
Type 4: Fit in 16k. No bank overlap. Thus, size is at most 16k.
[ Type 7 (for a future version) : allocate in base RAM ]

To be clear, with type 0, 1 and 2, even if less than 16k is required, the allocation may be split across banks or even pages, requiring mem_connect_next_part to iterate through parts.
To ensure the whole allocation fit in one bank, use Type 4.

Whatever the type :
* each part (but the first) shall begin at #4000
* each part (but the last) shall end at #7FFF
in order to ease boundaries detection by client code.

In: A=type
    DEHL=size
Out: If ok, Carry is set, BC = AllocID. DEHL = Start Addr32.
     Else, NC. A = error code.

+C mem_alloc_fit_in_bank [Already coded]

Allocate BC contiguous bytes (no cross-bank).
This is a shortcut for mem_alloc with A=4, DE=0, HL=BC, and preserving DE & HL.

In: BC=size (necessarily less than 16k)
Out: As mem_alloc, except DE and HL are preserved.

+F mem_alloc_fit_in_page [Optional]

Allocate BC contiguous bytes (no cross-page).
This is a shortcut for mem_alloc with A=3, DE=0 (or 1 is BC=0), HL=BC, and preserving DE & HL.

In: BC=size (0=64k)
Out: As mem_alloc, except DE and HL are preserved.
[[/Code]]

+12 mem_alloc_aligned

Allocate BC contiguous bytes, at an address with same set bits than HL, and same reset bits than DE.

The motivations behind this routine is to allow to either :
* get allocation at XX00 address (great for tables).
* force a specific address : we don't care which page/bank it is, but we wish absolute address (e.g. for variables).
* reserve a whole bank.
* choose bank (e.g. bank 3, for its connection possibilities). That's more general than Symbos's "allocation type".

Example :
* HL=0000, DE=FF00  gives an XX00 address
* HL=DE             gives HL
* HL=0000, DE=C000, BC=4000 reserves a whole bank
* HL=C000, DE=FFFF  gives an address living in bank 3
* HL=0000, DE=FFFF  is identical to mem_alloc_in_bank (no constraint)
* HL=FFFF, DE=0000  returns error 02.

In:  A = type (cf mem_alloc). [Only type 4 must be supported for first version]
    BC = size (less than 16k)
    DE = AND mask
    HL = OR mask
Out: as mem_alloc

+15 mem_alloc_100

Short-cut for mem_alloc_aligned with BC = &100, DE = &FF00, HL = &0000

Motivation : gives a &100 chunk aligned at XX00 address.

In: Nothing
Out: as mem_alloc, except DE & HL are preserved.

+18 mem_alloc_nice_cut [optionnal]

Allocate a zone composed of the following chunks : 1 header and n slices.
The header might be empty.

The allocation may possibly be split across banks, but with the following guaranties :
* each chunk (header/slice) is in-bank contiguous.
* the chunk either ends at 7FFF, or is immediately followed by next chunk.

Motivation :
* allow bigger allocations
* no need to check end of bank while iterating the header or one slice.
* make end of part detection easy

In: A=type (cf mem_alloc)
    DEHL=size
    BC=header size
    IX=slices size
Out: as mem_alloc

+1B Reserved

+1E Reserved

+21 mem_extend

Extend a current allocation, and return a 16 bits pointer to the extension.
The extension itself is in-bank contiguous (type 4), but may not be stuck to the currently allocated zone.
It may even be in another bank, in which case it will be XX00 aligned.

Motivation : perfect for single-linked lists and rooted trees which may become bigger than 16k,
             when you don't have to free nodes separately.

In: DE = PartID  (the id of the part to be extended)
    BC = extension size (less than 16k)
Out: If ok, Carry is set and 
       DE = Plain address in bank (4000-FFFF) si extension resides in same bank than PartID.
       HL = Bank+MSB otherwise (see mem_convert_address_32_to_16)
     Otherwise, NC and A = error number.

+24 mem_free

Release the allocation.

In: BC = AllocID
Out: If ok, Carry is set.
     Otherwise, NC and A = error number.

+27 mem_connect_alloc

Connect the bank where the allocation resides, and return start address.

In: BC = AllocID
Out: If ok, Carry is set, the bank is connected (in #4000-#7FFF),
        HL = concrete address in bank
     Otherwise, NC and A = error number.

+2A mem_connect_address [Optionnal]

E.g.
00000000 : connect bank C4, return &4000 in HL
00018345 : connect bank CE, return &4345 in HL

In: DEHL = Addr32
Out: as mem_connect_alloc

+2D mem_connect_next_part [Optionnal]

With type 4 allocation obtained, the byte #7FFF in one bank is followed by byte #4000 in subsequent bank.
This is not true anymore with allocation through mem_alloc_nice_cut (due to other constaints to be respected).
In the latter case, this routine is the only way to connect the following part.

In: BC = current PartID
Out: as mem_connect_alloc

+30 mem_convert_addr32_to_word [Optionnal]

Convert an xxxxyyyy address to a word.
Actually the address must be 000xyy00 for this to work.
But it doesn't simply return 0xyy !
It returns the connection bank for the pal (e.g. #C4, #DC...) and the MSB of the address in the bank.

That's a convenient helper for fast access to the location.
NB: Since it presumes a 7Fxx IO address, it only works in the first 512k.

E.g.00018300 would return H = CE, L = 43

In: DEHL = Addr32
Out: If ok, Carry is set.
       L = bank to send to #7fxx port.
       H = MSB in bank (in #40-#7f range)
     Otherwise, NC and A = error number.

+33 mem_get_size [Optionnal]

Return the allocation size.

In: BC = AllocID
Out: If ok, Carry is set and DEHL = size.
     Otherwise, NC and A = error number.

+36 mem_detect_pages [Already coded]

Return number of additional pages. (E.g. 1 for stock 6128, 8 for 512 X-Mem).
Used internally to find highest bank available.

In: N/A
OUt: BC = number of additional pages.
[[/Code]]

+39 mem_get_error_message

Return error message corresponding to error number.

In: A = error number
    HL = 81-sized buffer.
Out: Buffer filled with error text, 0-terminated.

Code suggestions

No internal details have be given, on purpose.
Only the interface is important. The coder is free !

That being said, I've had enough metro journey to think about it, and I can share my views.

Let's call AllocInfo the structure describing one allocation.

An array of AllocInfo is better than a linked list (faster and shorter).
We still could use a linked list of freed allocations, reusing corresponding freed slots in the array. OvL! style.

AllocInfo structure
-------------------

Its ID = index in the array

This actually not describe the whole allocation, but each part residing in one bank. So :
* size is at most #4000
* the size of the whole allocation is obtained by iterating on each part.

+0   Byte  Allocation type
      00 = Free.
     Bits 1,0 (Private type)
      0 Free
      1 Alloc 1st part
      2 Alloc subsequent part
      3 Internal (cannot be released)
     Bits 4,3,2 (Alloc type)
      Cf mem_alloc
+1   Addr32 Start address
+5   Word   Size
+7   Word   ID of next part (or next free ID for type 00).
+9   Byte   Caller ROM (to track whose allocation it is)
+A   Word   Caller Address
+C   Word   Reserved [Could be next ID sorted by Start address]
+E   Word   Reserved

The array of AllocInfo is enough to infer the memory occupation map.
But for faster and simpler routines, I've though about a summary occupation map :

Occupation Map
--------------

Array of 1 byte per &100 chunk.
There are &100 of them for 64k, &800 for 512k.

Each byte indicate used bytes :
00 means free chunk
 x means chunk is occupied from 00 to X-1
FF means chunk is full
(If chunk is fully occupied except for its last byte, this is not codable : we pretend the full chunk is occupied).

E.g : If range #4000-#4083 of a given bank is used, #84 would be stored in the corresponding slot.
Warning ! If range #4000-#4030 of this same bank is freed, we must continue to pretend #84 bytes are used.

Once again, it's only a proposition :

Description of work bank
------------------------

#4000 STR  "Allocator" : Signature.
#4009 Byte Work Bank (e.g. #C7 for stock 6128, #FF with X-Mem)
#400A ...  Internal variables.

For 64k (stock CPC)
#4100-#77FF Free for users.
#7800-#7EFF AllocInfo array.
#7F00-#7FFF Occupation map.

For 512k

#4100-#77FF AllocInfo array.
#7800-#7FFF Occupation map.
Sauf mention contraire, le contenu de cette page est protégé par la licence Creative Commons Attribution-ShareAlike 3.0 License