Head

GCC Code Coverage Report

Directory:	../src/		Exec	Total	Coverage
File:	/home/joels/Current/lispbm/src/lbm_memory.c	Lines:	228	254	89.8 %
Date:	2025-01-19 11:10:47	Branches:	95	133	71.4 %


/*
    Copyright 2020 - 2024 Joel Svensson  svenssonjoel@yahoo.se
                     2024 Benjamin Vedder

    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 <stdint.h>
#include <stdlib.h>
#include <stdio.h>

#include "lbm_memory.h"
#include "platform_mutex.h"

// pull in from eval_cps
void lbm_request_gc(void);

/* Status bit patterns */
#define FREE_OR_USED  0  //00b
#define END           1  //01b
#define START         2  //10b
#define START_END     3  //11b

/* States in memory_allocate state-machine*/
#define INIT                 0
#define FREE_LENGTH_CHECK    1
#define SKIP                 2
#define ALLOC_DONE           0xF00DF00D
#define ALLOC_FAILED         0xDEADBEAF

static lbm_uint *bitmap = NULL;
static lbm_uint *memory = NULL;
static lbm_uint memory_size;  // in 4 or 8 byte words depending on 32 or 64 bit platform
static lbm_uint bitmap_size;  // in 4 or 8 byte words
static lbm_uint memory_base_address = 0;
static lbm_uint memory_num_free = 0;
static lbm_uint memory_min_free = 0;
static volatile lbm_uint memory_reserve_level = 0;
static mutex_t lbm_mem_mutex;
static bool    lbm_mem_mutex_initialized;
static lbm_uint alloc_offset = 0;

int lbm_memory_init(lbm_uint *data, lbm_uint data_size,
                    lbm_uint *bits, lbm_uint bits_size) {

  if (!lbm_mem_mutex_initialized) {
    mutex_init(&lbm_mem_mutex);
    lbm_mem_mutex_initialized = true;
  }

  alloc_offset = 0;

  mutex_lock(&lbm_mem_mutex);
  int res = 0;
  if (data == NULL || bits == NULL) return 0;

  if (((lbm_uint)data % sizeof(lbm_uint) != 0) ||
      (data_size * 2) != (bits_size * sizeof(lbm_uint) * 8) ||
      data_size % 4 != 0 ||
      ((lbm_uint)bits % sizeof(lbm_uint) != 0) ||
      bits_size < 1 ||
      bits_size % 4 != 0) {
    // data is not aligned to sizeof lbm_uint
    // size is too small
    // or size is not a multiple of 4
  } else {

    bitmap = bits;
    bitmap_size = bits_size;

    for (lbm_uint i = 0; i < bitmap_size; i ++) {
      bitmap[i] = 0;
    }

    memory = data;
    memory_base_address = (lbm_uint)data;
    memory_size = data_size;
    memory_min_free = data_size;
    memory_num_free = data_size;
    memory_reserve_level = (lbm_uint)(0.1 * (lbm_float)data_size);
    res = 1;
  }
  mutex_unlock(&lbm_mem_mutex);
  return res;
}

void lbm_memory_set_reserve(lbm_uint num_words) {
  memory_reserve_level = num_words;
}

lbm_uint lbm_memory_get_reserve(void) {
  return memory_reserve_level;
}

static inline lbm_uint address_to_bitmap_ix(lbm_uint *ptr) {
  #ifndef LBM64
  return ((lbm_uint)ptr - memory_base_address) >> 2;
  #else
  return ((lbm_uint)ptr - memory_base_address) >> 3;
  #endif
}

lbm_int lbm_memory_address_to_ix(lbm_uint *ptr) {
  /* TODO: assuming that index
           will have more then enough room in the
           positive half of a 28bit integer */
  return (lbm_int)address_to_bitmap_ix(ptr);
}


static inline lbm_uint *bitmap_ix_to_address(lbm_uint ix) {
  return &((lbm_uint*)(memory_base_address))[ix];// + (ix << 2));
}

