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
23 const int SimpleBestFitAllocator::kMemoryAlign = 32;
24
SimpleBestFitAllocator()25 SimpleBestFitAllocator::SimpleBestFitAllocator()
26 : mHeapSize(0)
27 {
28 }
29
SimpleBestFitAllocator(size_t size)30 SimpleBestFitAllocator::SimpleBestFitAllocator(size_t size)
31 : mHeapSize(0)
32 {
33 setSize(size);
34 }
35
~SimpleBestFitAllocator()36 SimpleBestFitAllocator::~SimpleBestFitAllocator()
37 {
38 while(!mList.isEmpty()) {
39 delete mList.remove(mList.head());
40 }
41 }
42
setSize(size_t size)43 ssize_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
size() const55 size_t SimpleBestFitAllocator::size() const
56 {
57 return mHeapSize;
58 }
59
allocate(size_t size,uint32_t flags)60 ssize_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
deallocate(size_t offset)68 ssize_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
alloc(size_t size,uint32_t flags)79 ssize_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 LOGE_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
dealloc(size_t start)131 SimpleBestFitAllocator::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 #ifndef NDEBUG
157 if (!freed->free) {
158 dump_l("dealloc (!freed->free)");
159 }
160 #endif
161 LOG_FATAL_IF(!freed->free,
162 "freed block at offset 0x%08lX of size 0x%08lX is not free!",
163 freed->start * kMemoryAlign, freed->size * kMemoryAlign);
164
165 return freed;
166 }
167 cur = cur->next;
168 }
169 return 0;
170 }
171