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:	2024-12-05 14:36:58	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		43344	int lbm_memory_init(lbm_uint *data, lbm_uint data_size,
55			lbm_uint *bits, lbm_uint bits_size) {
56
57	✓✓	43344	if (!lbm_mem_mutex_initialized) {
58		21672	mutex_init(&lbm_mem_mutex);
59		21672	lbm_mem_mutex_initialized = true;
60			}
61
62		43344	alloc_offset = 0;
63
64		43344	mutex_lock(&lbm_mem_mutex);
65		43344	int res = 0;
66	✓✗✗✓	43344	if (data == NULL \|\| bits == NULL) return 0;
67
68	✓✗	43344	if (((lbm_uint)data % sizeof(lbm_uint) != 0) \|\|
69	✓✗	43344	(data_size * 2) != (bits_size * sizeof(lbm_uint) * 8) \|\|
70	✓✗	43344	data_size % 4 != 0 \|\|
71	✓✗✓✗	43344	((lbm_uint)bits % sizeof(lbm_uint) != 0) \|\|
72		43344	bits_size < 1 \|\|
73	✓✗	43344	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		43344	bitmap = bits;
80		43344	bitmap_size = bits_size;
81
82	✓✓	11139408	for (lbm_uint i = 0; i < bitmap_size; i ++) {
83		11096064	bitmap[i] = 0;
84			}
85
86		43344	memory = data;
87		43344	memory_base_address = (lbm_uint)data;
88		43344	memory_size = data_size;
89		43344	memory_min_free = data_size;
90		43344	memory_num_free = data_size;
91		43344	memory_reserve_level = (lbm_uint)(0.1 * (lbm_float)data_size);
92		43344	res = 1;
93			}
94		43344	mutex_unlock(&lbm_mem_mutex);
95		43344	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		9679873	static inline lbm_uint address_to_bitmap_ix(lbm_uint *ptr) {
107			#ifndef LBM64
108		9679873	return ((lbm_uint)ptr - memory_base_address) >> 2;
109			#else
110			return ((lbm_uint)ptr - memory_base_address) >> 3;
111			#endif
112			}
113
114		22708	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		22708	return (lbm_int)address_to_bitmap_ix(ptr);
119			}
120
121
122		10400437	static inline lbm_uint *bitmap_ix_to_address(lbm_uint ix) {
123		10400437	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		279058183	static inline lbm_uint status(lbm_uint i) {
137
138		279058183	lbm_uint ix = i << 1; // * 2
139		279058183	lbm_uint word_ix = ix >> WORD_IX_SHIFT; // / 32
140		279058183	lbm_uint bit_ix = ix & WORD_MOD_MASK; // % 32
141
142		279058183	lbm_uint mask = ((lbm_uint)3) << bit_ix; // 000110..0
143	✗✓	279058183	if (word_ix > bitmap_size) {
144			return (lbm_uint)NULL;
145			}
146		279058183	return (bitmap[word_ix] & mask) >> bit_ix;
147			}
148
149		39973998	static inline void set_status(lbm_uint i, lbm_uint status) {
150		39973998	lbm_uint ix = i << 1; // * 2
151		39973998	lbm_uint word_ix = ix >> WORD_IX_SHIFT; // / 32
152		39973998	lbm_uint bit_ix = ix & WORD_MOD_MASK; // % 32
153
154		39973998	lbm_uint clr_mask = ~(((lbm_uint)3) << bit_ix);
155		39973998	lbm_uint mask = status << bit_ix;
156
157		39973998	bitmap[word_ix] &= clr_mask;
158		39973998	bitmap[word_ix] \|= mask;
159		39973998	}
160
161		28	lbm_uint lbm_memory_num_words(void) {
162		28	return memory_size;
163			}
164
165		44408	lbm_uint lbm_memory_num_free(void) {
166		44408	return memory_num_free;
167			}
168
169			lbm_uint lbm_memory_maximum_used(void) {
170			return (memory_size - memory_min_free);
171			}
172
173		347919	void lbm_memory_update_min_free(void) {
174	✓✓	347919	if (memory_num_free < memory_min_free)
175		3350	memory_min_free = memory_num_free;
176		347919	}
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	✓✓✓✗	13477520	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		10138828	case FREE_LENGTH_CHECK:
198		10138828	curr_length ++;
199	✓✓	10138828	if (curr_length > max_length) max_length = curr_length;
200		10138828	state = FREE_LENGTH_CHECK;
201		10138828	break;
202		3334884	case SKIP:
203		3334884	break;
204			}
205		13477520	break;
206		140504	case END:
207		140504	state = INIT;
208		140504	break;
209		140504	case START:
210		140504	state = SKIP;
211		140504	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		10406283	static lbm_uint *lbm_memory_allocate_internal(lbm_uint num_words) {
230
231	✓✗✗✓	10406283	if (memory == NULL \|\| bitmap == NULL) {
232			return NULL;
233			}
234
235		10406283	mutex_lock(&lbm_mem_mutex);
236
237		10406283	lbm_uint start_ix = 0;
238		10406283	lbm_uint end_ix = 0;
239		10406283	lbm_uint free_length = 0;
240		10406283	unsigned int state = INIT;
241		10406283	lbm_uint loop_max = (bitmap_size << BITMAP_SIZE_SHIFT);
242
243	✓✓	100874255	for (lbm_uint i = 0; i < loop_max; i ++) {
244	✓✓✓✓ ✗	100868409	switch(status(alloc_offset)) {
245	✓✓✓✗	89617507	case FREE_OR_USED:
246			switch (state) {
247		10477149	case INIT:
248		10477149	start_ix = alloc_offset;
249	✓✓	10477149	if (num_words == 1) {
250		73352	end_ix = alloc_offset;
251		73352	state = ALLOC_DONE;
252			} else {
253		10403797	state = FREE_LENGTH_CHECK;
254		10403797	free_length = 1;
255			}
256		10477149	break;
257		59493954	case FREE_LENGTH_CHECK:
258		59493954	free_length ++;
259	✓✓	59493954	if (free_length == num_words) {
260		10327085	end_ix = alloc_offset;
261		10327085	state = ALLOC_DONE;
262			} else {
263		49166869	state = FREE_LENGTH_CHECK;
264			}
265		59493954	break;
266		19646404	case SKIP:
267		19646404	break;
268			}
269		89617507	break;
270		10712384	case END:
271		10712384	state = INIT;
272		10712384	break;
273		458564	case START:
274		458564	state = SKIP;
275		458564	break;
276		79954	case START_END:
277		79954	state = INIT;
278		79954	break;
279			default: // error case
280			mutex_unlock(&lbm_mem_mutex);
281			return NULL;
282			}
283
284	✓✓	100868409	if (state == ALLOC_DONE) break;
285
286		90467972	alloc_offset++;
287	✓✓	90467972	if (alloc_offset == loop_max ) {
288		6182	free_length = 0;
289		6182	alloc_offset = 0;
290		6182	state = INIT;
291			}
292			}
293
294	✓✓	10406283	if (state == ALLOC_DONE) {
295	✓✓	10400437	if (start_ix == end_ix) {
296		73352	set_status(start_ix, START_END);
297			} else {
298		10327085	set_status(start_ix, START);
299		10327085	set_status(end_ix, END);
300			}
301		10400437	memory_num_free -= num_words;
302		10400437	mutex_unlock(&lbm_mem_mutex);
303		10400437	return bitmap_ix_to_address(start_ix);
304			}
305		5846	mutex_unlock(&lbm_mem_mutex);
306		5846	return NULL;
307			}
308
309		457856	lbm_uint *lbm_memory_allocate(lbm_uint num_words) {
310	✗✓	457856	if (memory_num_free - num_words < memory_reserve_level) {
311			lbm_request_gc();
312			return NULL;
313			}
314		457856	return lbm_memory_allocate_internal(num_words);
315			}
316
317		9693832	int lbm_memory_free(lbm_uint *ptr) {
318		9693832	int r = 0;
319	✓✓	9693832	if (lbm_memory_ptr_inside(ptr)) {
320		9646294	mutex_lock(&lbm_mem_mutex);
321		9646294	lbm_uint ix = address_to_bitmap_ix(ptr);
322		9646294	lbm_uint count_freed = 0;
323		9646294	alloc_offset = ix;
324	✓✓✗	9646294	switch(status(ix)) {
325		9578440	case START:
326		9578440	set_status(ix, FREE_OR_USED);
327	✓✗	45810911	for (lbm_uint i = ix; i < (bitmap_size << BITMAP_SIZE_SHIFT); i ++) {
328		45810911	count_freed ++;
329	✓✓	45810911	if (status(i) == END) {
330		9578440	set_status(i, FREE_OR_USED);
331		9578440	r = 1;
332		9578440	break;
333			}
334			}
335		9578440	break;
336		67854	case START_END:
337		67854	set_status(ix, FREE_OR_USED);
338		67854	count_freed = 1;
339		67854	r = 1;
340		67854	break;
341			default:
342			break;
343			}
344	✓✗	9646294	if (r) {
345	✓✗✓✓	101263156	while (alloc_offset > 0 && status(alloc_offset - 1) == FREE_OR_USED) {
346		91616862	alloc_offset--;
347			}
348			}
349		9646294	memory_num_free += count_freed;
350		9646294	mutex_unlock(&lbm_mem_mutex);
351			}
352		9693832	return r;
353			}
354			//Malloc/free like interface
355		9910510	void* lbm_malloc(size_t size) {
356	✗✓	9910510	if (size == 0) return NULL;
357			lbm_uint alloc_size;
358
359		9910510	alloc_size = size / sizeof(lbm_uint);
360	✓✓	9910510	if (size % sizeof(lbm_uint)) alloc_size += 1;
361
362	✓✓	9910510	if (memory_num_free - alloc_size < memory_reserve_level) {
363		4280	lbm_request_gc();
364		4280	return NULL;
365			}
366		9906230	return lbm_memory_allocate_internal(alloc_size);
367			}
368
369		42197	void* lbm_malloc_reserve(size_t size) {
370	✗✓	42197	if (size == 0) return NULL;
371			lbm_uint alloc_size;
372
373		42197	alloc_size = size / sizeof(lbm_uint);
374	✓✓	42197	if (size % sizeof(lbm_uint)) alloc_size += 1;
375
376	✓✓	42197	if (memory_num_free - alloc_size < memory_reserve_level) {
377		88	lbm_request_gc();
378			}
379		42197	return lbm_memory_allocate_internal(alloc_size);
380			}
381
382		31606	void lbm_free(void *ptr) {
383		31606	lbm_memory_free(ptr);
384		31606	}
385
386		10871	int lbm_memory_shrink(lbm_uint *ptr, lbm_uint n) {
387	✓✗✗✓	10871	if (!lbm_memory_ptr_inside(ptr) \|\| n == 0) return 0;
388
389		10871	lbm_uint ix = address_to_bitmap_ix(ptr);
390
391		10871	mutex_lock(&lbm_mem_mutex);
392	✗✓	10871	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	✗✓	10871	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		10871	bool done = false;
402		10871	unsigned int i = 0;
403
404	✓✗	116382	for (i = 0; i < ((bitmap_size << BITMAP_SIZE_SHIFT) - ix); i ++) {
405	✗✓✗✗	116382	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	✓✓	116382	if (i == (n-1)) {
411	✓✗✗✓	21742	if (status(ix+i) == END \|\|
412		10871	status(ix+i) == START_END) {
413			done = true;
414			}
415	✓✓	10871	if (i == 0) {
416		1176	set_status(ix+i, START_END);
417			}
418			else {
419		9695	set_status(ix+i, END);
420			}
421		10871	break;
422			}
423			}
424		10871	alloc_offset = ix+i;
425
426		10871	lbm_uint count = 0;
427	✓✗	10871	if (!done) {
428		10871	i++; // move to next position, prev position should be END or START_END
429	✓✗	7546987	for (;i < ((bitmap_size << BITMAP_SIZE_SHIFT) - ix); i ++) {
430		7546987	count ++;
431	✓✓	7546987	if (status(ix+i) == END) {
432		10871	set_status(ix+i, FREE_OR_USED);
433		10871	break;
434			}
435			}
436			}
437
438		10871	memory_num_free += count;
439		10871	mutex_unlock(&lbm_mem_mutex);
440		10871	return 1;
441			}
442
443		9704703	int lbm_memory_ptr_inside(lbm_uint *ptr) {
444	✓✓	19361868	return ((lbm_uint)ptr >= (lbm_uint)memory &&
445	✓✗	9657165	(lbm_uint)ptr < (lbm_uint)memory + (memory_size * sizeof(lbm_uint)));
446			}