#ifndef LBM64
#define WORD_IX_SHIFT 5
#define WORD_MOD_MASK 0x1F
#define BITMAP_SIZE_SHIFT 4  // 16 statuses per bitmap word
#else
#define WORD_IX_SHIFT 6      // divide by 64
#define WORD_MOD_MASK 0x3F   // mod 64
#define BITMAP_SIZE_SHIFT 5  // times 32, 32 statuses per bitmap word
#endif

static inline lbm_uint status(lbm_uint i) {

  lbm_uint ix = i << 1;                      // * 2
  lbm_uint word_ix = ix >> WORD_IX_SHIFT;    // / 32
  lbm_uint bit_ix  = ix & WORD_MOD_MASK;              // % 32

  lbm_uint mask = ((lbm_uint)3) << bit_ix;       // 000110..0
  if (word_ix > bitmap_size) {
    return (lbm_uint)NULL;
  }
  return (bitmap[word_ix] & mask) >> bit_ix;
}

static inline void set_status(lbm_uint i, lbm_uint status) {
  lbm_uint ix = i << 1;          // * 2
  lbm_uint word_ix = ix >> WORD_IX_SHIFT;    // / 32
  lbm_uint bit_ix  = ix & WORD_MOD_MASK;  // % 32

  lbm_uint clr_mask = ~(((lbm_uint)3) << bit_ix);
  lbm_uint mask = status << bit_ix;

  bitmap[word_ix] &= clr_mask;
  bitmap[word_ix] |= mask;
}

lbm_uint lbm_memory_num_words(void) {
  return memory_size;
}

lbm_uint lbm_memory_num_free(void) {
  return memory_num_free;
}

lbm_uint lbm_memory_maximum_used(void) {
  return (memory_size - memory_min_free);
}

void lbm_memory_update_min_free(void) {
  if (memory_num_free < memory_min_free)
    memory_min_free = memory_num_free;
}

lbm_uint lbm_memory_longest_free(void) {
  if (memory == NULL || bitmap == NULL) {
    return 0;
  }
  mutex_lock(&lbm_mem_mutex);
  unsigned int state = INIT;
  lbm_uint max_length = 0;

  lbm_uint curr_length = 0;
  for (unsigned int i = 0; i < (bitmap_size << BITMAP_SIZE_SHIFT); i ++) {

    switch(status(i)) {
    case FREE_OR_USED:
      switch (state) {
      case INIT:
        curr_length = 1;
        if (curr_length > max_length) max_length = curr_length;
        state = FREE_LENGTH_CHECK;
        break;
      case FREE_LENGTH_CHECK:
        curr_length ++;
        if (curr_length > max_length) max_length = curr_length;
        state = FREE_LENGTH_CHECK;
        break;
      case SKIP:
        break;
      }
      break;
    case END:
      state = INIT;
      break;
    case START:
      state = SKIP;
      break;
    case START_END:
      state = INIT;
      break;
    default:
      mutex_unlock(&lbm_mem_mutex);
      return 0;
      break;
    }
  }
  mutex_unlock(&lbm_mem_mutex);
  if (memory_num_free - max_length < memory_reserve_level) {
    lbm_uint n = memory_reserve_level - (memory_num_free - max_length);
    max_length -= n;
  }
  return max_length;
}

