1/**
2 * \file
3 * \brief Simple heap allocator.
4 *
5 * This file implements a very simple heap allocator, based on K&R malloc.
6 */
7
8/*
9 * Copyright (c) 2008, ETH Zurich.
10 * All rights reserved.
11 *
12 * This file is distributed under the terms in the attached LICENSE file.
13 * If you do not find this file, copies can be found by writing to:
14 * ETH Zurich D-INFK, Haldeneggsteig 4, CH-8092 Zurich. Attn: Systems Group.
15 */
16
17#include <barrelfish/barrelfish.h>
18#include <barrelfish/heap.h>
19
20/**
21 * \brief Initialise a new heap
22 *
23 * \param heap      Heap structure to be filled in
24 * \param buf       Memory buffer out of which to allocate
25 * \param buflen    Size of buffer
26 * \param morecore_func Function to call to increase heap, or NULL
27 */
28void heap_init(struct heap *heap, void *buf, size_t buflen,
29               Morecore_func_t morecore_func)
30{
31    assert(heap != NULL);
32    assert(buf != NULL);
33    assert(buflen > sizeof(union heap_header));
34
35    // Initialise base header (nothing allocated)
36    heap->base.s.ptr = heap->freep = &heap->base;
37    heap->base.s.size = 0;
38    heap->morecore_func = morecore_func;
39
40    // Insert freelist header into new memory buffer
41    union heap_header *h = buf;
42    h->s.size = buflen / sizeof(union heap_header);
43
44    // Add header to freelist
45    heap_free(heap, (void *)(h + 1));
46}
47
48/**
49 * \brief Equivalent of malloc; allocates memory out of given heap.
50 *
51 * \returns NULL on failure
52 */
53void *heap_alloc(struct heap *heap, size_t nbytes)
54{
55    union heap_header *p, *prevp;
56    unsigned nunits;
57    nunits = (nbytes + sizeof(union heap_header) - 1)
58             / sizeof(union heap_header) + 1;
59
60    prevp = heap->freep;
61    assert(prevp != NULL);
62
63    for (p = prevp->s.ptr;; prevp = p, p = p->s.ptr) {
64        if (p->s.size >= nunits) {    /* big enough */
65            if (p->s.size == nunits) {    /* exactly */
66                prevp->s.ptr = p->s.ptr;
67            } else {    /* allocate tail end */
68                p->s.size -= nunits;
69                p += p->s.size;
70                p->s.size = nunits;
71            }
72            heap->freep = prevp;
73
74            return (void *) (p + 1);
75        }
76        if (p == heap->freep) {    /* wrapped around free list */
77            /* try morecore, if we have one */
78            if (heap->morecore_func == NULL
79                || (p = (union heap_header *)
80                    heap->morecore_func(heap, nunits)) == NULL) {
81                return NULL;    /* none left */
82            }
83        }
84    }
85}
86
87/**
88 * \brief Equivalent of free: put block back in free list.
89 */
90void heap_free(struct heap *heap, void *ap)
91{
92    union heap_header *bp, *p;
93
94    assert(heap != NULL);
95    assert(heap->freep != NULL);
96    if (ap == NULL) {
97        return;
98    }
99
100    bp = (union heap_header *) ap - 1;    /* point to block header */
101    for (p = heap->freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr) {
102        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr)) {
103            break;    /* freed block at start or end of arena */
104        }
105    }
106
107    if (bp + bp->s.size == p->s.ptr) {    /* join to upper nbr */
108        bp->s.size += p->s.ptr->s.size;
109        bp->s.ptr = p->s.ptr->s.ptr;
110    } else {
111        bp->s.ptr = p->s.ptr;
112    }
113
114    if (p + p->s.size == bp) {    /* join to lower nbr */
115        p->s.size += bp->s.size;
116        p->s.ptr = bp->s.ptr;
117    } else {
118        p->s.ptr = bp;
119    }
120
121    heap->freep = p;
122}
123
124
125/**
126 * \brief Allocate and map in one or more pages of memory
127 */
128static void *pages_alloc(size_t pages)
129{
130    assert(!"not implemented");
131    return NULL;
132}
133
134/**
135 * \brief sbrk() equivalent.
136 *
137 * This function allocates at least the amount given by 'nu' in sizeof(::Header)
138 * byte units. It returns a pointer to the freelist header of the memory region.
139 * NULL is returned when out of memory.
140 *
141 * \param nu    Number of memory units (1 unit == sizeof(::Header) bytes)
142 *
143 * \return Pointer to freelist header of new memory region or NULL on out of
144 * memory.
145 */
146union heap_header *heap_default_morecore(struct heap *heap, unsigned nu)
147{
148    union heap_header *up;
149    size_t            nb = ROUND_UP(nu * sizeof(union heap_header),
150                                    BASE_PAGE_SIZE);
151
152    // Allocate requested number of pages and insert freelist header
153    up = (union heap_header*)pages_alloc(nb / BASE_PAGE_SIZE);
154    up->s.size = nb / sizeof(union heap_header);
155
156    // Add header to freelist
157    heap_free(heap, (void *)(up + 1));
158    return up;
159}
160