heap.h

Go to the documentation of this file.

/*
    Copyright 2018, 2024 Joel Svensson        svenssonjoel@yahoo.se
 
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.
 
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
 
    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef HEAP_H_
#define HEAP_H_
 
#include <string.h>
#include <stdarg.h>
 
#include "lbm_types.h"
#include "symrepr.h"
#include "stack.h"
#include "lbm_memory.h"
#include "lbm_defines.h"
#include "lbm_channel.h"
 
#ifdef __cplusplus
extern "C" {
#endif
 
/*
Planning for a more space efficient heap representation.
TODO: Need to find a good reference to read up on this.
      - List based heap
      - Easy to implement and somewhat efficient
 
0000 0000  Size    Free bits
003F FFFF  4MB      10
007F FFFF  8MB       9
00FF FFFF  16MB      8
01FF FFFF  32MB      7
03FF FFFF  64MB      6         * Kind of heap size I am looking for
07FF FFFF  128MB     5
0FFF FFFF  256MB     4
1FFF FFFF  512MB     3
 
 
--- May 9 2021 ---
Actually now I am much more interested in way smaller memories ;)
 
0000 0000  Size    Free bits
0000 0FFF   4KB     20          |
0000 1FFF   8KB     19          |
0000 3FFF  16KB     18          |
0000 7FFF  32KB     17          |
0000 FFFF  64KB     16          |
0001 FFFF  128KB    15          |
0003 FFFF  256KB    14          | - This range is very interesting.
0007 FFFF  512KB    13
000F FFFF  1MB      12
001F FFFF  2MB      11
003F FFFF  4MB      10
007F FFFF  8MB       9
00FF FFFF  16MB      8
01FF FFFF  32MB      7
03FF FFFF  64MB      6
07FF FFFF  128MB     5
0FFF FFFF  256MB     4
1FFF FFFF  512MB     3
 
Those are the kind of platforms that are fun... so a bunch of
wasted bits in heap pointers if we run on small MCUs.
 
-----------------
 
it is also the case that not all addresses will be used if all "cells" are
of the same size, 8 bytes...
 
value 0: 0000 0000
value 1: 0000 0008
value 3: 0000 0010
value 4: 0000 0018
 
Means bits 0,1,2 will always be empty in a valid address.
 
Cons cells also need to be have room for 2 pointers. So each ted cell from
memory should be 8bytes.
 
Things that needs to be represented within these bits:
 
 - GC MARK one per cell
 - TYPE: type of CAR and type of cons
 
Types I would want:
 - Full 32bit integer. Does not leave room for identification of type
 - Float values.  Same problem
 
 
Free bits in pointers 64MB heap:
31 30 29 28 27 26                               2 1 0
0  0  0  0  0  0  XX XXXX XXXX XXXX XXXX XXXX X 0 0 0
 
 
Information needed for each cell:
 Meaning  |   bits total | bits per car | bits per cdr
 GC mark  |    2         |   1          |   1          - only one of them will be used (the other is wasted)   
 Type     |    2x        |   x          |   x
 Ptr/!ptr |    2         |   1          |   1
 
 
Types (unboxed):
 - Symbols
 - 28bit integer   ( will need signed shift right functionality )
 - 28bit unsigned integer
 - Character
 
If four types is all that should be possible (unboxed). then 2 bits are needed to differentiate.  
2 + 1 + 1 = 4 => 28bits for data.
 
bit 0: ptr/!ptr
bit 1: gc
bit 2-3: type (if not ptr)
bit 3 - 24 ptr (if ptr)
bit 4 - 31 value (if value)
 
An unboxed value can occupy a car or cdr field in a cons cell.
 
types (boxed) extra information in pointer to cell can contain information
 - 32 bit integer
 - 32 bit unsigned integer
 - 32 bit float
 
boxed representation:
  [ptr| cdr]
    |
  [Value | Aux + GC_MARK]
 
Kinds of pointers:
 - Pointer to cons cell.
 - Pointer to unboxed value  (fixnums not in a list, I hope this is so rare that it can be removed )  
   - integer
   - unsigned integer
   - symbol
   - float
 - Pointer to boxed value.
   - 32 bit integer
   - 32 bit unsigned integer
   - 32 bit float
 - (Maybe something else ? Vectors/strings allocated in memory not occupied by heap?)
   - vector of int
   - vector of uint
   - vector of float
   - vector of double
   - String
 
13 pointer"types" -> needs 4 bits
for 64MB heap there are 6 free bits. So with this scheme going to 128MB or 256MB heap 
is also possible
 
 a pointer to some off heap vector/string could be represented by
 
 [ptr | cdr]
   |
 [full pointer | Aux + GC_MARK]
   |
 [VECTOR]
 
Aux bits could be used for storing vector size. Up to 30bits should be available there
>> This is problematic. Now the information that something is a vector is split up 
>> between 2 cons cells. This means GC needs both of these intact to be able to make 
>> proper decision.
>> Will try to resolve this by adding some special symbols. But these must be symbols 
>> that cannot occur normally in programs. Then an array could be:
 
 [Full pointer | ARRAY_SYM + GC_MARK]
     |
 [VECTOR]
 
>> Boxed values same treatment as above.
>> TODO: Could this be simpler?
 
[ VALUE | TYPE_SYM + GC_MARK]
 
 
0000 00XX XXXX XXXX XXXX XXXX XXXX X000   : 0x03FF FFF8
1111 AA00 0000 0000 0000 0000 0000 0000   : 0xFC00 0000 (AA bits left unused for now, future heap growth?)
 */
 