static lbm_uint *lbm_memory_allocate_internal(lbm_uint num_words) {

  if (memory == NULL || bitmap == NULL) {
    return NULL;
  }

  mutex_lock(&lbm_mem_mutex);

  lbm_uint start_ix = 0;
  lbm_uint end_ix = 0;
  lbm_uint free_length = 0;
  unsigned int state = INIT;
  lbm_uint loop_max = (bitmap_size << BITMAP_SIZE_SHIFT);

  for (lbm_uint i = 0; i < loop_max; i ++) {
    switch(status(alloc_offset)) {
    case FREE_OR_USED:
      switch (state) {
      case INIT:
        start_ix = alloc_offset;
        if (num_words == 1) {
          end_ix = alloc_offset;
          state = ALLOC_DONE;
        } else {
          state = FREE_LENGTH_CHECK;
          free_length = 1;
        }
        break;
      case FREE_LENGTH_CHECK:
        free_length ++;
        if (free_length == num_words) {
          end_ix = alloc_offset;
          state = ALLOC_DONE;
        } else {
          state = FREE_LENGTH_CHECK;
        }
        break;
      case SKIP:
        break;
      }
      break;
    case END:
      state = INIT;
      break;
    case START:
      state = SKIP;
      break;
    case START_END:
      state = INIT;
      break;
    default: // error case
      mutex_unlock(&lbm_mem_mutex);
      return NULL;
    }

    if (state == ALLOC_DONE) break;

    alloc_offset++;
    if (alloc_offset == loop_max ) {
      free_length = 0;
      alloc_offset = 0;
      state = INIT;
    }
  }

  if (state == ALLOC_DONE) {
    if (start_ix == end_ix) {
      set_status(start_ix, START_END);
    } else {
      set_status(start_ix, START);
      set_status(end_ix, END);
    }
    memory_num_free -= num_words;
    mutex_unlock(&lbm_mem_mutex);
    return bitmap_ix_to_address(start_ix);
  }
  mutex_unlock(&lbm_mem_mutex);
  return NULL;
}

lbm_uint *lbm_memory_allocate(lbm_uint num_words) {
  if (memory_num_free - num_words < memory_reserve_level) {
    lbm_request_gc();
    return NULL;
  }
  return lbm_memory_allocate_internal(num_words);
}

int lbm_memory_free(lbm_uint *ptr) {
  int r = 0;
  if (lbm_memory_ptr_inside(ptr)) {
    mutex_lock(&lbm_mem_mutex);
    lbm_uint ix = address_to_bitmap_ix(ptr);
    lbm_uint count_freed = 0;
    alloc_offset = ix;
    switch(status(ix)) {
    case START:
      set_status(ix, FREE_OR_USED);
      for (lbm_uint i = ix; i < (bitmap_size << BITMAP_SIZE_SHIFT); i ++) {
        count_freed ++;
        if (status(i) == END) {
          set_status(i, FREE_OR_USED);
          r = 1;
          break;
        }
      }
      break;
    case START_END:
      set_status(ix, FREE_OR_USED);
      count_freed = 1;
      r = 1;
      break;
    default:
      break;
    }
    if (r) {
      while (alloc_offset > 0 && status(alloc_offset - 1) == FREE_OR_USED) {
        alloc_offset--;
      }
    }
    memory_num_free += count_freed;
    mutex_unlock(&lbm_mem_mutex);
  }
  return r;
}
//Malloc/free like interface
void* lbm_malloc(size_t size) {
  if (size == 0) return NULL;
  lbm_uint alloc_size;

  alloc_size = size / sizeof(lbm_uint);
  if (size % sizeof(lbm_uint)) alloc_size += 1;

  if (memory_num_free - alloc_size < memory_reserve_level) {
    lbm_request_gc();
    return NULL;
  }
  return lbm_memory_allocate_internal(alloc_size);
}

void* lbm_malloc_reserve(size_t size) {
  if (size == 0) return NULL;
  lbm_uint alloc_size;

  alloc_size = size / sizeof(lbm_uint);
  if (size % sizeof(lbm_uint)) alloc_size += 1;

  if (memory_num_free - alloc_size < memory_reserve_level) {
    lbm_request_gc();
  }
  return lbm_memory_allocate_internal(alloc_size);
}

void lbm_free(void *ptr) {
  lbm_memory_free(ptr);
}

