1/*
2 * Copyright (C) 2009 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include <cutils/log.h>
18
19#include "allocator.h"
20
21
22// align all the memory blocks on a cache-line boundary
23const int SimpleBestFitAllocator::kMemoryAlign = 32;
24
25SimpleBestFitAllocator::SimpleBestFitAllocator()
26    : mHeapSize(0)
27{
28}
29
30SimpleBestFitAllocator::SimpleBestFitAllocator(size_t size)
31    : mHeapSize(0)
32{
33    setSize(size);
34}
35
36SimpleBestFitAllocator::~SimpleBestFitAllocator()
37{
38    while(!mList.isEmpty()) {
39        delete mList.remove(mList.head());
40    }
41}
42
43ssize_t SimpleBestFitAllocator::setSize(size_t size)
44{
45    Locker::Autolock _l(mLock);
46    if (mHeapSize != 0) return -EINVAL;
47    size_t pagesize = getpagesize();
48    mHeapSize = ((size + pagesize-1) & ~(pagesize-1));
49    chunk_t* node = new chunk_t(0, mHeapSize / kMemoryAlign);
50    mList.insertHead(node);
51    return size;
52}
53
54
55size_t SimpleBestFitAllocator::size() const
56{
57    return mHeapSize;
58}
59
60ssize_t SimpleBestFitAllocator::allocate(size_t size, uint32_t flags)
61{
62    Locker::Autolock _l(mLock);
63    if (mHeapSize == 0) return -EINVAL;
64    ssize_t offset = alloc(size, flags);
65    return offset;
66}
67
68ssize_t SimpleBestFitAllocator::deallocate(size_t offset)
69{
70    Locker::Autolock _l(mLock);
71    if (mHeapSize == 0) return -EINVAL;
72    chunk_t const * const freed = dealloc(offset);
73    if (freed) {
74        return 0;
75    }
76    return -ENOENT;
77}
78
79ssize_t SimpleBestFitAllocator::alloc(size_t size, uint32_t flags)
80{
81    if (size == 0) {
82        return 0;
83    }
84    size = (size + kMemoryAlign-1) / kMemoryAlign;
85    chunk_t* free_chunk = 0;
86    chunk_t* cur = mList.head();
87
88    size_t pagesize = getpagesize();
89    while (cur) {
90        int extra = ( -cur->start & ((pagesize/kMemoryAlign)-1) ) ;
91
92        // best fit
93        if (cur->free && (cur->size >= (size+extra))) {
94            if ((!free_chunk) || (cur->size < free_chunk->size)) {
95                free_chunk = cur;
96            }
97            if (cur->size == size) {
98                break;
99            }
100        }
101        cur = cur->next;
102    }
103
104    if (free_chunk) {
105        const size_t free_size = free_chunk->size;
106        free_chunk->free = 0;
107        free_chunk->size = size;
108        if (free_size > size) {
109            int extra = ( -free_chunk->start & ((pagesize/kMemoryAlign)-1) ) ;
110            if (extra) {
111                chunk_t* split = new chunk_t(free_chunk->start, extra);
112                free_chunk->start += extra;
113                mList.insertBefore(free_chunk, split);
114            }
115
116            ALOGE_IF(((free_chunk->start*kMemoryAlign)&(pagesize-1)),
117                    "page is not aligned!!!");
118
119            const ssize_t tail_free = free_size - (size+extra);
120            if (tail_free > 0) {
121                chunk_t* split = new chunk_t(
122                        free_chunk->start + free_chunk->size, tail_free);
123                mList.insertAfter(free_chunk, split);
124            }
125        }
126        return (free_chunk->start)*kMemoryAlign;
127    }
128    return -ENOMEM;
129}
130
131SimpleBestFitAllocator::chunk_t* SimpleBestFitAllocator::dealloc(size_t start)
132{
133    start = start / kMemoryAlign;
134    chunk_t* cur = mList.head();
135    while (cur) {
136        if (cur->start == start) {
137            LOG_FATAL_IF(cur->free,
138                "block at offset 0x%08lX of size 0x%08lX already freed",
139                cur->start*kMemoryAlign, cur->size*kMemoryAlign);
140
141            // merge freed blocks together
142            chunk_t* freed = cur;
143            cur->free = 1;
144            do {
145                chunk_t* const p = cur->prev;
146                chunk_t* const n = cur->next;
147                if (p && (p->free || !cur->size)) {
148                    freed = p;
149                    p->size += cur->size;
150                    mList.remove(cur);
151                    delete cur;
152                }
153                cur = n;
154            } while (cur && cur->free);
155
156            LOG_FATAL_IF(!freed->free,
157                "freed block at offset 0x%08lX of size 0x%08lX is not free!",
158                freed->start * kMemoryAlign, freed->size * kMemoryAlign);
159
160            return freed;
161        }
162        cur = cur->next;
163    }
164    return 0;
165}
166