typedef enum {
  LBM_FLASH_WRITE_OK,
  LBM_FLASH_FULL,
  LBM_FLASH_WRITE_ERROR
} lbm_flash_status;
 
typedef struct {
  lbm_value car;
  lbm_value cdr;
} lbm_cons_t;
 
typedef struct {
  lbm_cons_t *heap;
  lbm_value freelist;          // list of free cons cells.
  lbm_stack_t gc_stack;
 
  lbm_uint heap_size;          // In number of cells.
  lbm_uint heap_bytes;         // In bytes.
 
  lbm_uint num_alloc;          // Number of cells allocated.
  lbm_uint num_alloc_arrays;   // Number of arrays allocated.
 
  lbm_uint gc_num;             // Number of times gc has been performed.
  lbm_uint gc_marked;          // Number of cells marked by mark phase.
  lbm_uint gc_recovered;       // Number of cells recovered by sweep phase.
  lbm_uint gc_recovered_arrays;// Number of arrays recovered by sweep.
  lbm_uint gc_least_free;      // The smallest length of the freelist.
  lbm_uint gc_last_free;       // Number of elements on the freelist
                               // after most recent GC.
} lbm_heap_state_t;
 
extern lbm_heap_state_t lbm_heap_state;
 
  typedef bool (*const_heap_write_fun)(lbm_uint w, lbm_uint ix);
 
typedef struct {
  lbm_uint *heap;
  lbm_uint  next;  // next free index.
  lbm_uint  size;  // in lbm_uint words. (cons-cells = words / 2)
} lbm_const_heap_t;
 
typedef struct {
  lbm_uint size;            
  lbm_uint *data;           
} lbm_array_header_t;
 
typedef struct {
  lbm_uint size;
  lbm_uint *data;
  uint32_t index;         // Limits arrays to max 2^32-1 elements.
} lbm_array_header_extended_t;
 
void lbm_gc_lock(void);
/* Unlock GC mutex
 */
void lbm_gc_unlock(void);
 
int lbm_heap_init(lbm_cons_t *addr, lbm_uint num_cells,
                  lbm_uint gc_stack_size);
 
void lbm_heap_new_gc_time(lbm_uint dur);
void lbm_heap_new_freelist_length(void);
static inline lbm_uint lbm_heap_num_free(void) {
  return lbm_heap_state.heap_size - lbm_heap_state.num_alloc;
}
 
