Home | History | Annotate | Download | only in linker 
      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