int lbm_memory_shrink(lbm_uint *ptr, lbm_uint n) {
  if (!lbm_memory_ptr_inside(ptr) || n == 0) return 0;

  lbm_uint ix = address_to_bitmap_ix(ptr);

  mutex_lock(&lbm_mem_mutex);
  if (status(ix) == START_END) {
    mutex_unlock(&lbm_mem_mutex);
    return 1; // A one word arrays always succeeds at remaining at 1 word
  }
  if (status(ix) != START) {
    mutex_unlock(&lbm_mem_mutex);
    return 0; // ptr does not point to the start of an allocated range.
  }

  bool done = false;
  unsigned int i = 0;

  for (i = 0; i < ((bitmap_size << BITMAP_SIZE_SHIFT) - ix); i ++) {
    if (status(ix+i) == END && i < n) {
      mutex_unlock(&lbm_mem_mutex);
      return 0; // cannot shrink allocation to a larger size
    }

    if (i == (n-1)) {
      if (status(ix+i) == END ||
          status(ix+i) == START_END) {
        done = true;
      }
      if (i == 0) {
        set_status(ix+i, START_END);
      }
      else {
        set_status(ix+i, END);
      }
      break;
    }
  }
  alloc_offset = ix+i;

  lbm_uint count = 0;
  if (!done) {
    i++; // move to next position, prev position should be END or START_END
    for (;i < ((bitmap_size << BITMAP_SIZE_SHIFT) - ix); i ++) {
      count ++;
      if (status(ix+i) == END) {
        set_status(ix+i, FREE_OR_USED);
        break;
      }
    }
  }

  memory_num_free += count;
  mutex_unlock(&lbm_mem_mutex);
  return 1;
}

int lbm_memory_ptr_inside(lbm_uint *ptr) {
  return ((lbm_uint)ptr >= (lbm_uint)memory &&
          (lbm_uint)ptr < (lbm_uint)memory + (memory_size * sizeof(lbm_uint)));
}


Generated by: GCOVR (Version 4.2)