lbm_uint lbm_heap_num_allocated(void);
lbm_uint lbm_heap_size(void);
lbm_uint lbm_heap_size_bytes(void);
lbm_value lbm_heap_allocate_cell(lbm_type ptr_type, lbm_value car, lbm_value cdr);
lbm_value lbm_heap_allocate_list(lbm_uint n);
lbm_value lbm_heap_allocate_list_init_va(unsigned int n, va_list valist);
lbm_value lbm_heap_allocate_list_init(unsigned int n, ...);
char *lbm_dec_str(lbm_value val);
lbm_array_header_t *lbm_dec_array_r(lbm_value val);
lbm_array_header_t *lbm_dec_array_rw(lbm_value val);
lbm_array_header_t *lbm_dec_lisp_array_r(lbm_value val);
lbm_array_header_t *lbm_dec_lisp_array_rw(lbm_value val);
lbm_char_channel_t *lbm_dec_channel(lbm_value val);
lbm_uint lbm_dec_custom(lbm_value val);
uint8_t lbm_dec_as_char(lbm_value a);
uint32_t lbm_dec_as_u32(lbm_value val);
int32_t lbm_dec_as_i32(lbm_value val);
float lbm_dec_as_float(lbm_value val);
uint64_t lbm_dec_as_u64(lbm_value val);
int64_t lbm_dec_as_i64(lbm_value val);
double lbm_dec_as_double(lbm_value val);
 
lbm_uint lbm_dec_as_uint(lbm_value val);
 
lbm_int lbm_dec_as_int(lbm_value val);
 
lbm_uint lbm_dec_raw(lbm_value v);
lbm_value lbm_cons(lbm_value car, lbm_value cdr);
 
lbm_value lbm_car(lbm_value cons);
lbm_value lbm_caar(lbm_value c);
lbm_value lbm_cadr(lbm_value c);
lbm_value lbm_cdr(lbm_value cons);
lbm_value lbm_cddr(lbm_value c);
int lbm_set_car(lbm_value c, lbm_value v);
int lbm_set_cdr(lbm_value c, lbm_value v);
int lbm_set_car_and_cdr(lbm_value c, lbm_value car_val, lbm_value cdr_val);
// List functions
lbm_uint lbm_list_length(lbm_value c);
 
unsigned int lbm_list_length_pred(lbm_value c, bool *pres, bool (*pred)(lbm_value));
lbm_value lbm_list_reverse(lbm_value list);
lbm_value lbm_list_destructive_reverse(lbm_value list);
lbm_value lbm_list_copy(int *m, lbm_value list);
 
lbm_value lbm_list_append(lbm_value list1, lbm_value list2);
 
lbm_value lbm_list_drop(unsigned int n, lbm_value ls);
lbm_value lbm_index_list(lbm_value l, int32_t n);
 
// State and statistics
void lbm_get_heap_state(lbm_heap_state_t *);
lbm_uint lbm_get_gc_stack_max(void);
lbm_uint lbm_get_gc_stack_size(void);
// Garbage collection
void lbm_gc_state_inc(void);
void lbm_nil_freelist(void);
void lbm_gc_mark_env(lbm_value);
void lbm_gc_mark_phase(lbm_value root);
void lbm_gc_mark_aux(lbm_uint *data, lbm_uint n);
void lbm_gc_mark_roots(lbm_uint *roots, lbm_uint num_roots);
int lbm_gc_sweep_phase(void);
 
// Array functionality
int lbm_heap_allocate_array(lbm_value *res, lbm_uint size);
int lbm_heap_allocate_lisp_array(lbm_value *res, lbm_uint size);
int lbm_lift_array(lbm_value *value, char *data, lbm_uint num_elt);
lbm_int lbm_heap_array_get_size(lbm_value arr);
const uint8_t *lbm_heap_array_get_data_ro(lbm_value arr);
uint8_t *lbm_heap_array_get_data_rw(lbm_value arr);
int lbm_heap_explicit_free_array(lbm_value arr);
 
lbm_uint lbm_size_of(lbm_type t);
 
