Head

GCC Code Coverage Report

Directory:	../src/		Exec	Total	Coverage
File:	/home/joels/Current/lispbm/src/lbm_defrag_mem.c	Lines:	124	126	98.4 %
Date:	2024-12-05 14:36:58	Branches:	41	49	83.7 %


/*
    Copyright 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/>.
*/

#include <lbm_defrag_mem.h>
#include <heap.h>
#include <lbm_memory.h>

static inline lbm_uint bs2ws(lbm_uint bs) {
  return bs % sizeof(lbm_uint) == 0 ? bs / sizeof(lbm_uint) : (bs / sizeof(lbm_uint)) + 1;
}

#define DEFRAG_MEM_HEADER_SIZE 2
#define DEFRAG_MEM_HEADER_BYTES  (2*sizeof(lbm_uint))
#define DEFRAG_MEM_DATA(X) &(X)[DEFRAG_MEM_HEADER_SIZE];
// length and flags.
// Currently only one flag that tells if we should do a compaction before allocation.
#define DEFRAG_MEM_SIZE(X) X[0]
#define DEFRAG_MEM_FLAGS(X) X[1]

#define DEFRAG_ALLOC_SIZE(X) X[0]
#define DEFRAG_ALLOC_DATA(X) X[1]
#define DEFRAG_ALLOC_CELLPTR(X) X[2]

lbm_value lbm_defrag_mem_create(lbm_uint nbytes) {
  lbm_value res = ENC_SYM_TERROR;
  lbm_uint nwords = bs2ws(nbytes); // multiple of 4.
  if (nwords > 0) {
    res = ENC_SYM_MERROR;
    lbm_uint *data = (lbm_uint*)lbm_malloc(DEFRAG_MEM_HEADER_BYTES + nwords * sizeof(lbm_uint));
    if (data) {
      memset((uint8_t*)data , 0, DEFRAG_MEM_HEADER_BYTES + nwords*sizeof(lbm_uint));
      data[0] = nwords;
      data[1] = 0;      //flags
      lbm_value cell = lbm_heap_allocate_cell(LBM_TYPE_DEFRAG_MEM, (lbm_uint)data, ENC_SYM_DEFRAG_MEM_TYPE);
      if (cell == ENC_SYM_MERROR) {
        lbm_free(data);
      } else {
        res = cell;
      }
    }
  }
  return res;
}

static void free_defrag_allocation(lbm_uint *allocation) {
  lbm_uint size = DEFRAG_ALLOC_SIZE(allocation); // array allocation is size in bytes
  // a defrag-mem allocation is always bigger than 0
  lbm_uint nwords = bs2ws(size) + 3;
  lbm_value cell_back_ptr = DEFRAG_ALLOC_CELLPTR(allocation);

  // I have a feeling that it should be impossible for the
  // cell to be recovered if we end up here.
  // if the cell is recovered, then the data should also have been
  // cleared in the defrag_mem.

  cell_back_ptr = lbm_set_ptr_type(cell_back_ptr, LBM_TYPE_CONS);
  bool marked = lbm_cdr(cell_back_ptr) & LBM_GC_MASK;
  lbm_value new_cdr = marked ? (ENC_SYM_NIL | LBM_GC_MARKED) : ENC_SYM_NIL;
  lbm_set_car_and_cdr(cell_back_ptr, ENC_SYM_NIL, new_cdr);
  // possible optimize, if not marked. dont bother setting anything.

  for (lbm_uint i = 0; i < nwords; i ++) {
    allocation[i] = 0;
  }
}

// Called by GC.
// As it is called by GC, gc bits may be set and needs to be
// honored!
void lbm_defrag_mem_destroy(lbm_uint *defrag_mem) {
  lbm_uint nwords = DEFRAG_MEM_SIZE(defrag_mem);
  lbm_uint *defrag_data = DEFRAG_MEM_DATA(defrag_mem);
  for (lbm_uint i = 0; i < nwords;) {
    lbm_uint a = defrag_data[i];
    if (a != 0) {
      lbm_uint *allocation = &defrag_data[i];
      lbm_uint alloc_words = 3 + bs2ws(DEFRAG_ALLOC_SIZE(allocation));
      free_defrag_allocation(allocation);
      i += alloc_words;
    }
    else i ++;
  }
  lbm_free(defrag_mem);
}


