1 | /******************************************************************* |
---|
2 | * File: omAlloc.c |
---|
3 | * Purpose: implementation of main omalloc functions |
---|
4 | * Author: obachman@mathematik.uni-kl.de (Olaf Bachmann) |
---|
5 | * Created: 11/99 |
---|
6 | *******************************************************************/ |
---|
7 | #ifndef OM_ALLOC_C |
---|
8 | #define OM_ALLOC_C |
---|
9 | |
---|
10 | #include "omalloc.h" |
---|
11 | |
---|
12 | #ifdef HAVE_OMALLOC |
---|
13 | /******************************************************************* |
---|
14 | * |
---|
15 | * global variables |
---|
16 | * |
---|
17 | *******************************************************************/ |
---|
18 | |
---|
19 | omBinPage_t om_ZeroPage[] = {{0, NULL, NULL, NULL, NULL}}; |
---|
20 | omSpecBin om_SpecBin = NULL; |
---|
21 | |
---|
22 | #include "omalloc/omTables.inc" |
---|
23 | |
---|
24 | |
---|
25 | /******************************************************************* |
---|
26 | * |
---|
27 | * Local stuff |
---|
28 | * |
---|
29 | *******************************************************************/ |
---|
30 | |
---|
31 | /* Get new page and initialize */ |
---|
32 | static omBinPage omAllocNewBinPage(omBin bin) |
---|
33 | { |
---|
34 | omBinPage newpage; |
---|
35 | void* tmp; |
---|
36 | int i = 1; |
---|
37 | |
---|
38 | if (bin->max_blocks > 0) newpage = omAllocBinPage(); |
---|
39 | else newpage = omAllocBinPages(-bin->max_blocks); |
---|
40 | |
---|
41 | omAssume(omIsAddrPageAligned((void*) newpage)); |
---|
42 | |
---|
43 | omSetTopBinAndStickyOfPage(newpage, bin, bin->sticky); |
---|
44 | newpage->used_blocks = -1; |
---|
45 | newpage->current = (void*) (((char*)newpage) + SIZEOF_OM_BIN_PAGE_HEADER); |
---|
46 | tmp = newpage->current; |
---|
47 | while (i < bin->max_blocks) |
---|
48 | { |
---|
49 | tmp = *((void**)tmp) = ((void**) tmp) + bin->sizeW; |
---|
50 | i++; |
---|
51 | } |
---|
52 | *((void**)tmp) = NULL; |
---|
53 | omAssume(omListLength(newpage->current) == |
---|
54 | (bin->max_blocks > 1 ? bin->max_blocks : 1)); |
---|
55 | return newpage; |
---|
56 | } |
---|
57 | |
---|
58 | /* primitives for handling of list of pages */ |
---|
59 | OM_INLINE_LOCAL void omTakeOutBinPage(omBinPage page, omBin bin) |
---|
60 | { |
---|
61 | if (bin->current_page == page) |
---|
62 | { |
---|
63 | if (page->next == NULL) |
---|
64 | { |
---|
65 | if (page->prev == NULL) |
---|
66 | { |
---|
67 | omAssume(bin->last_page == page); |
---|
68 | bin->last_page = NULL; |
---|
69 | bin->current_page = om_ZeroPage; |
---|
70 | return; |
---|
71 | } |
---|
72 | bin->current_page = page->prev; |
---|
73 | } |
---|
74 | else |
---|
75 | bin->current_page = page->next; |
---|
76 | } |
---|
77 | if (bin->last_page == page) |
---|
78 | { |
---|
79 | omAssume(page->prev != NULL && page->next == NULL); |
---|
80 | bin->last_page = page->prev; |
---|
81 | } |
---|
82 | else |
---|
83 | { |
---|
84 | omAssume(page->next != NULL); |
---|
85 | page->next->prev = page->prev; |
---|
86 | } |
---|
87 | if (page->prev != NULL) page->prev->next = page->next; |
---|
88 | } |
---|
89 | |
---|
90 | OM_INLINE_LOCAL void omInsertBinPage(omBinPage after, omBinPage page, omBin bin) |
---|
91 | { |
---|
92 | if (bin->current_page == om_ZeroPage) |
---|
93 | { |
---|
94 | omAssume(bin->last_page == NULL); |
---|
95 | page->next = NULL; |
---|
96 | page->prev = NULL; |
---|
97 | bin->current_page = page; |
---|
98 | bin->last_page = page; |
---|
99 | } |
---|
100 | else |
---|
101 | { |
---|
102 | omAssume(after != NULL && bin->last_page != NULL); |
---|
103 | if (after == bin->last_page) |
---|
104 | { |
---|
105 | bin->last_page = page; |
---|
106 | } |
---|
107 | else |
---|
108 | { |
---|
109 | omAssume(after->next != NULL); |
---|
110 | after->next->prev = page; |
---|
111 | } |
---|
112 | page->next = after->next; |
---|
113 | after->next = page; |
---|
114 | page->prev = after; |
---|
115 | } |
---|
116 | } |
---|
117 | |
---|
118 | /* bin->current_page is empty, get new bin->current_page, return addr*/ |
---|
119 | void* omAllocBinFromFullPage(omBin bin) |
---|
120 | { |
---|
121 | void* addr; |
---|
122 | omBinPage newpage; |
---|
123 | omAssume(bin->current_page->current == NULL); |
---|
124 | |
---|
125 | if (bin->current_page != om_ZeroPage) |
---|
126 | { |
---|
127 | omAssume(bin->last_page != NULL); |
---|
128 | /* Set this to zero, but preserve the first bit, |
---|
129 | so that tracking works */ |
---|
130 | #ifdef OM_HAVE_TRACK |
---|
131 | bin->current_page->used_blocks &= (((unsigned long) 1) << (BIT_SIZEOF_LONG -1)); |
---|
132 | #else |
---|
133 | bin->current_page->used_blocks = 0; |
---|
134 | #endif |
---|
135 | } |
---|
136 | |
---|
137 | if (!bin->sticky && bin->current_page->next != NULL) |
---|
138 | { |
---|
139 | omAssume(bin->current_page->next->current != NULL); |
---|
140 | newpage = bin->current_page->next; |
---|
141 | } |
---|
142 | else |
---|
143 | { |
---|
144 | // need to Allocate new page |
---|
145 | newpage = omAllocNewBinPage(bin); |
---|
146 | omInsertBinPage(bin->current_page, newpage, bin); |
---|
147 | } |
---|
148 | |
---|
149 | bin->current_page = newpage; |
---|
150 | omAssume(newpage != NULL && newpage != om_ZeroPage && |
---|
151 | newpage->current != NULL); |
---|
152 | __omTypeAllocFromNonEmptyPage(void*, addr, newpage); |
---|
153 | return addr; |
---|
154 | } |
---|
155 | |
---|
156 | |
---|
157 | /* page->used_blocks <= 0, so, either free page or reallocate to |
---|
158 | the right of current_page */ |
---|
159 | /* |
---|
160 | * Now: there are three different strategies here, on what to do with |
---|
161 | * pages which were full and now have a free block: |
---|
162 | * 1.) Insert at the end (default) |
---|
163 | * 2.) Insert after current_page => #define PAGE_AFTER_CURRENT |
---|
164 | * 3.) Let it be new current_page => #define PAGE_BEFORE_CURRENT |
---|
165 | * Still need to try out which is best |
---|
166 | */ |
---|
167 | void omFreeToPageFault(omBinPage page, void* addr) |
---|
168 | { |
---|
169 | omBin bin; |
---|
170 | omAssume(page->used_blocks <= 0L); |
---|
171 | |
---|
172 | #ifdef OM_HAVE_TRACK |
---|
173 | if (page->used_blocks < 0L) |
---|
174 | { |
---|
175 | omFreeTrackAddr(addr); |
---|
176 | return; |
---|
177 | } |
---|
178 | #endif |
---|
179 | |
---|
180 | bin = omGetBinOfPage(page); |
---|
181 | if ((page->current != NULL) || (bin->max_blocks <= 1)) |
---|
182 | { |
---|
183 | // all blocks of page are now collected |
---|
184 | omTakeOutBinPage(page, bin); |
---|
185 | // page can be freed |
---|
186 | if (bin->max_blocks > 0) |
---|
187 | omFreeBinPage(page); |
---|
188 | else |
---|
189 | omFreeBinPages(page, - bin->max_blocks); |
---|
190 | #ifdef OM_HAVE_TRACK |
---|
191 | om_JustFreedPage = page; |
---|
192 | #endif |
---|
193 | } |
---|
194 | else |
---|
195 | { |
---|
196 | // page was full |
---|
197 | page->current = addr; |
---|
198 | page->used_blocks = bin->max_blocks - 2; |
---|
199 | *((void**)addr) = NULL; |
---|
200 | |
---|
201 | omTakeOutBinPage(page, bin); |
---|
202 | #if defined(PAGE_BEFORE_CURRENT) |
---|
203 | if (bin->current_page->prev != NULL) |
---|
204 | omInsertBinPage(bin->current_page->prev, page); |
---|
205 | else |
---|
206 | omInsertBinPage(bin->current_page, page, bin); |
---|
207 | bin->current_page = page; |
---|
208 | #else |
---|
209 | # if defined(PAGE_AFTER_CURRENT) |
---|
210 | omInsertBinPage(bin->current_page, page, bin); |
---|
211 | # else |
---|
212 | omInsertBinPage(bin->last_page, page, bin); |
---|
213 | # endif |
---|
214 | #endif |
---|
215 | } |
---|
216 | } |
---|
217 | |
---|
218 | /******************************************************************* |
---|
219 | * |
---|
220 | * DoRealloc |
---|
221 | * |
---|
222 | *******************************************************************/ |
---|
223 | #ifdef OM_ALIGNMNET_NEEDS_WORK |
---|
224 | #define DO_ZERO(flag) (flag & 1) |
---|
225 | #else |
---|
226 | #define DO_ZERO(flag) flag |
---|
227 | #endif |
---|
228 | |
---|
229 | void* omDoRealloc(void* old_addr, size_t new_size, int flag) |
---|
230 | { |
---|
231 | void* new_addr; |
---|
232 | |
---|
233 | if (!omIsBinPageAddr(old_addr) && new_size > OM_MAX_BLOCK_SIZE) |
---|
234 | { |
---|
235 | if (DO_ZERO(flag)) |
---|
236 | return omRealloc0Large(old_addr, new_size); |
---|
237 | else |
---|
238 | return omReallocLarge(old_addr, new_size); |
---|
239 | } |
---|
240 | else |
---|
241 | { |
---|
242 | size_t old_size = omSizeOfAddr(old_addr); |
---|
243 | size_t min_size; |
---|
244 | |
---|
245 | omAssume(OM_IS_ALIGNED(old_addr)); |
---|
246 | |
---|
247 | #ifdef OM_ALIGNMENT_NEEDS_WORK |
---|
248 | if (flag & 2) |
---|
249 | __omTypeAllocAligned(void*, new_addr, new_size); |
---|
250 | else |
---|
251 | #endif |
---|
252 | __omTypeAlloc(void*, new_addr, new_size); |
---|
253 | |
---|
254 | new_size = omSizeOfAddr(new_addr); |
---|
255 | min_size = (old_size < new_size ? old_size : new_size); |
---|
256 | omMemcpyW(new_addr, old_addr, min_size >> LOG_SIZEOF_LONG); |
---|
257 | |
---|
258 | if (DO_ZERO(flag) && (new_size > old_size)) |
---|
259 | omMemsetW((char*) new_addr + min_size, 0, (new_size - old_size) >> LOG_SIZEOF_LONG); |
---|
260 | |
---|
261 | __omFreeSize(old_addr, old_size); |
---|
262 | |
---|
263 | return new_addr; |
---|
264 | } |
---|
265 | } |
---|
266 | #endif |
---|
267 | #endif /* OM_ALLOC_C */ |
---|