source: git/omalloc/omBinPage.c @ 967895

spielwiese
Last change on this file since 967895 was 967895, checked in by Hans Schoenemann <hannes@…>, 7 years ago
fix: count omalloc-internal small blocks from malloc
  • Property mode set to 100644
File size: 17.6 KB
Line 
1/*******************************************************************
2 *  File:    omBinPage.c
3 *  Purpose: implementation of routines for primitve BinPage managment
4 *  Author:  obachman (Olaf Bachmann)
5 *  Created: 11/99
6 *******************************************************************/
7#include <mylimits.h>
8#include "omalloc.h"
9#include "omDefaultConfig.h"
10
11/*******************************************************************
12 *
13 * Local declarations
14 *
15 *******************************************************************/
16
17/* define if you want to keep regions approximately in order */
18#define OM_KEEP_REGIONS_ORDER
19
20struct omBinPageRegion_s
21{
22  void* current;        /* linked list of free pages */
23  omBinPageRegion next; /* nex/prev pointer in ring of regions */
24  omBinPageRegion prev;
25  char* init_addr;      /* pointer portion of inital chunk which is still free */
26  char* addr;         /* addr returned by alloc */
27  int   init_pages;   /* number of pages still available in init_chunk */
28  int   used_pages;     /* number of used pages */
29  int pages;          /* total size of region */
30};
31
32/* globale variable holding pointing int regions ring */
33static omBinPageRegion om_CurrentBinPageRegion = NULL;
34unsigned long om_MaxBinPageIndex = 0;
35unsigned long om_MinBinPageIndex = ULONG_MAX;
36unsigned long *om_BinPageIndicies = NULL;
37
38/* declaration of local procs */
39static void* omTakeOutConsecutivePages(omBinPageRegion region, int how_many);
40static omBinPageRegion omAllocNewBinPagesRegion(int min_pages);
41static void omFreeBinPagesRegion(omBinPageRegion region);
42
43static void omBinPageIndexFault(unsigned long low_index, unsigned long high_index);
44static void omRegisterBinPages(void* low_addr, int pages);
45static void omUnregisterBinPages(void* low_addr, int pages);
46
47OM_INLINE_LOCAL void omTakeOutRegion(omBinPageRegion region)
48{
49  omAssume(region != NULL);
50
51  if (region->prev != NULL)
52  {
53    omAssume(region->prev != region && region->prev != region->next);
54    region->prev->next = region->next;
55  }
56
57  if (region->next != NULL)
58  {
59    omAssume(region->next != region && region->prev != region->next);
60    region->next->prev = region->prev;
61  }
62}
63
64OM_INLINE_LOCAL void omInsertRegionAfter(omBinPageRegion insert, omBinPageRegion after)
65{
66  omAssume(insert != NULL && after != NULL && insert != after);
67  insert->next = after->next;
68  insert->prev = after;
69  after->next = insert;
70  if (insert->next != NULL)
71  {
72    omAssume(insert->next != insert && insert->next != after);
73    insert->next->prev = insert;
74  }
75}
76
77OM_INLINE_LOCAL void omInsertRegionBefore(omBinPageRegion insert, omBinPageRegion before)
78{
79  omAssume(insert != NULL && before != NULL && insert != before);
80  insert->prev = before->prev;
81  insert->next = before;
82  before->prev = insert;
83  if (insert->prev != NULL)
84    insert->prev->next = insert;
85}
86
87
88/*******************************************************************
89 *
90 * Alloc/Free of BinPages
91 *
92 *******************************************************************/
93#define NEXT_PAGE(page) *((void**) page)
94#define OM_IS_EMPTY_REGION(region) ((region)->current == NULL && (region->init_addr == NULL))
95
96omBinPage omAllocBinPage()
97{
98  omBinPage bin_page;
99
100  if (om_CurrentBinPageRegion == NULL)
101    om_CurrentBinPageRegion = omAllocNewBinPagesRegion(1);
102
103  while (1)
104  {
105    if (om_CurrentBinPageRegion->current != NULL)
106    {
107      bin_page = om_CurrentBinPageRegion->current;
108      om_CurrentBinPageRegion->current = NEXT_PAGE(bin_page);
109      goto Found;
110    }
111    if (om_CurrentBinPageRegion->init_pages > 0)
112    {
113      bin_page = (omBinPage)om_CurrentBinPageRegion->init_addr;
114      om_CurrentBinPageRegion->init_pages--;
115      if (om_CurrentBinPageRegion->init_pages > 0)
116        om_CurrentBinPageRegion->init_addr += SIZEOF_SYSTEM_PAGE;
117      else
118        om_CurrentBinPageRegion->init_addr = NULL;
119      goto Found;
120    }
121    if (om_CurrentBinPageRegion->next != NULL)
122    {
123      om_CurrentBinPageRegion = om_CurrentBinPageRegion->next;
124    }
125    else
126    {
127      omBinPageRegion new_region = omAllocNewBinPagesRegion(1);
128      new_region->prev = om_CurrentBinPageRegion;
129      om_CurrentBinPageRegion->next = new_region;
130      om_CurrentBinPageRegion = new_region;
131    }
132  }
133
134  Found:
135  bin_page->region = om_CurrentBinPageRegion;
136  om_CurrentBinPageRegion->used_pages++;
137
138  om_Info.UsedPages++;
139  om_Info.AvailPages--;
140  if (om_Info.UsedPages > om_Info.MaxPages)
141    om_Info.MaxPages = om_Info.UsedPages;
142
143  OM_ALLOC_BINPAGE_HOOK;
144  return bin_page;
145}
146
147omBinPage omAllocBinPages(int how_many)
148{
149  omBinPage bin_page;
150  omBinPageRegion region;
151
152  if (om_CurrentBinPageRegion == NULL)
153    om_CurrentBinPageRegion = omAllocNewBinPagesRegion(how_many);
154
155  region = om_CurrentBinPageRegion;
156  while (1)
157  {
158    if (region->init_pages >= how_many)
159    {
160      bin_page = (omBinPage)region->init_addr;
161      region->init_pages -= how_many;
162      if (region->init_pages)
163        region->init_addr += how_many*SIZEOF_SYSTEM_PAGE;
164      else
165        region->init_addr = NULL;
166      goto Found;
167    }
168    if ((bin_page = omTakeOutConsecutivePages(region, how_many)) != NULL)
169    {
170      goto Found;
171    }
172    if (region->next != NULL)
173    {
174      region = region->next;
175    }
176    else
177    {
178      omBinPageRegion new_region = omAllocNewBinPagesRegion(how_many);
179      region->next = new_region;
180      new_region->prev = region;
181      region = new_region;
182    }
183  }
184  /*while (1) */
185
186  Found:
187  bin_page->region = region;
188  region->used_pages += how_many;
189
190  if (region != om_CurrentBinPageRegion && OM_IS_EMPTY_REGION(region))
191  {
192    omTakeOutRegion(region);
193    omInsertRegionBefore(region, om_CurrentBinPageRegion);
194  }
195  om_Info.UsedPages += how_many;
196  om_Info.AvailPages -= how_many;
197  if (om_Info.UsedPages > om_Info.MaxPages)
198    om_Info.MaxPages = om_Info.UsedPages;
199
200  OM_ALLOC_BINPAGE_HOOK;
201  return bin_page;
202}
203
204void omFreeBinPages(omBinPage bin_page, int how_many)
205{
206  omBinPageRegion region = bin_page->region;
207
208  region->used_pages -= how_many;
209  if (region->used_pages == 0)
210  {
211    if (region == om_CurrentBinPageRegion)
212    {
213      if (region->next != NULL)
214        om_CurrentBinPageRegion = region->next;
215      else
216        om_CurrentBinPageRegion = region->prev;
217    }
218    omTakeOutRegion(region);
219    omFreeBinPagesRegion(region);
220  }
221  else
222  {
223    if (region != om_CurrentBinPageRegion && OM_IS_EMPTY_REGION(region))
224    {
225      omTakeOutRegion(region);
226      omInsertRegionAfter(region, om_CurrentBinPageRegion);
227    }
228    if (how_many > 1)
229    {
230      int i = how_many;
231      char* page = (char *)bin_page;
232
233      while (i > 1)
234      {
235        NEXT_PAGE(page) = page + SIZEOF_SYSTEM_PAGE;
236        page = NEXT_PAGE(page);
237        i--;
238      }
239      NEXT_PAGE(page) = region->current;
240    }
241    else
242    {
243      NEXT_PAGE(bin_page) = region->current;
244    }
245    region->current = (void*) bin_page;
246  }
247  om_Info.AvailPages += how_many;
248  om_Info.UsedPages -= how_many;
249  OM_FREE_BINPAGE_HOOK;
250}
251
252static void* omTakeOutConsecutivePages(omBinPageRegion region, int pages)
253{
254  void* current;
255  char* iter;
256  void* prev = NULL;
257  void* bin_page;
258  int found;
259  current = region->current;
260  while (current != NULL)
261  {
262    found = 1;
263    iter = current;
264    while (NEXT_PAGE(iter) == (iter + SIZEOF_SYSTEM_PAGE))
265    {
266      iter = NEXT_PAGE(iter);
267      /* handle pathological case that iter + SIZEOF_SYSTEM_PAGE == 0 */
268      if (iter == NULL) return NULL;
269      found++;
270      if (found == pages)
271      {
272        bin_page = current;
273        if (current == region->current)
274        {
275          region->current = NEXT_PAGE(iter);
276        }
277        else
278        {
279          omAssume(prev != NULL);
280          NEXT_PAGE(prev) = NEXT_PAGE(iter);
281        }
282        return bin_page;
283      }
284    }
285    prev = iter;
286    current = NEXT_PAGE(iter);
287  }
288  return NULL;
289}
290
291/* Alloc a new region and insert into regions ring, set current to new region */
292static omBinPageRegion omAllocNewBinPagesRegion(int min_pages)
293{
294  omBinPageRegion region = omAllocFromSystem(sizeof(omBinPageRegion_t));
295  om_Info.InternalUsedBytesMalloc+=sizeof(omBinPageRegion_t);
296  void* addr;
297  int pages = (min_pages>om_Opts.PagesPerRegion ? min_pages : om_Opts.PagesPerRegion);
298  size_t size = pages*SIZEOF_SYSTEM_PAGE;
299
300  addr = _omVallocFromSystem(size, 1);
301  if (addr == NULL)
302  {
303    pages = min_pages;
304    size = min_pages*SIZEOF_SYSTEM_PAGE;
305    addr = omVallocFromSystem(size);
306  }
307
308  omRegisterBinPages(addr, pages);
309  region->addr = addr;
310  region->pages = pages;
311  region->used_pages = 0;
312  region->init_addr = addr;
313  region->init_pages = pages;
314  region->current = NULL;
315  region->next = NULL;
316  region->prev = NULL;
317
318  om_Info.AvailPages += pages;
319
320  om_Info.CurrentRegionsAlloc++;
321  if (om_Info.CurrentRegionsAlloc > om_Info.MaxRegionsAlloc)
322    om_Info.MaxRegionsAlloc = om_Info.CurrentRegionsAlloc;
323
324  return region;
325}
326
327/* Free region */
328static void omFreeBinPagesRegion(omBinPageRegion region)
329{
330  omAssume(region != NULL && region->used_pages == 0);
331
332  om_Info.AvailPages -= region->pages;
333  om_Info.CurrentRegionsAlloc--;
334
335  omUnregisterBinPages(region->addr, region->pages);
336  omVfreeToSystem(region->addr, region->pages*SIZEOF_SYSTEM_PAGE);
337  omFreeSizeToSystem(region, sizeof(omBinPageRegion_t));
338  om_Info.InternalUsedBytesMalloc-=sizeof(omBinPageRegion_t);
339}
340
341/*******************************************************************
342 *
343 * BinPage registration
344 *
345 *******************************************************************/
346
347static void omBinPageIndexFault(unsigned long low_index, unsigned long high_index)
348{
349  unsigned long index_diff = high_index - low_index;
350  long i;
351  omAssume(low_index <= high_index &&
352           (high_index > om_MaxBinPageIndex || low_index < om_MinBinPageIndex));
353
354  if (om_BinPageIndicies == NULL)
355  {
356    om_BinPageIndicies = (unsigned long*) omAllocFromSystem((index_diff + 1)*SIZEOF_LONG);
357    om_MaxBinPageIndex = high_index;
358    om_MinBinPageIndex = low_index;
359    for (i=0; i<=index_diff; i++) om_BinPageIndicies[i] = 0;
360  }
361  else
362  {
363    unsigned long old_length = om_MaxBinPageIndex - om_MinBinPageIndex + 1;
364    unsigned long new_length = (low_index < om_MinBinPageIndex ?
365                                om_MaxBinPageIndex - low_index :
366                                high_index - om_MinBinPageIndex) + 1;
367    om_BinPageIndicies  = (unsigned long*) omReallocSizeFromSystem(om_BinPageIndicies, old_length*SIZEOF_LONG,
368                                                                   new_length*SIZEOF_LONG);
369    if (low_index < om_MinBinPageIndex)
370    {
371      unsigned long offset = new_length - old_length;
372      for (i=old_length - 1; i >= 0; i--) om_BinPageIndicies[i+offset] = om_BinPageIndicies[i];
373      for (i=0; i<offset; i++)  om_BinPageIndicies[i] = 0;
374      om_MinBinPageIndex = low_index;
375    }
376    else
377    {
378      for (i=old_length; i<new_length; i++) om_BinPageIndicies[i] = 0;
379      om_MaxBinPageIndex = high_index;
380    }
381  }
382}
383
384static void omRegisterBinPages(void* low_addr, int pages)
385{
386  unsigned long low_index = omGetPageIndexOfAddr(low_addr);
387  char* high_addr = (char *)low_addr + (pages-1)*SIZEOF_SYSTEM_PAGE;
388  unsigned long high_index = omGetPageIndexOfAddr(high_addr);
389  unsigned long shift;
390
391  if (low_index < om_MinBinPageIndex || high_index > om_MaxBinPageIndex)
392    omBinPageIndexFault(low_index, high_index);
393
394  shift = omGetPageShiftOfAddr(low_addr);
395  if (low_index < high_index)
396  {
397    if (shift == 0)
398    {
399      om_BinPageIndicies[low_index-om_MinBinPageIndex] = ULONG_MAX;
400    }
401    else
402    {
403      om_BinPageIndicies[low_index-om_MinBinPageIndex] |= ~ ((((unsigned long) 1) << shift) - 1);
404    }
405    for (shift = low_index+1; shift < high_index; shift++)
406    {
407      om_BinPageIndicies[shift-om_MinBinPageIndex] = ULONG_MAX;
408    }
409    shift = omGetPageShiftOfAddr(high_addr);
410    if (shift == BIT_SIZEOF_LONG - 1)
411    {
412      om_BinPageIndicies[high_index - om_MinBinPageIndex] = ULONG_MAX;
413    }
414    else
415    {
416      om_BinPageIndicies[high_index-om_MinBinPageIndex] |= ((((unsigned long) 1) << (shift + 1)) - 1);
417    }
418  }
419  else
420  {
421    high_index = omGetPageShiftOfAddr(high_addr);
422    while (high_index > shift)
423    {
424      om_BinPageIndicies[low_index-om_MinBinPageIndex] |= (((unsigned long) 1) << high_index);
425      high_index--;
426    }
427    om_BinPageIndicies[low_index-om_MinBinPageIndex] |= (((unsigned long) 1) << shift);
428  }
429}
430
431static void omUnregisterBinPages(void* low_addr, int pages)
432{
433  unsigned long low_index = omGetPageIndexOfAddr(low_addr);
434  char* high_addr = (char *)low_addr + (pages-1)*SIZEOF_SYSTEM_PAGE;
435  unsigned long high_index = omGetPageIndexOfAddr(high_addr);
436  unsigned long shift;
437
438  shift = omGetPageShiftOfAddr(low_addr);
439  if (low_index < high_index)
440  {
441    if (shift == 0)
442    {
443      om_BinPageIndicies[low_index-om_MinBinPageIndex] = 0;
444    }
445    else
446    {
447      om_BinPageIndicies[low_index-om_MinBinPageIndex] &= ((((unsigned long) 1) << shift) - 1);
448    }
449    for (shift = low_index+1; shift < high_index; shift++)
450    {
451      om_BinPageIndicies[shift-om_MinBinPageIndex] = 0;
452    }
453    shift = omGetPageShiftOfAddr(high_addr);
454    if (shift == BIT_SIZEOF_LONG - 1)
455    {
456      om_BinPageIndicies[high_index - om_MinBinPageIndex] = 0;
457    }
458    else
459    {
460      om_BinPageIndicies[high_index-om_MinBinPageIndex] &= ~ ((((unsigned long) 1) << (shift + 1)) - 1);
461    }
462  }
463  else
464  {
465     high_index = omGetPageShiftOfAddr(high_addr);
466     while (high_index > shift)
467     {
468       om_BinPageIndicies[low_index-om_MinBinPageIndex] &= ~(((unsigned long) 1) << high_index);
469       high_index--;
470     }
471     om_BinPageIndicies[low_index-om_MinBinPageIndex] &= ~(((unsigned long) 1) << shift);
472  }
473}
474
475/***********************************************************************
476 *
477 * checking routines
478 *
479 *******************************************************************/
480#ifndef OM_NDEBUG
481#include "omDebug.h"
482
483int omIsKnownMemoryRegion(omBinPageRegion region)
484{
485  omBinPageRegion iter = om_CurrentBinPageRegion;
486
487  if (region == NULL || iter == NULL) return 0;
488  iter = omGListLast(om_CurrentBinPageRegion, prev);
489  do
490  {
491    if (region == iter) return 1;
492    iter = iter->next;
493  }
494  while (iter != NULL);
495  return 0;
496}
497
498
499omError_t omCheckBinPageRegion(omBinPageRegion region, int level, omError_t report, OM_FLR_DECL)
500{
501  if (level <= 0) return omError_NoError;
502
503  omCheckReturn(omCheckPtr(region, report, OM_FLR_VAL));
504  omCheckReturnCorrupted(! omIsKnownMemoryRegion(region));
505  omCheckReturnCorrupted(! omIsAddrPageAligned(region->addr) || ! omIsAddrPageAligned(region->current));
506  omCheckReturnCorrupted(region->used_pages < 0);
507  omCheckReturnCorrupted(region->init_pages < 0 || region->init_pages > region->pages);
508
509  if (region->init_pages)
510  {
511    omCheckReturnCorrupted(! omIsAddrPageAligned(region->init_addr));
512    omCheckReturnCorrupted(! (region->init_addr >= region->addr
513                              && region->init_addr <= region->addr + (region->pages -1)*SIZEOF_SYSTEM_PAGE));
514    omCheckReturnCorrupted(region->init_addr !=
515                           region->addr + (region->pages - region->init_pages)*SIZEOF_SYSTEM_PAGE);
516  }
517
518  omCheckReturn(omCheckList(region->current, level, report, OM_FLR_VAL));
519  omCheckReturnCorrupted(region->current == NULL && region->used_pages + region->init_pages != region->pages);
520  omCheckReturnCorrupted(level > 1 &&
521                         omListLength(region->current)+region->used_pages+region->init_pages != region->pages);
522  return omError_NoError;
523}
524
525omError_t omCheckBinPageRegions(int level, omError_t report, OM_FLR_DECL)
526{
527  omBinPageRegion iter = om_CurrentBinPageRegion;
528
529  if (level <= 0) return omError_NoError;
530  if (iter == NULL) return omError_NoError;
531
532  omCheckReturnError(om_CurrentBinPageRegion->next != NULL && OM_IS_EMPTY_REGION(om_CurrentBinPageRegion->next),
533                     omError_InternalBug);
534  omCheckReturnError(om_CurrentBinPageRegion->prev != NULL && ! OM_IS_EMPTY_REGION(om_CurrentBinPageRegion->prev),
535                     omError_InternalBug);
536
537
538  if (level > 1)
539  {
540    omBinPageRegion prev_last = (omBinPageRegion) omGListLast(om_CurrentBinPageRegion, prev);
541    omBinPageRegion next_last = (omBinPageRegion) omGListLast(om_CurrentBinPageRegion, next);
542
543    omCheckReturn(omCheckGList(iter, next, level, report, OM_FLR_VAL));
544    omCheckReturn(omCheckGList(iter, prev, level, report, OM_FLR_VAL));
545
546    omCheckReturnCorrupted(omGListLength(prev_last, next)
547                          !=
548                          omGListLength(next_last, prev));
549
550    omCheckReturn(omCheckBinPageRegion(om_CurrentBinPageRegion, level - 1, report, OM_FLR_VAL));
551
552    iter = om_CurrentBinPageRegion->next;
553    while (iter)
554    {
555      omCheckReturnError(OM_IS_EMPTY_REGION(iter), omError_InternalBug);
556
557      omCheckReturn(omCheckBinPageRegion(iter, level - 1, report, OM_FLR_VAL));
558      iter = iter->next;
559    }
560
561    iter = om_CurrentBinPageRegion->prev;
562    while (iter)
563    {
564      omCheckReturnError( !OM_IS_EMPTY_REGION(iter), omError_InternalBug);
565      omCheckReturn(omCheckBinPageRegion(iter, level - 1, report, OM_FLR_VAL));
566      iter = iter->prev;
567    }
568  }
569  return omError_NoError;
570}
571
572omBinPageRegion omFindRegionOfAddr(void* addr)
573{
574  omBinPageRegion region = om_CurrentBinPageRegion;
575
576  if (region == NULL) return 0;
577  region = omGListLast(region, prev);
578  do
579  {
580    if ((char *)addr >= region->addr
581    && (char *)addr < region->addr + (region->pages)*SIZEOF_SYSTEM_PAGE)
582      return region;
583    region = region->next;
584  }
585  while (region != NULL);
586  return NULL;
587}
588
589int omIsAddrOnFreeBinPage(void* addr)
590{
591  char *c_addr=(char *)addr;
592  omBinPageRegion region = om_CurrentBinPageRegion;
593
594  if (region == NULL) return 0;
595  do
596  {
597    if (c_addr > region->addr && c_addr < region->addr + (region->pages)*SIZEOF_SYSTEM_PAGE)
598    {
599      if (omIsOnList(region->current, omGetPageOfAddr(addr))) return 1;
600      return 0;
601    }
602    region = region->next;
603  }
604  while (region != NULL);
605  return 0;
606}
607
608#endif /* ! OM_NDEBUG */
Note: See TracBrowser for help on using the repository browser.