static void lbm_defrag_mem_defrag(lbm_uint *defrag_mem, lbm_uint bytes) {
  lbm_uint mem_size = ((lbm_uint*)defrag_mem)[0]; // mem size words
  lbm_uint *mem_data = DEFRAG_MEM_DATA(defrag_mem);
  lbm_uint hole_start = 0;

  lbm_uint until_size = bs2ws(bytes) + 3; // defrag until hole is this size or complete defrag.

  for (lbm_uint i = 0; i < mem_size; ) {
    // check if there is an allocation here
    if (mem_data[i] != 0) {
      lbm_uint *source = &mem_data[i];
      lbm_uint *target = &mem_data[hole_start];
      lbm_uint alloc_bytes = DEFRAG_ALLOC_SIZE(source);
      lbm_uint alloc_words = bs2ws(alloc_bytes);
      // move allocation into hole
      if (hole_start == i) {
        i += alloc_words+3;
        hole_start = i;
      } else {
        lbm_uint move_dist = i - hole_start;
        if (move_dist >= until_size) break;
        lbm_uint clear_ix = (hole_start + alloc_words + 3);
        memmove(target, source, (alloc_words + 3) * sizeof(lbm_uint));
        memset(&mem_data[clear_ix],0, move_dist* sizeof(lbm_uint));
        DEFRAG_ALLOC_DATA(target) = (lbm_uint)&target[3];
        lbm_value cell = DEFRAG_ALLOC_CELLPTR(target);

        lbm_set_car(cell,(lbm_uint)target);
        // move home and i forwards.
        // i can move to the original end of allocation.
        hole_start += alloc_words + 3;
        i += alloc_words + 3;
      }
    } else {
      // no allocation hole remains but i increments.
      i ++;
    }
  }
}

// Allocate an array from the defragable pool
// these arrays must be recognizable by GC so that
// gc can free them by performing a call into the defrag_mem api.
// At the same time they need to be just bytearrays..
// Allocation must always scan from start.
//

#define INIT 0
#define FREE_LEN 1

// An array allocated in defragmem has the following layout inside of the defrag mem
//
// [header (size, data-ptr) cell_back_ptr | data | padding ]

lbm_value lbm_defrag_mem_alloc_internal(lbm_uint *defrag_mem, lbm_uint bytes) {

  if (bytes == 0) return ENC_SYM_EERROR;
  lbm_value cell = lbm_heap_allocate_cell(LBM_TYPE_CONS, ENC_SYM_NIL, ENC_SYM_DEFRAG_ARRAY_TYPE);

  if (cell == ENC_SYM_MERROR) {
    return cell;
  }

  lbm_uint mem_size = DEFRAG_MEM_SIZE(defrag_mem);
  lbm_uint *mem_data = DEFRAG_MEM_DATA(defrag_mem);

  lbm_uint num_words = bs2ws(bytes);
  lbm_uint alloc_words = num_words + 3;

  uint8_t state = INIT;
  lbm_uint free_words = 0;
  lbm_uint free_start = 0;
  bool alloc_found = false;
  lbm_value res = ENC_SYM_MERROR;

  for (lbm_uint i = 0; i < mem_size;) {
    switch(state) {
    case INIT:
      if (mem_data[i] == 0) {
        free_start = i;
        free_words = 1;
        state = FREE_LEN;
        i++;
      } else {
        // jump to next spot
        i += bs2ws(mem_data[i]) + 3;
      }
      break;
    case FREE_LEN:
      if (mem_data[i] == 0) {
        free_words ++;
        if (free_words >= alloc_words) {
          alloc_found = true;
        } else {
          i ++;
        }
      } else {
        state = INIT;
        i++;
      }
      break;
    }
    if (alloc_found) break;
  }
  if (alloc_found) {
    lbm_uint *allocation = (lbm_uint*)&mem_data[free_start];
    DEFRAG_ALLOC_SIZE(allocation) = bytes;
    DEFRAG_ALLOC_DATA(allocation) = (lbm_uint)&allocation[3]; //data starts after back_ptr
    DEFRAG_ALLOC_CELLPTR(allocation) = cell;
    lbm_set_car(cell, (lbm_uint)allocation);
    cell = lbm_set_ptr_type(cell, LBM_TYPE_ARRAY);
    res = cell;
  } else {
    DEFRAG_MEM_FLAGS(defrag_mem) = 1;
    lbm_set_car_and_cdr(cell, ENC_SYM_NIL, ENC_SYM_NIL);
  }
  return res;
}