int lbm_const_heap_init(const_heap_write_fun w_fun,
                        lbm_const_heap_t *heap,
                        lbm_uint *addr);
 
lbm_flash_status lbm_allocate_const_cell(lbm_value *res);
lbm_flash_status lbm_write_const_raw(lbm_uint *data, lbm_uint n, lbm_uint *res);
lbm_flash_status lbm_allocate_const_raw(lbm_uint nwords, lbm_uint *res);
lbm_flash_status write_const_cdr(lbm_value cell, lbm_value val);
lbm_flash_status write_const_car(lbm_value cell, lbm_value val);
lbm_flash_status lbm_const_write(lbm_uint *tgt, lbm_uint val);
lbm_uint lbm_flash_memory_usage(void);
 
static inline lbm_type lbm_type_of(lbm_value x) {
  return (x & LBM_PTR_BIT) ? (x & LBM_PTR_TYPE_MASK) : (x & LBM_VAL_TYPE_MASK);
}
 
// type-of check that is safe in functional code
static inline lbm_type lbm_type_of_functional(lbm_value x) {
  return (x & LBM_PTR_BIT) ?
    (x & (LBM_PTR_TO_CONSTANT_MASK & LBM_PTR_TYPE_MASK)) :
     (x & LBM_VAL_TYPE_MASK);
}
 
static inline lbm_value lbm_enc_cons_ptr(lbm_uint x) {
  return ((x << LBM_ADDRESS_SHIFT) | LBM_TYPE_CONS | LBM_PTR_BIT);
}
 
static inline lbm_uint lbm_dec_ptr(lbm_value p) {
  return ((LBM_PTR_VAL_MASK & p) >> LBM_ADDRESS_SHIFT);
}
 
extern lbm_cons_t *lbm_heaps[2];
 
static inline lbm_uint lbm_dec_cons_cell_ptr(lbm_value p) {
  lbm_uint h = (p & LBM_PTR_TO_CONSTANT_BIT) >> LBM_PTR_TO_CONSTANT_SHIFT;
  return lbm_dec_ptr(p) >> h;
}
 
static inline lbm_cons_t *lbm_dec_heap(lbm_value p) {
  lbm_uint h = (p & LBM_PTR_TO_CONSTANT_BIT) >> LBM_PTR_TO_CONSTANT_SHIFT;
  return lbm_heaps[h];
}
 
static inline lbm_value lbm_set_ptr_type(lbm_value p, lbm_type t) {
  return ((LBM_PTR_VAL_MASK & p) | t | LBM_PTR_BIT);
}
 
static inline lbm_value lbm_enc_sym(lbm_uint s) {
  return (s << LBM_VAL_SHIFT) | LBM_TYPE_SYMBOL;
}
 
static inline lbm_value lbm_enc_i(lbm_int x) {
  return ((lbm_uint)x << LBM_VAL_SHIFT) | LBM_TYPE_I;
}
 
static inline lbm_value lbm_enc_u(lbm_uint x) {
  return (x << LBM_VAL_SHIFT) | LBM_TYPE_U;
}
 
extern lbm_value lbm_enc_i32(int32_t x);
 
extern lbm_value lbm_enc_u32(uint32_t x);
 
extern lbm_value lbm_enc_float(float x);
 
extern lbm_value lbm_enc_i64(int64_t x);
 
extern lbm_value lbm_enc_u64(uint64_t x);
 
extern lbm_value lbm_enc_double(double x);
 
static inline lbm_value lbm_enc_char(uint8_t x) {
  return ((lbm_uint)x << LBM_VAL_SHIFT) | LBM_TYPE_CHAR;
}
 
static inline lbm_int lbm_dec_i(lbm_value x) {
  return (lbm_int)x >> LBM_VAL_SHIFT;
}
 
static inline lbm_uint lbm_dec_u(lbm_value x) {
  return x >> LBM_VAL_SHIFT;
}
 
static inline uint8_t lbm_dec_char(lbm_value x) {
  return (uint8_t)(x >> LBM_VAL_SHIFT);
}
 
