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