lbm_value lbm_defrag_mem_alloc(lbm_uint *defrag_mem, lbm_uint bytes) {

  lbm_value res = lbm_defrag_mem_alloc_internal(defrag_mem, bytes); // Try to allocate
  if (lbm_is_symbol_merror(res)) {
    if (DEFRAG_MEM_FLAGS(defrag_mem)) { //if we already performed GC, then also defrag
      lbm_defrag_mem_defrag(defrag_mem, bytes);
      res = lbm_defrag_mem_alloc_internal(defrag_mem, bytes); // then try again
      DEFRAG_MEM_FLAGS(defrag_mem) = 0;
    }
  }
  return res;
}


// IF GC frees a defrag allocation, the cell pointing to it will also be destroyed by GC.

// is it guaranteed there are no copies of a heap-cell representing a defrag allocation.
// Same guarantee must hold for arrays in general or it would not be possible to explicitly free
// any array.

// At the time of free from GC all we have is the pointer.
void lbm_defrag_mem_free(lbm_uint* data) {
  lbm_uint nbytes = data[0];
  lbm_uint words_to_wipe = 3 + bs2ws(nbytes);
  for (lbm_uint i = 0; i < words_to_wipe; i ++) {
    data[i] = 0;
  }
}



Generated by: GCOVR (Version 4.2)