static inline lbm_uint lbm_dec_sym(lbm_value x) {
  return x >> LBM_VAL_SHIFT;
}
 
extern float lbm_dec_float(lbm_value x);
 
extern double lbm_dec_double(lbm_value x);
 
 
static inline uint32_t lbm_dec_u32(lbm_value x) {
#ifndef LBM64
  return (uint32_t)lbm_car(x);
#else
   return (uint32_t)(x >> LBM_VAL_SHIFT);
#endif
}
 
extern uint64_t lbm_dec_u64(lbm_value x);
 
static inline int32_t lbm_dec_i32(lbm_value x) {
#ifndef LBM64
  return (int32_t)lbm_car(x);
#else
  return (int32_t)(x >> LBM_VAL_SHIFT);
#endif
}
 
extern int64_t lbm_dec_i64(lbm_value x);
  
static inline bool lbm_is_ptr(lbm_value x) {
  return (x & LBM_PTR_BIT);
}
 
static inline bool lbm_is_constant(lbm_value x) {
  return ((x & LBM_PTR_BIT && x & LBM_PTR_TO_CONSTANT_BIT) ||
          (!(x & LBM_PTR_BIT)));
}
 
static inline bool lbm_is_cons_rw(lbm_value x) {
  return (lbm_type_of(x) == LBM_TYPE_CONS);
}
 
static inline bool lbm_is_cons(lbm_value x) {
  return lbm_is_ptr(x) && ((x & LBM_CONS_TYPE_MASK) == LBM_TYPE_CONS);
}
 
static inline bool lbm_is_symbol_nil(lbm_value exp) {
  return !exp;
}
  
static inline bool lbm_is_number(lbm_value x) {
  return
    (x & LBM_PTR_BIT) ?
    ((x & LBM_NUMBER_MASK) == LBM_NUMBER_MASK) :
    (x & LBM_VAL_TYPE_MASK);
}
 
// Check if an array is valid (an invalid array has been freed by someone explicitly)
static inline bool lbm_heap_array_valid(lbm_value arr) {
  return !(lbm_is_symbol_nil(lbm_car(arr))); // this is an is_zero check similar to (a == NULL)
}
 
static inline bool lbm_is_array_r(lbm_value x) {
  lbm_type t = lbm_type_of(x);
  return (((t & LBM_PTR_TO_CONSTANT_MASK) == LBM_TYPE_ARRAY) && lbm_heap_array_valid(x)) ;
}
 
static inline bool lbm_is_array_rw(lbm_value x) {
  return ((lbm_type_of(x) == LBM_TYPE_ARRAY) &&
          !(x & LBM_PTR_TO_CONSTANT_BIT) &&
          lbm_heap_array_valid(x));
}
 
static inline bool lbm_is_lisp_array_r(lbm_value x) {
  lbm_type t = lbm_type_of(x);
  return ((t & LBM_PTR_TO_CONSTANT_MASK) == LBM_TYPE_LISPARRAY);
}
 
static inline bool lbm_is_lisp_array_rw(lbm_value x) {
  return( (lbm_type_of(x) == LBM_TYPE_LISPARRAY) && !(x & LBM_PTR_TO_CONSTANT_BIT));
}
 
 
static inline bool lbm_is_channel(lbm_value x) {
  return (lbm_type_of(x) == LBM_TYPE_CHANNEL &&
          lbm_type_of(lbm_cdr(x)) == LBM_TYPE_SYMBOL &&
          lbm_cdr(x) == ENC_SYM_CHANNEL_TYPE);
}
static inline bool lbm_is_char(lbm_value x) {
  return (lbm_type_of(x) == LBM_TYPE_CHAR);
}
 
static inline bool lbm_is_special(lbm_value symrep) {
  return ((lbm_type_of(symrep) == LBM_TYPE_SYMBOL) &&
          (lbm_dec_sym(symrep) < SPECIAL_SYMBOLS_END));
}
 
static inline bool lbm_is_closure(lbm_value exp) {
  return ((lbm_is_cons(exp)) &&
          (lbm_type_of(lbm_car(exp)) == LBM_TYPE_SYMBOL) &&
          (lbm_car(exp) == ENC_SYM_CLOSURE));
}
 
