1/*
2 * free.c
3 *
4 * Very simple linked-list based malloc()/free().
5 */
6
7#include <syslinux/firmware.h>
8#include <stdlib.h>
9#include <dprintf.h>
10#include "malloc.h"
11
12#include <stdio.h>
13
14static struct free_arena_header *
15__free_block(struct free_arena_header *ah)
16{
17    struct free_arena_header *pah, *nah;
18    struct free_arena_header *head =
19	&__core_malloc_head[ARENA_HEAP_GET(ah->a.attrs)];
20
21    pah = ah->a.prev;
22    nah = ah->a.next;
23    if ( ARENA_TYPE_GET(pah->a.attrs) == ARENA_TYPE_FREE &&
24           (char *)pah+ARENA_SIZE_GET(pah->a.attrs) == (char *)ah ) {
25        /* Coalesce into the previous block */
26        ARENA_SIZE_SET(pah->a.attrs, ARENA_SIZE_GET(pah->a.attrs) +
27		ARENA_SIZE_GET(ah->a.attrs));
28        pah->a.next = nah;
29        nah->a.prev = pah;
30
31#ifdef DEBUG_MALLOC
32        ARENA_TYPE_SET(ah->a.attrs, ARENA_TYPE_DEAD);
33#endif
34
35        ah = pah;
36        pah = ah->a.prev;
37    } else {
38        /* Need to add this block to the free chain */
39        ARENA_TYPE_SET(ah->a.attrs, ARENA_TYPE_FREE);
40        ah->a.tag = MALLOC_FREE;
41
42        ah->next_free = head->next_free;
43        ah->prev_free = head;
44        head->next_free = ah;
45        ah->next_free->prev_free = ah;
46    }
47
48    /* In either of the previous cases, we might be able to merge
49       with the subsequent block... */
50    if ( ARENA_TYPE_GET(nah->a.attrs) == ARENA_TYPE_FREE &&
51           (char *)ah+ARENA_SIZE_GET(ah->a.attrs) == (char *)nah ) {
52        ARENA_SIZE_SET(ah->a.attrs, ARENA_SIZE_GET(ah->a.attrs) +
53		ARENA_SIZE_GET(nah->a.attrs));
54
55        /* Remove the old block from the chains */
56        nah->next_free->prev_free = nah->prev_free;
57        nah->prev_free->next_free = nah->next_free;
58        ah->a.next = nah->a.next;
59        nah->a.next->a.prev = ah;
60
61#ifdef DEBUG_MALLOC
62        ARENA_TYPE_SET(nah->a.attrs, ARENA_TYPE_DEAD);
63#endif
64    }
65
66    /* Return the block that contains the called block */
67    return ah;
68}
69
70void bios_free(void *ptr)
71{
72    struct free_arena_header *ah;
73
74    ah = (struct free_arena_header *)
75        ((struct arena_header *)ptr - 1);
76
77#ifdef DEBUG_MALLOC
78    if (ah->a.magic != ARENA_MAGIC)
79	dprintf("failed free() magic check: %p\n", ptr);
80
81    if (ARENA_TYPE_GET(ah->a.attrs) != ARENA_TYPE_USED)
82	dprintf("invalid arena type: %d\n", ARENA_TYPE_GET(ah->a.attrs));
83#endif
84
85    __free_block(ah);
86}
87
88__export void free(void *ptr)
89{
90    dprintf("free(%p) @ %p\n", ptr, __builtin_return_address(0));
91
92    if ( !ptr )
93        return;
94
95    sem_down(&__malloc_semaphore, 0);
96    firmware->mem->free(ptr);
97    sem_up(&__malloc_semaphore);
98
99  /* Here we could insert code to return memory to the system. */
100}
101
102/*
103 * This is used to insert a block which is not previously on the
104 * free list.  Only the a.size field of the arena header is assumed
105 * to be valid.
106 */
107void __inject_free_block(struct free_arena_header *ah)
108{
109    struct free_arena_header *head =
110	&__core_malloc_head[ARENA_HEAP_GET(ah->a.attrs)];
111    struct free_arena_header *nah;
112    size_t a_end = (size_t) ah + ARENA_SIZE_GET(ah->a.attrs);
113    size_t n_end;
114
115    dprintf("inject: %#zx bytes @ %p, heap %u (%p)\n",
116	    ARENA_SIZE_GET(ah->a.attrs), ah,
117	    ARENA_HEAP_GET(ah->a.attrs), head);
118
119    sem_down(&__malloc_semaphore, 0);
120
121    for (nah = head->a.next ; nah != head ; nah = nah->a.next) {
122        n_end = (size_t) nah + ARENA_SIZE_GET(nah->a.attrs);
123
124        /* Is nah entirely beyond this block? */
125        if ((size_t) nah >= a_end)
126            break;
127
128        /* Is this block entirely beyond nah? */
129        if ((size_t) ah >= n_end)
130            continue;
131
132	printf("conflict:ah: %p, a_end: %p, nah: %p, n_end: %p\n", ah, a_end, nah, n_end);
133
134        /* Otherwise we have some sort of overlap - reject this block */
135	sem_up(&__malloc_semaphore);
136        return;
137    }
138
139    /* Now, nah should point to the successor block */
140    ah->a.next = nah;
141    ah->a.prev = nah->a.prev;
142    nah->a.prev = ah;
143    ah->a.prev->a.next = ah;
144
145    __free_block(ah);
146
147    sem_up(&__malloc_semaphore);
148}
149
150/*
151 * Free all memory which is tagged with a specific tag.
152 */
153static void __free_tagged(malloc_tag_t tag) {
154    struct free_arena_header *fp, *head;
155    int i;
156
157    sem_down(&__malloc_semaphore, 0);
158
159    for (i = 0; i < NHEAP; i++) {
160	dprintf("__free_tagged(%u) heap %d\n", tag, i);
161	head = &__core_malloc_head[i];
162	for (fp = head->a.next ; fp != head ; fp = fp->a.next) {
163	    if (ARENA_TYPE_GET(fp->a.attrs) == ARENA_TYPE_USED &&
164		fp->a.tag == tag)
165		fp = __free_block(fp);
166	}
167    }
168
169    sem_up(&__malloc_semaphore);
170    dprintf("__free_tagged(%u) done\n", tag);
171}
172
173void comboot_cleanup_lowmem(com32sys_t *regs)
174{
175    (void)regs;
176
177    __free_tagged(MALLOC_MODULE);
178}
179