← Back to branch summary

~pmdj/ubuntu/trusty/qemu/2.9+applesmc+fadtv3

« back to all changes in this revision

Viewing changes to roms/SLOF/slof/allocator.c

  • Committer: Phil Dennis-Jordan
  • Date: 2017-07-21 08:03:43 UTC
  • mfrom: (1.1.1)
  • Revision ID: phil@philjordan.eu-20170721080343-2yr2vdj7713czahv
New upstream release 2.9.0.

Show diffs side-by-side

added added

removed removed

Lines of Context:
roms/SLOF/slof/allocator.c
 
1
/******************************************************************************
 
2
 * Copyright (c) 2013 IBM Corporation
 
3
 * All rights reserved.
 
4
 * This program and the accompanying materials
 
5
 * are made available under the terms of the BSD License
 
6
 * which accompanies this distribution, and is available at
 
7
 * http://www.opensource.org/licenses/bsd-license.php
 
8
 *
 
9
 * Contributors:
 
10
 *     IBM Corporation - initial implementation
 
11
 *****************************************************************************/
 
12
/*
 
13
 * All functions concerning interface to slof
 
14
 */
 
15
#include <stdio.h>
 
16
#include <string.h>
 
17
#include <stdlib.h>
 
18
#include <stdbool.h>
 
19
#include <helpers.h>
 
20
#include <allocator.h>
 
21
 
 
22
#undef DEBUG
 
23
//#define DEBUG
 
24
#ifdef DEBUG
 
25
#define dprintf(_x ...) do { printf ("%s: ", __func__); printf(_x); } while (0);
 
26
#else
 
27
#define dprintf(_x ...)
 
28
#endif
 
29
 
 
30
#define DEFAULT_BLOCK_SIZE 4096
 
31
 
 
32
#define BM_WORD_SIZE (sizeof(unsigned long))
 
33
#define BM_WORD_BITS (BM_WORD_SIZE * 8)
 
34
 
 
35
struct bitmap {
 
36
        unsigned long start;
 
37
        unsigned long size;
 
38
        unsigned long bm_size;
 
39
        unsigned long block_size;
 
40
        unsigned long free_blocks;
 
41
        unsigned long bmw[];
 
42
};
 
43
 
 
44
#define BIT(x)   (1UL << x)
 
45
#define BM_WORD(bmw, n) (bmw[n/BM_WORD_BITS])
 
46
#define BM_WORD_MODULO(n)  (n % BM_WORD_BITS)
 
47
#define BM_NUM_BITS(reqsize, bsize)     ((reqsize / bsize) + (reqsize % bsize? 1 : 0))
 
48
 
 
49
static void bm_clear_bit(unsigned long *bmw, int n)
 
50
{
 
51
        BM_WORD(bmw, n) &= ~BIT(BM_WORD_MODULO(n));
 
52
}
 
53
 
 
54
static void bm_set_bit(unsigned long *bmw, int n)
 
55
{
 
56
        BM_WORD(bmw, n) |= BIT(BM_WORD_MODULO(n));
 
57
}
 
58
 
 
59
static bool bm_test_bit(unsigned long *bmw, int n)
 
60
{
 
61
#ifdef DEBUG
 
62
        //printf("BMW %x, bitpos %d, value %d\n", &BM_WORD(bmw, n), n, !!(BM_WORD(bmw, n) & BIT(BM_WORD_MODULO(n))));
 
63
#endif
 
64
        return !!(BM_WORD(bmw, n) & BIT(BM_WORD_MODULO(n)));
 
65
}
 
66
 
 
67
/* Improvement: can use FFS routines to get faster results */
 
68
static int bm_find_bits(struct bitmap *bm, unsigned int n_bits)
 
69
{
 
70
        unsigned int i, j, total_bits;
 
71
        int found = -1;
 
72
        dprintf("Finding %d bits set\n", n_bits);
 
73
        total_bits = BM_NUM_BITS(bm->size, bm->block_size);
 
74
        for(i = 0; i < total_bits; i++) {
 
75
                if (!bm_test_bit(bm->bmw, i))
 
76
                        continue;
 
77
                /* we have hit the boundary now, give up */
 
78
                if (i + n_bits > total_bits)
 
79
                        break;
 
80
                /* Lets find if we have consecutive bits set */
 
81
                for(j = i; j < (i + n_bits); j++) {
 
82
                        if (!bm_test_bit(bm->bmw, (j)))
 
83
                                break;
 
84
                }
 
85
                /* Got it */
 
86
                if (j == (i + n_bits)) {
 
87
                        found = i;
 
88
                        break;
 
89
                }
 
90
        }
 
91
        return found;
 
92
}
 
93
 
 
94
void SLOF_bm_print(unsigned long handle)
 
95
{
 
96
        struct bitmap *bm;
 
97
        unsigned int i;
 
98
 
 
99
        if (!handle)
 
100
                return;
 
101
 
 
102
        bm = (struct bitmap *) handle;
 
103
        printf("BITMAP: start %lx, size %ld, blocksize %ld\n\n",
 
104
                bm->start, bm->size, bm->block_size);
 
105
        printf("0                 16                32                48              63\n");
 
106
        for(i = 0; i < BM_NUM_BITS(bm->size, bm->block_size); i++) {
 
107
                if (i > 0 && (i % 64 == 0))
 
108
                        printf("\n");
 
109
                else if (i > 0 && (i % 8 == 0))
 
110
                        printf(" ");
 
111
                printf("%d", bm_test_bit(bm->bmw, i));
 
112
        }
 
113
        printf("\n\n");
 
114
}
 