Line	Branch	Exec	Source
1			/*
2			Copyright 2020 - 2024 Joel Svensson svenssonjoel@yahoo.se
3			2024 Benjamin Vedder
4
5			This program is free software: you can redistribute it and/or modify
6			it under the terms of the GNU General Public License as published by
7			the Free Software Foundation, either version 3 of the License, or
8			(at your option) any later version.
9
10			This program is distributed in the hope that it will be useful,
11			but WITHOUT ANY WARRANTY; without even the implied warranty of
12			MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13			GNU General Public License for more details.
14
15			You should have received a copy of the GNU General Public License
16			along with this program. If not, see <http://www.gnu.org/licenses/>.
17			*/
18
19			#include <stdint.h>
20			#include <stdlib.h>
21			#include <stdio.h>
22
23			#include "lbm_memory.h"
24			#include "platform_mutex.h"
25
26			// pull in from eval_cps
27			void lbm_request_gc(void);
28
29			/* Status bit patterns */
30			#define FREE_OR_USED 0 //00b
31			#define END 1 //01b
32			#define START 2 //10b
33			#define START_END 3 //11b
34
35			/* States in memory_allocate state-machine*/
36			#define INIT 0
37			#define FREE_LENGTH_CHECK 1
38			#define SKIP 2
39			#define ALLOC_DONE 0xF00DF00D
40			#define ALLOC_FAILED 0xDEADBEAF
41
42			static lbm_uint *bitmap = NULL;
43			static lbm_uint *memory = NULL;
44			static lbm_uint memory_size; // in 4 or 8 byte words depending on 32 or 64 bit platform
45			static lbm_uint bitmap_size; // in 4 or 8 byte words
46			static lbm_uint memory_base_address = 0;
47			static lbm_uint memory_num_free = 0;
48			static lbm_uint memory_min_free = 0;
49			static volatile lbm_uint memory_reserve_level = 0;
50			static mutex_t lbm_mem_mutex;
51			static bool lbm_mem_mutex_initialized;
52			static lbm_uint alloc_offset = 0;
53
54		43176	int lbm_memory_init(lbm_uint *data, lbm_uint data_size,
55			lbm_uint *bits, lbm_uint bits_size) {
56
57	✓✓	43176	if (!lbm_mem_mutex_initialized) {
58		21588	mutex_init(&lbm_mem_mutex);
59		21588	lbm_mem_mutex_initialized = true;
60			}
61
62		43176	alloc_offset = 0;
63
64		43176	mutex_lock(&lbm_mem_mutex);
65		43176	int res = 0;
66	✓✗✗✓	43176	if (data == NULL \|\| bits == NULL) return 0;
67
68	✓✗	43176	if (((lbm_uint)data % sizeof(lbm_uint) != 0) \|\|
69	✓✗	43176	(data_size * 2) != (bits_size * sizeof(lbm_uint) * 8) \|\|
70	✓✗	43176	data_size % 4 != 0 \|\|
71	✓✗✓✗	43176	((lbm_uint)bits % sizeof(lbm_uint) != 0) \|\|
72		43176	bits_size < 1 \|\|
73	✓✗	43176	bits_size % 4 != 0) {
74			// data is not aligned to sizeof lbm_uint
75			// size is too small
76			// or size is not a multiple of 4
77			} else {
78
79		43176	bitmap = bits;
80		43176	bitmap_size = bits_size;
81
82	✓✓	11096232	for (lbm_uint i = 0; i < bitmap_size; i ++) {
83		11053056	bitmap[i] = 0;
84			}
85
86		43176	memory = data;
87		43176	memory_base_address = (lbm_uint)data;
88		43176	memory_size = data_size;
89		43176	memory_min_free = data_size;
90		43176	memory_num_free = data_size;
91		43176	memory_reserve_level = (lbm_uint)(0.1 * (lbm_float)data_size);
92		43176	res = 1;
93			}
94		43176	mutex_unlock(&lbm_mem_mutex);
95		43176	return res;
96			}
97
98			void lbm_memory_set_reserve(lbm_uint num_words) {
99			memory_reserve_level = num_words;
100			}
101
102			lbm_uint lbm_memory_get_reserve(void) {
103			return memory_reserve_level;
104			}
105
106		9681992	static inline lbm_uint address_to_bitmap_ix(lbm_uint *ptr) {
107			#ifndef LBM64
108		9681992	return ((lbm_uint)ptr - memory_base_address) >> 2;
109			#else
110			return ((lbm_uint)ptr - memory_base_address) >> 3;
111			#endif
112			}
113
114		22624	lbm_int lbm_memory_address_to_ix(lbm_uint *ptr) {
115			/* TODO: assuming that index
116			will have more then enough room in the
117			positive half of a 28bit integer */
118		22624	return (lbm_int)address_to_bitmap_ix(ptr);
119			}
120
121
122		10421506	static inline lbm_uint *bitmap_ix_to_address(lbm_uint ix) {
123		10421506	return &((lbm_uint*)(memory_base_address))[ix];// + (ix << 2));
124			}
125
126			#ifndef LBM64
127			#define WORD_IX_SHIFT 5
128			#define WORD_MOD_MASK 0x1F
129			#define BITMAP_SIZE_SHIFT 4 // 16 statuses per bitmap word
130			#else
131			#define WORD_IX_SHIFT 6 // divide by 64
132			#define WORD_MOD_MASK 0x3F // mod 64
133			#define BITMAP_SIZE_SHIFT 5 // times 32, 32 statuses per bitmap word
134			#endif
135
136		279818589	static inline lbm_uint status(lbm_uint i) {
137
138		279818589	lbm_uint ix = i << 1; // * 2
139		279818589	lbm_uint word_ix = ix >> WORD_IX_SHIFT; // / 32
140		279818589	lbm_uint bit_ix = ix & WORD_MOD_MASK; // % 32
141
142		279818589	lbm_uint mask = ((lbm_uint)3) << bit_ix; // 000110..0
143	✗✓	279818589	if (word_ix > bitmap_size) {
144			return (lbm_uint)NULL;
145			}
146		279818589	return (bitmap[word_ix] & mask) >> bit_ix;
147			}
148
149		40020482	static inline void set_status(lbm_uint i, lbm_uint status) {
150		40020482	lbm_uint ix = i << 1; // * 2
151		40020482	lbm_uint word_ix = ix >> WORD_IX_SHIFT; // / 32
152		40020482	lbm_uint bit_ix = ix & WORD_MOD_MASK; // % 32
153
154		40020482	lbm_uint clr_mask = ~(((lbm_uint)3) << bit_ix);
155		40020482	lbm_uint mask = status << bit_ix;
156
157		40020482	bitmap[word_ix] &= clr_mask;
158		40020482	bitmap[word_ix] \|= mask;
159		40020482	}
160
161		28	lbm_uint lbm_memory_num_words(void) {
162		28	return memory_size;
163			}
164
165		44240	lbm_uint lbm_memory_num_free(void) {
166		44240	return memory_num_free;
167			}
168
169			lbm_uint lbm_memory_maximum_used(void) {
170			return (memory_size - memory_min_free);
171			}
172
173		347733	void lbm_memory_update_min_free(void) {
174	✓✓	347733	if (memory_num_free < memory_min_free)
175		3348	memory_min_free = memory_num_free;
176		347733	}
177
178		3360	lbm_uint lbm_memory_longest_free(void) {
179	✓✗✗✓	3360	if (memory == NULL \|\| bitmap == NULL) {
180			return 0;
181			}
182		3360	mutex_lock(&lbm_mem_mutex);
183		3360	unsigned int state = INIT;
184		3360	lbm_uint max_length = 0;
185
186		3360	lbm_uint curr_length = 0;
187	✓✓	13765920	for (unsigned int i = 0; i < (bitmap_size << BITMAP_SIZE_SHIFT); i ++) {
188
189	✓✓✓✓ ✗	13762560	switch(status(i)) {
190	✓✓✓✗	13470800	case FREE_OR_USED:
191			switch (state) {
192		3808	case INIT:
193		3808	curr_length = 1;
194	✓✓	3808	if (curr_length > max_length) max_length = curr_length;
195		3808	state = FREE_LENGTH_CHECK;
196		3808	break;
197		10128748	case FREE_LENGTH_CHECK:
198		10128748	curr_length ++;
199	✓✓	10128748	if (curr_length > max_length) max_length = curr_length;
200		10128748	state = FREE_LENGTH_CHECK;
201		10128748	break;
202		3338244	case SKIP:
203		3338244	break;
204			}
205		13470800	break;
206		143864	case END:
207		143864	state = INIT;
208		143864	break;
209		143864	case START:
210		143864	state = SKIP;
211		143864	break;
212		4032	case START_END:
213		4032	state = INIT;
214		4032	break;
215			default:
216			mutex_unlock(&lbm_mem_mutex);
217			return 0;
218			break;
219			}
220			}
221		3360	mutex_unlock(&lbm_mem_mutex);
222	✓✗	3360	if (memory_num_free - max_length < memory_reserve_level) {
223		3360	lbm_uint n = memory_reserve_level - (memory_num_free - max_length);
224		3360	max_length -= n;
225			}
226		3360	return max_length;
227			}
228
229		10427354	static lbm_uint *lbm_memory_allocate_internal(lbm_uint num_words) {
230
231	✓✗✗✓	10427354	if (memory == NULL \|\| bitmap == NULL) {
232			return NULL;
233			}
234
235		10427354	mutex_lock(&lbm_mem_mutex);
236
237		10427354	lbm_uint start_ix = 0;
238		10427354	lbm_uint end_ix = 0;
239		10427354	lbm_uint free_length = 0;
240		10427354	unsigned int state = INIT;
241		10427354	lbm_uint loop_max = (bitmap_size << BITMAP_SIZE_SHIFT);
242
243	✓✓	101371956	for (lbm_uint i = 0; i < loop_max; i ++) {
244	✓✓✓✓ ✗	101366108	switch(status(alloc_offset)) {
245	✓✓✓✗	90086318	case FREE_OR_USED:
246			switch (state) {
247		10495174	case INIT:
248		10495174	start_ix = alloc_offset;
249	✓✓	10495174	if (num_words == 1) {
250		73352	end_ix = alloc_offset;
251		73352	state = ALLOC_DONE;
252			} else {
253		10421822	state = FREE_LENGTH_CHECK;
254		10421822	free_length = 1;
255			}
256		10495174	break;
257		59943636	case FREE_LENGTH_CHECK:
258		59943636	free_length ++;
259	✓✓	59943636	if (free_length == num_words) {
260		10348154	end_ix = alloc_offset;
261		10348154	state = ALLOC_DONE;
262			} else {
263		49595482	state = FREE_LENGTH_CHECK;
264			}
265		59943636	break;
266		19647508	case SKIP:
267		19647508	break;
268			}
269		90086318	break;
270		10734530	case END:
271		10734530	state = INIT;
272		10734530	break;
273		465218	case START:
274		465218	state = SKIP;
275		465218	break;
276		80042	case START_END:
277		80042	state = INIT;
278		80042	break;
279			default: // error case
280			mutex_unlock(&lbm_mem_mutex);
281			return NULL;
282			}
283
284	✓✓	101366108	if (state == ALLOC_DONE) break;
285
286		90944602	alloc_offset++;
287	✓✓	90944602	if (alloc_offset == loop_max ) {
288		6184	free_length = 0;
289		6184	alloc_offset = 0;
290		6184	state = INIT;
291			}
292			}
293
294	✓✓	10427354	if (state == ALLOC_DONE) {
295	✓✓	10421506	if (start_ix == end_ix) {
296		73352	set_status(start_ix, START_END);
297			} else {
298		10348154	set_status(start_ix, START);
299		10348154	set_status(end_ix, END);
300			}
301		10421506	memory_num_free -= num_words;
302		10421506	mutex_unlock(&lbm_mem_mutex);
303		10421506	return bitmap_ix_to_address(start_ix);
304			}
305		5848	mutex_unlock(&lbm_mem_mutex);
306		5848	return NULL;
307			}
308
309		477232	lbm_uint *lbm_memory_allocate(lbm_uint num_words) {
310	✗✓	477232	if (memory_num_free - num_words < memory_reserve_level) {
311			lbm_request_gc();
312			return NULL;
313			}
314		477232	return lbm_memory_allocate_internal(num_words);
315			}
316
317		9696486	int lbm_memory_free(lbm_uint *ptr) {
318		9696486	int r = 0;
319	✓✓	9696486	if (lbm_memory_ptr_inside(ptr)) {
320		9649124	mutex_lock(&lbm_mem_mutex);
321		9649124	lbm_uint ix = address_to_bitmap_ix(ptr);
322		9649124	lbm_uint count_freed = 0;
323		9649124	alloc_offset = ix;
324	✓✓✗	9649124	switch(status(ix)) {
325		9581210	case START:
326		9581210	set_status(ix, FREE_OR_USED);
327	✓✗	46281967	for (lbm_uint i = ix; i < (bitmap_size << BITMAP_SIZE_SHIFT); i ++) {
328		46281967	count_freed ++;
329	✓✓	46281967	if (status(i) == END) {
330		9581210	set_status(i, FREE_OR_USED);
331		9581210	r = 1;
332		9581210	break;
333			}
334			}
335		9581210	break;
336		67914	case START_END:
337		67914	set_status(ix, FREE_OR_USED);
338		67914	count_freed = 1;
339		67914	r = 1;
340		67914	break;
341			default:
342			break;
343			}
344	✓✗	9649124	if (r) {
345	✓✗✓✓	101067652	while (alloc_offset > 0 && status(alloc_offset - 1) == FREE_OR_USED) {
346		91418528	alloc_offset--;
347			}
348			}
349		9649124	memory_num_free += count_freed;
350		9649124	mutex_unlock(&lbm_mem_mutex);
351			}
352		9696486	return r;
353			}
354			//Malloc/free like interface
355		9904684	void* lbm_malloc(size_t size) {
356	✗✓	9904684	if (size == 0) return NULL;
357			lbm_uint alloc_size;
358
359		9904684	alloc_size = size / sizeof(lbm_uint);
360	✓✓	9904684	if (size % sizeof(lbm_uint)) alloc_size += 1;
361
362	✓✓	9904684	if (memory_num_free - alloc_size < memory_reserve_level) {
363		4280	lbm_request_gc();
364		4280	return NULL;
365			}
366		9900404	return lbm_memory_allocate_internal(alloc_size);
367			}
368
369		49718	void* lbm_malloc_reserve(size_t size) {
370	✗✓	49718	if (size == 0) return NULL;
371			lbm_uint alloc_size;
372
373		49718	alloc_size = size / sizeof(lbm_uint);
374	✓✓	49718	if (size % sizeof(lbm_uint)) alloc_size += 1;
375
376	✓✓	49718	if (memory_num_free - alloc_size < memory_reserve_level) {
377		88	lbm_request_gc();
378			}
379		49718	return lbm_memory_allocate_internal(alloc_size);
380			}
381
382		39018	void lbm_free(void *ptr) {
383		39018	lbm_memory_free(ptr);
384		39018	}
385
386		10244	int lbm_memory_shrink(lbm_uint *ptr, lbm_uint n) {
387	✓✗✗✓	10244	if (!lbm_memory_ptr_inside(ptr) \|\| n == 0) return 0;
388
389		10244	lbm_uint ix = address_to_bitmap_ix(ptr);
390
391		10244	mutex_lock(&lbm_mem_mutex);
392	✗✓	10244	if (status(ix) == START_END) {
393			mutex_unlock(&lbm_mem_mutex);
394			return 1; // A one word arrays always succeeds at remaining at 1 word
395			}
396	✗✓	10244	if (status(ix) != START) {
397			mutex_unlock(&lbm_mem_mutex);
398			return 0; // ptr does not point to the start of an allocated range.
399			}
400
401		10244	bool done = false;
402		10244	unsigned int i = 0;
403
404	✓✗	115128	for (i = 0; i < ((bitmap_size << BITMAP_SIZE_SHIFT) - ix); i ++) {
405	✗✓✗✗	115128	if (status(ix+i) == END && i < n) {
406			mutex_unlock(&lbm_mem_mutex);
407			return 0; // cannot shrink allocation to a larger size
408			}
409
410	✓✓	115128	if (i == (n-1)) {
411	✓✗✗✓	20488	if (status(ix+i) == END \|\|
412		10244	status(ix+i) == START_END) {
413			done = true;
414			}
415	✓✓	10244	if (i == 0) {
416		1176	set_status(ix+i, START_END);
417			}
418			else {
419		9068	set_status(ix+i, END);
420			}
421		10244	break;
422			}
423			}
424		10244	alloc_offset = ix+i;
425
426		10244	lbm_uint count = 0;
427	✓✗	10244	if (!done) {
428		10244	i++; // move to next position, prev position should be END or START_END
429	✓✗	7535074	for (;i < ((bitmap_size << BITMAP_SIZE_SHIFT) - ix); i ++) {
430		7535074	count ++;
431	✓✓	7535074	if (status(ix+i) == END) {
432		10244	set_status(ix+i, FREE_OR_USED);
433		10244	break;
434			}
435			}
436			}
437
438		10244	memory_num_free += count;
439		10244	mutex_unlock(&lbm_mem_mutex);
440		10244	return 1;
441			}
442
443		9706730	int lbm_memory_ptr_inside(lbm_uint *ptr) {
444	✓✓	19366098	return ((lbm_uint)ptr >= (lbm_uint)memory &&
445	✓✗	9659368	(lbm_uint)ptr < (lbm_uint)memory + (memory_size * sizeof(lbm_uint)));
446			}