static inline bool lbm_is_continuation(lbm_value exp) {
  return ((lbm_type_of(exp) == LBM_TYPE_CONS) &&
          (lbm_type_of(lbm_car(exp)) == LBM_TYPE_SYMBOL) &&
          (lbm_car(exp) == ENC_SYM_CONT));
}
 
static inline bool lbm_is_macro(lbm_value exp) {
  return ((lbm_type_of(exp) == LBM_TYPE_CONS) &&
          (lbm_type_of(lbm_car(exp)) == LBM_TYPE_SYMBOL) &&
          (lbm_car(exp) == ENC_SYM_MACRO));
}
 
static inline bool lbm_is_match_binder(lbm_value exp) {
  return (lbm_is_cons(exp) &&
          (lbm_type_of(lbm_car(exp)) == LBM_TYPE_SYMBOL) &&
          (lbm_car(exp) == ENC_SYM_MATCH_ANY));
}
 
static inline bool lbm_is_comma_qualified_symbol(lbm_value exp) {
  return (lbm_is_cons(exp) &&
          (lbm_type_of(lbm_car(exp)) == LBM_TYPE_SYMBOL) &&
          (lbm_car(exp) == ENC_SYM_COMMA) &&
          (lbm_type_of(lbm_cadr(exp)) == LBM_TYPE_SYMBOL));
}
 
static inline bool lbm_is_symbol(lbm_value exp) {
  return !(exp & LBM_LOW_RESERVED_BITS);
}
 
static inline bool lbm_is_symbol_true(lbm_value exp) {
  return (lbm_is_symbol(exp) && exp == ENC_SYM_TRUE);
}
 
static inline bool lbm_is_symbol_eval(lbm_value exp) {
  return (lbm_is_symbol(exp) && exp == ENC_SYM_EVAL);
}
 
static inline bool lbm_is_symbol_merror(lbm_value exp) {
  return lbm_is_symbol(exp) && (exp == ENC_SYM_MERROR);
}
 
static inline bool lbm_is_list(lbm_value x) {
  return (lbm_is_cons(x) || lbm_is_symbol_nil(x));
}
 
static inline bool lbm_is_list_rw(lbm_value x) {
  return (lbm_is_cons_rw(x) || lbm_is_symbol_nil(x));
}
 
static inline bool lbm_is_quoted_list(lbm_value x) {
  return (lbm_is_cons(x) &&
          lbm_is_symbol(lbm_car(x)) &&
          (lbm_car(x) == ENC_SYM_QUOTE) &&
          lbm_is_cons(lbm_cdr(x)) &&
          lbm_is_cons(lbm_cadr(x)));
}
 
#ifndef LBM64
#define ERROR_SYMBOL_MASK 0xFFFFFFF0
#else
#define ERROR_SYMBOL_MASK 0xFFFFFFFFFFFFFFF0
#endif
 
/* all error signaling symbols are in the range 0x20 - 0x2F */
static inline bool lbm_is_error(lbm_value v){
  return (lbm_is_symbol(v) &&
          ((lbm_dec_sym(v) & ERROR_SYMBOL_MASK) == 0x20));
}
 
// ref_cell: returns a reference to the cell addressed by bits 3 - 26
//           Assumes user has checked that is_ptr was set
static inline lbm_cons_t* lbm_ref_cell(lbm_value addr) {
  return &lbm_dec_heap(addr)[lbm_dec_cons_cell_ptr(addr)];
  //return &lbm_heap_state.heap[lbm_dec_ptr(addr)];
}
 
 
// lbm_uint a = lbm_heaps[0];
// lbm_uint b = lbm_heaps[1];
// lbm_uint i = (addr & LBM_PTR_TO_CONSTANT_BIT) >> LBM_PTR_TO_CONSTANT_SHIFT) - 1;
// lbm_uint h = (a & i) | (b & ~i);
 
#ifdef __cplusplus
}
#endif
#endif