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 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 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 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 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 148 unsigned long ba_start_addr(struct ba *ba, int index) 149 { 150 return BA_START_ADDR(index); 151 } 152 153 unsigned long ba_len(struct ba *ba, int index) 154 { 155 return BA_LEN(index); 156 } 157