1 /*
2 * Copyright (C) 2008 The Android Open Source Project
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in
12 * the documentation and/or other materials provided with the
13 * distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
18 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
19 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
21 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
22 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
23 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
24 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
25 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 */
28
29 #include "linker.h"
30 #include "linker_debug.h"
31 #include "ba.h"
32
33 #undef min
34 #define min(a,b) ((a)<(b)?(a):(b))
35
36 #define BA_IS_FREE(index) (!(ba->bitmap[index].allocated))
37 #define BA_ORDER(index) ba->bitmap[index].order
38 #define BA_BUDDY_INDEX(index) ((index) ^ (1 << BA_ORDER(index)))
39 #define BA_NEXT_INDEX(index) ((index) + (1 << BA_ORDER(index)))
40 #define BA_OFFSET(index) ((index) * ba->min_alloc)
41 #define BA_START_ADDR(index) (BA_OFFSET(index) + ba->base)
42 #define BA_LEN(index) ((1 << BA_ORDER(index)) * ba->min_alloc)
43
44 static unsigned long ba_order(struct ba *ba, unsigned long len);
45
ba_init(struct ba * ba)46 void ba_init(struct ba *ba)
47 {
48 int i, index = 0;
49
50 unsigned long max_order = ba_order(ba, ba->size);
51 if (ba->max_order == 0 || ba->max_order > max_order)
52 ba->max_order = max_order;
53
54 for (i = sizeof(ba->num_entries) * 8 - 1; i >= 0; i--) {
55 if (ba->num_entries & 1<<i) {
56 BA_ORDER(index) = i;
57 index = BA_NEXT_INDEX(index);
58 }
59 }
60 }
61
ba_free(struct ba * ba,int index)62 int ba_free(struct ba *ba, int index)
63 {
64 int buddy, curr = index;
65
66 /* clean up the bitmap, merging any buddies */
67 ba->bitmap[curr].allocated = 0;
68 /* find a slots buddy Buddy# = Slot# ^ (1 << order)
69 * if the buddy is also free merge them
70 * repeat until the buddy is not free or end of the bitmap is reached
71 */
72 do {
73 buddy = BA_BUDDY_INDEX(curr);
74 if (BA_IS_FREE(buddy) &&
75 BA_ORDER(buddy) == BA_ORDER(curr)) {
76 BA_ORDER(buddy)++;
77 BA_ORDER(curr)++;
78 curr = min(buddy, curr);
79 } else {
80 break;
81 }
82 } while (curr < ba->num_entries);
83
84 return 0;
85 }
86
ba_order(struct ba * ba,unsigned long len)87 static unsigned long ba_order(struct ba *ba, unsigned long len)
88 {
89 unsigned long i;
90
91 len = (len + ba->min_alloc - 1) / ba->min_alloc;
92 len--;
93 for (i = 0; i < sizeof(len)*8; i++)
94 if (len >> i == 0)
95 break;
96 return i;
97 }
98
ba_allocate(struct ba * ba,unsigned long len)99 int ba_allocate(struct ba *ba, unsigned long len)
100 {
101 int curr = 0;
102 int end = ba->num_entries;
103 int best_fit = -1;
104 unsigned long order = ba_order(ba, len);
105
106 if (order > ba->max_order)
107 return -1;
108
109 /* look through the bitmap:
110 * if you find a free slot of the correct order use it
111 * otherwise, use the best fit (smallest with size > order) slot
112 */
113 while (curr < end) {
114 if (BA_IS_FREE(curr)) {
115 if (BA_ORDER(curr) == (unsigned char)order) {
116 /* set the not free bit and clear others */
117 best_fit = curr;
118 break;
119 }
120 if (BA_ORDER(curr) > (unsigned char)order &&
121 (best_fit < 0 ||
122 BA_ORDER(curr) < BA_ORDER(best_fit)))
123 best_fit = curr;
124 }
125 curr = BA_NEXT_INDEX(curr);
126 }
127
128 /* if best_fit < 0, there are no suitable slots,
129 * return an error
130 */
131 if (best_fit < 0)
132 return -1;
133
134 /* now partition the best fit:
135 * split the slot into 2 buddies of order - 1
136 * repeat until the slot is of the correct order
137 */
138 while (BA_ORDER(best_fit) > (unsigned char)order) {
139 int buddy;
140 BA_ORDER(best_fit) -= 1;
141 buddy = BA_BUDDY_INDEX(best_fit);
142 BA_ORDER(buddy) = BA_ORDER(best_fit);
143 }
144 ba->bitmap[best_fit].allocated = 1;
145 return best_fit;
146 }
147
ba_start_addr(struct ba * ba,int index)148 unsigned long ba_start_addr(struct ba *ba, int index)
149 {
150 return BA_START_ADDR(index);
151 }
152
ba_len(struct ba * ba,int index)153 unsigned long ba_len(struct ba *ba, int index)
154 {
155 return BA_LEN(index);
156 }
157