115
 
 
116
unsigned long SLOF_bm_allocator_init(unsigned long start, unsigned long size,
 
117
                                unsigned long blocksize)
 
118
{
 
119
        struct bitmap *bm;
 
120
        unsigned long alloc_size, bm_size, n_bits;
 
121
 
 
122
        dprintf("enter start %x, size %d, block-size %d\n", start, size, blocksize);
 
123
 
 
124
        if (!size)
 
125
                return 0;
 
126
        if (!blocksize)
 
127
                blocksize = DEFAULT_BLOCK_SIZE;
 
128
 
 
129
        n_bits = BM_NUM_BITS(size, blocksize);
 
130
        bm_size = (n_bits / BM_WORD_BITS) + ((n_bits % BM_WORD_BITS)? 1 : 0);
 
131
        alloc_size = sizeof(struct bitmap) + bm_size * BM_WORD_SIZE;
 
132
        dprintf("Size %ld, blocksize %ld, bm_size %ld, alloc_size %ld\n",
 
133
                size, blocksize, bm_size, alloc_size);
 
134
        bm = (struct bitmap *) SLOF_alloc_mem(alloc_size);
 
135
        if (!bm)
 
136
                return 0;
 
137
        bm->start = start;
 
138
        bm->size = size;
 
139
        bm->bm_size = bm_size;
 
140
        bm->block_size = blocksize;
 
141
        bm->free_blocks = n_bits;
 
142
        memset(bm->bmw, 0xFF, bm_size*BM_WORD_SIZE);
 
143
        return (unsigned long)bm;
 
144
}
 
145
 
 
146
unsigned long SLOF_bm_alloc(unsigned long handle, unsigned long size)
 
147
{
 
148
        struct bitmap *bm;
 
149
        unsigned long n_bits;
 
150
        unsigned long addr;
 
151
        unsigned int i;
 
152
        int bitpos;
 
153
 
 
154
        if (!handle)
 
155
                return -1;
 
156
 
 
157
        bm = (struct bitmap *) handle;
 
158
 
 
159
        n_bits = BM_NUM_BITS(size, bm->block_size);
 
160
        if (n_bits > bm->free_blocks)
 
161
                return -1;
 
162
 
 
163
        bitpos = bm_find_bits(bm, n_bits);
 
164
        if (bitpos == -1)
 
165
                return -1;
 
166
 
 
167
        dprintf("BMW %d, bitpos %d\n", i, bitpos);
 
168
        dprintf("size %d, block_size %d, n_bits %d\n", size, bm->block_size, n_bits);
 
169
        for(i = bitpos; i < (bitpos + n_bits); i++) {
 
170
#ifdef DEBUG
 
171
                if (!bm_test_bit(bm->bmw, i))
 
172
                        dprintf("Warning: Bit already in use: %d\n", i);
 
173
#endif
 
174
                bm_clear_bit(bm->bmw, i);
 
175
        }
 
176
        bm->free_blocks -= n_bits;
 
177
        addr = bm->start + bitpos * bm->block_size;
 
178
        dprintf("BMW %d, bitpos %d addr %lx free_blocks %d\n", i, bitpos, addr, bm->free_blocks);
 
179
        return addr;
 
180
}
 
181
 
 
182
void SLOF_bm_free(unsigned long handle, unsigned long ptr, unsigned long size)
 
183
{
 
184
        struct bitmap *bm;
 
185
        unsigned long bitpos, n_bits;
 
186
        unsigned long addr;
 
187
        unsigned int i;
 
188
 
 
189
        if (!handle)
 
190
                return;
 
191
 
 
192
        bm = (struct bitmap *) handle;
 
193
        addr = (unsigned long ) ptr;
 
194
        n_bits = BM_NUM_BITS(size, bm->block_size);
 
195
        if (addr < bm->start || (bm->start + bm->size) < (addr + size)) {
 
196
                printf("Error: Bitmap start %lx, size %ld, requested address %lx, size %ld\n",
 
197
                        bm->start, bm->size, addr, size);
 
198
                return;
 
199
        }
 
200
        bitpos = (addr - bm->start) / bm->block_size;
 
201
        bm->free_blocks += n_bits;
 
202
 
 
203
#ifdef DEBUG
 
204
        dprintf("addr %lx, bitpos %d\n", addr, bitpos);
 
205
        dprintf("size %d, block_size %d, n_bits %d, free_blocks %d\n", size, bm->block_size, n_bits, bm->free_blocks);
 
206
        if (addr % bm->block_size) {
 
207
                dprintf("Warning: Address not aligned addr %lx\n", addr);
 
208
        }
 
209
#endif
 
210
 
 
211
        for(i = bitpos; i < (bitpos + n_bits); i++) {
 
212
#ifdef DEBUG
 
213
                if (bm_test_bit(bm->bmw, i))
 
214
                        dprintf("Warning: Bit already set: %d\n", i);
 
215
#endif
 
216
                bm_set_bit(bm->bmw, i);
 
217
        }
 
218
 
 
219
        return;
 
220
}