Line	Branch	Exec	Source
1			/*
2			Copyright 2024 Joel Svensson svenssonjoel@yahoo.se
3
4			This program is free software: you can redistribute it and/or modify
5			it under the terms of the GNU General Public License as published by
6			the Free Software Foundation, either version 3 of the License, or
7			(at your option) any later version.
8
9			This program is distributed in the hope that it will be useful,
10			but WITHOUT ANY WARRANTY; without even the implied warranty of
11			MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12			GNU General Public License for more details.
13
14			You should have received a copy of the GNU General Public License
15			along with this program. If not, see <http://www.gnu.org/licenses/>.
16			*/
17
18			#include <lbm_defrag_mem.h>
19			#include <heap.h>
20			#include <lbm_memory.h>
21
22		17668	static inline lbm_uint bs2ws(lbm_uint bs) {
23	✓✓	17668	return bs % sizeof(lbm_uint) == 0 ? bs / sizeof(lbm_uint) : (bs / sizeof(lbm_uint)) + 1;
24			}
25
26			#define DEFRAG_MEM_HEADER_SIZE 2
27			#define DEFRAG_MEM_HEADER_BYTES (2*sizeof(lbm_uint))
28			#define DEFRAG_MEM_DATA(X) &(X)[DEFRAG_MEM_HEADER_SIZE];
29			// length and flags.
30			// Currently only one flag that tells if we should do a compaction before allocation.
31			#define DEFRAG_MEM_SIZE(X) X[0]
32			#define DEFRAG_MEM_FLAGS(X) X[1]
33
34			#define DEFRAG_ALLOC_SIZE(X) X[0]
35			#define DEFRAG_ALLOC_DATA(X) X[1]
36			#define DEFRAG_ALLOC_CELLPTR(X) X[2]
37
38		140	lbm_value lbm_defrag_mem_create(lbm_uint nbytes) {
39		140	lbm_value res = ENC_SYM_TERROR;
40		140	lbm_uint nwords = bs2ws(nbytes); // multiple of 4.
41	✓✗	140	if (nwords > 0) {
42		140	res = ENC_SYM_MERROR;
43		140	lbm_uint data = (lbm_uint)lbm_malloc(DEFRAG_MEM_HEADER_BYTES + nwords * sizeof(lbm_uint));
44	✓✗	140	if (data) {
45		140	memset((uint8_t)data , 0, DEFRAG_MEM_HEADER_BYTES + nwordssizeof(lbm_uint));
46		140	data[0] = nwords;
47		140	data[1] = 0; //flags
48		140	lbm_value cell = lbm_heap_allocate_cell(LBM_TYPE_DEFRAG_MEM, (lbm_uint)data, ENC_SYM_DEFRAG_MEM_TYPE);
49	✗✓	140	if (cell == ENC_SYM_MERROR) {
50			lbm_free(data);
51			} else {
52		140	res = cell;
53			}
54			}
55			}
56		140	return res;
57			}
58
59		84	static void free_defrag_allocation(lbm_uint *allocation) {
60		84	lbm_uint size = DEFRAG_ALLOC_SIZE(allocation); // array allocation is size in bytes
61			// a defrag-mem allocation is always bigger than 0
62		84	lbm_uint nwords = bs2ws(size) + 3;
63		84	lbm_value cell_back_ptr = DEFRAG_ALLOC_CELLPTR(allocation);
64
65			// I have a feeling that it should be impossible for the
66			// cell to be recovered if we end up here.
67			// if the cell is recovered, then the data should also have been
68			// cleared in the defrag_mem.
69
70		84	cell_back_ptr = lbm_set_ptr_type(cell_back_ptr, LBM_TYPE_CONS);
71		84	bool marked = lbm_cdr(cell_back_ptr) & LBM_GC_MASK;
72	✓✗	84	lbm_value new_cdr = marked ? (ENC_SYM_NIL \| LBM_GC_MARKED) : ENC_SYM_NIL;
73		84	lbm_set_car_and_cdr(cell_back_ptr, ENC_SYM_NIL, new_cdr);
74			// possible optimize, if not marked. dont bother setting anything.
75
76	✓✓	588	for (lbm_uint i = 0; i < nwords; i ++) {
77		504	allocation[i] = 0;
78			}
79		84	}
80
81			// Called by GC.
82			// As it is called by GC, gc bits may be set and needs to be
83			// honored!
84		28	void lbm_defrag_mem_destroy(lbm_uint *defrag_mem) {
85		28	lbm_uint nwords = DEFRAG_MEM_SIZE(defrag_mem);
86		28	lbm_uint *defrag_data = DEFRAG_MEM_DATA(defrag_mem);
87	✓✓	308	for (lbm_uint i = 0; i < nwords;) {
88		280	lbm_uint a = defrag_data[i];
89	✓✓	280	if (a != 0) {
90		84	lbm_uint *allocation = &defrag_data[i];
91		84	lbm_uint alloc_words = 3 + bs2ws(DEFRAG_ALLOC_SIZE(allocation));
92		84	free_defrag_allocation(allocation);
93		84	i += alloc_words;
94			}
95		196	else i ++;
96			}
97		28	lbm_free(defrag_mem);
98		28	}
99
100
101		616	static void lbm_defrag_mem_defrag(lbm_uint *defrag_mem, lbm_uint bytes) {
102		616	lbm_uint mem_size = ((lbm_uint*)defrag_mem)[0]; // mem size words
103		616	lbm_uint *mem_data = DEFRAG_MEM_DATA(defrag_mem);
104		616	lbm_uint hole_start = 0;
105
106		616	lbm_uint until_size = bs2ws(bytes) + 3; // defrag until hole is this size or complete defrag.
107
108	✓✓	7504	for (lbm_uint i = 0; i < mem_size; ) {
109			// check if there is an allocation here
110	✓✓	6916	if (mem_data[i] != 0) {
111		2828	lbm_uint *source = &mem_data[i];
112		2828	lbm_uint *target = &mem_data[hole_start];
113		2828	lbm_uint alloc_bytes = DEFRAG_ALLOC_SIZE(source);
114		2828	lbm_uint alloc_words = bs2ws(alloc_bytes);
115			// move allocation into hole
116	✓✓	2828	if (hole_start == i) {
117		2604	i += alloc_words+3;
118		2604	hole_start = i;
119			} else {
120		224	lbm_uint move_dist = i - hole_start;
121	✓✓	224	if (move_dist >= until_size) break;
122		196	lbm_uint clear_ix = (hole_start + alloc_words + 3);
123		196	memmove(target, source, (alloc_words + 3) * sizeof(lbm_uint));
124		196	memset(&mem_data[clear_ix],0, move_dist* sizeof(lbm_uint));
125		196	DEFRAG_ALLOC_DATA(target) = (lbm_uint)&target[3];
126		196	lbm_value cell = DEFRAG_ALLOC_CELLPTR(target);
127
128		196	lbm_set_car(cell,(lbm_uint)target);
129			// move home and i forwards.
130			// i can move to the original end of allocation.
131		196	hole_start += alloc_words + 3;
132		196	i += alloc_words + 3;
133			}
134			} else {
135			// no allocation hole remains but i increments.
136		4088	i ++;
137			}
138			}
139		616	}
140
141			// Allocate an array from the defragable pool
142			// these arrays must be recognizable by GC so that
143			// gc can free them by performing a call into the defrag_mem api.
144			// At the same time they need to be just bytearrays..
145			// Allocation must always scan from start.
146			//
147
148			#define INIT 0
149			#define FREE_LEN 1
150
151			// An array allocated in defragmem has the following layout inside of the defrag mem
152			//
153			// [header (size, data-ptr) cell_back_ptr \| data \| padding ]
154
155		2800	lbm_value lbm_defrag_mem_alloc_internal(lbm_uint *defrag_mem, lbm_uint bytes) {
156
157	✗✓	2800	if (bytes == 0) return ENC_SYM_EERROR;
158		2800	lbm_value cell = lbm_heap_allocate_cell(LBM_TYPE_CONS, ENC_SYM_NIL, ENC_SYM_DEFRAG_ARRAY_TYPE);
159
160	✗✓	2800	if (cell == ENC_SYM_MERROR) {
161			return cell;
162			}
163
164		2800	lbm_uint mem_size = DEFRAG_MEM_SIZE(defrag_mem);
165		2800	lbm_uint *mem_data = DEFRAG_MEM_DATA(defrag_mem);
166
167		2800	lbm_uint num_words = bs2ws(bytes);
168		2800	lbm_uint alloc_words = num_words + 3;
169
170		2800	uint8_t state = INIT;
171		2800	lbm_uint free_words = 0;
172		2800	lbm_uint free_start = 0;
173		2800	bool alloc_found = false;
174		2800	lbm_value res = ENC_SYM_MERROR;
175
176	✓✓	31668	for (lbm_uint i = 0; i < mem_size;) {
177	✓✓✗	30492	switch(state) {
178		12880	case INIT:
179	✓✓	12880	if (mem_data[i] == 0) {
180		2800	free_start = i;
181		2800	free_words = 1;
182		2800	state = FREE_LEN;
183		2800	i++;
184			} else {
185			// jump to next spot
186		10080	i += bs2ws(mem_data[i]) + 3;
187			}
188		12880	break;
189		17612	case FREE_LEN:
190	✓✓	17612	if (mem_data[i] == 0) {
191		17528	free_words ++;
192	✓✓	17528	if (free_words >= alloc_words) {
193		1624	alloc_found = true;
194			} else {
195		15904	i ++;
196			}
197			} else {
198		84	state = INIT;
199		84	i++;
200			}
201		17612	break;
202			}
203	✓✓	30492	if (alloc_found) break;
204			}
205	✓✓	2800	if (alloc_found) {
206		1624	lbm_uint allocation = (lbm_uint)&mem_data[free_start];
207		1624	DEFRAG_ALLOC_SIZE(allocation) = bytes;
208		1624	DEFRAG_ALLOC_DATA(allocation) = (lbm_uint)&allocation[3]; //data starts after back_ptr
209		1624	DEFRAG_ALLOC_CELLPTR(allocation) = cell;
210		1624	lbm_set_car(cell, (lbm_uint)allocation);
211		1624	cell = lbm_set_ptr_type(cell, LBM_TYPE_ARRAY);
212		1624	res = cell;
213			} else {
214		1176	DEFRAG_MEM_FLAGS(defrag_mem) = 1;
215		1176	lbm_set_car_and_cdr(cell, ENC_SYM_NIL, ENC_SYM_NIL);
216			}
217		2800	return res;
218			}
219
220		2184	lbm_value lbm_defrag_mem_alloc(lbm_uint *defrag_mem, lbm_uint bytes) {
221
222		2184	lbm_value res = lbm_defrag_mem_alloc_internal(defrag_mem, bytes); // Try to allocate
223	✓✓	2184	if (lbm_is_symbol_merror(res)) {
224	✓✗	616	if (DEFRAG_MEM_FLAGS(defrag_mem)) { //if we already performed GC, then also defrag
225		616	lbm_defrag_mem_defrag(defrag_mem, bytes);
226		616	res = lbm_defrag_mem_alloc_internal(defrag_mem, bytes); // then try again
227		616	DEFRAG_MEM_FLAGS(defrag_mem) = 0;
228			}
229			}
230		2184	return res;
231			}
232
233
234			// IF GC frees a defrag allocation, the cell pointing to it will also be destroyed by GC.
235
236			// is it guaranteed there are no copies of a heap-cell representing a defrag allocation.
237			// Same guarantee must hold for arrays in general or it would not be possible to explicitly free
238			// any array.
239
240			// At the time of free from GC all we have is the pointer.
241		1036	void lbm_defrag_mem_free(lbm_uint* data) {
242		1036	lbm_uint nbytes = data[0];
243		1036	lbm_uint words_to_wipe = 3 + bs2ws(nbytes);
244	✓✓	7476	for (lbm_uint i = 0; i < words_to_wipe; i ++) {
245		6440	data[i] = 0;
246			}
247		1036	}
248