omBinPage.c File Reference

#include <limits.h>
#include "omalloc.h"
#include "omDefaultConfig.h"
#include "omDebug.h"

Go to the source code of this file.

Data Structures
struct	omBinPageRegion_t

Macros
#define	OM_KEEP_REGIONS_ORDER
#define	NEXT_PAGE(page)   *((void**) page)
#define	OM_IS_EMPTY_REGION(region)   ((region)->current == NULL && (region->init_addr == NULL))

Functions
static void *	omTakeOutConsecutivePages (omBinPageRegion region, int how_many)
static omBinPageRegion	omAllocNewBinPagesRegion (int min_pages)
static void	omFreeBinPagesRegion (omBinPageRegion region)
static void	omBinPageIndexFault (unsigned long low_index, unsigned long high_index)
static void	omRegisterBinPages (void *low_addr, int pages)
static void	omUnregisterBinPages (void *low_addr, int pages)
OM_INLINE_LOCAL void	omTakeOutRegion (omBinPageRegion region)
OM_INLINE_LOCAL void	omInsertRegionAfter (omBinPageRegion insert, omBinPageRegion after)
OM_INLINE_LOCAL void	omInsertRegionBefore (omBinPageRegion insert, omBinPageRegion before)
omBinPage	omAllocBinPage ()
omBinPage	omAllocBinPages (int how_many)
void	omFreeBinPages (omBinPage bin_page, int how_many)
int	omIsKnownMemoryRegion (omBinPageRegion region)
omError_t	omCheckBinPageRegion (omBinPageRegion region, int level, omError_t report, OM_FLR_DECL)
omError_t	omCheckBinPageRegions (int level, omError_t report, OM_FLR_DECL)
omBinPageRegion	omFindRegionOfAddr (void *addr)
int	omIsAddrOnFreeBinPage (void *addr)

Variables
static omBinPageRegion	om_CurrentBinPageRegion = NULL
unsigned long	om_MaxBinPageIndex = 0
unsigned long	om_MinBinPageIndex = ULONG_MAX
unsigned long *	om_BinPageIndicies = NULL

---

Data Structure Documentation

omBinPageRegion_s

struct omBinPageRegion_s

Definition at line 22 of file omBinPage.c.

Data Fields
char *	addr
void *	current
char *	init_addr
int	init_pages
omBinPageRegion	next
int	pages
omBinPageRegion	prev
int	used_pages

Macro Definition Documentation

NEXT_PAGE

#define NEXT_PAGE

(

page

)

*((void**) page)

Definition at line 95 of file omBinPage.c.

OM_IS_EMPTY_REGION

#define OM_IS_EMPTY_REGION

(

region

)

((region)->current == NULL && (region->init_addr == NULL))

Definition at line 96 of file omBinPage.c.

OM_KEEP_REGIONS_ORDER

#define OM_KEEP_REGIONS_ORDER

Definition at line 20 of file omBinPage.c.

Function Documentation

omAllocBinPage()

omBinPage omAllocBinPage

(

void

)

Definition at line 98 of file omBinPage.c.

{
  omBinPage bin_page;
 
  if (om_CurrentBinPageRegion == NULL)
    om_CurrentBinPageRegion = omAllocNewBinPagesRegion(1);
 
  while (1)
  {
    if (om_CurrentBinPageRegion->current != NULL)
    {
      bin_page = om_CurrentBinPageRegion->current;
      om_CurrentBinPageRegion->current = NEXT_PAGE(bin_page);
      goto Found;
    }
    if (om_CurrentBinPageRegion->init_pages > 0)
    {
      bin_page = (omBinPage)om_CurrentBinPageRegion->init_addr;
      om_CurrentBinPageRegion->init_pages--;
      if (om_CurrentBinPageRegion->init_pages > 0)
        om_CurrentBinPageRegion->init_addr += SIZEOF_SYSTEM_PAGE;
      else
        om_CurrentBinPageRegion->init_addr = NULL;
      goto Found;
    }
    if (om_CurrentBinPageRegion->next != NULL)
    {
      om_CurrentBinPageRegion = om_CurrentBinPageRegion->next;
    }
    else
    {
      omBinPageRegion new_region = omAllocNewBinPagesRegion(1);
      new_region->prev = om_CurrentBinPageRegion;
      om_CurrentBinPageRegion->next = new_region;
      om_CurrentBinPageRegion = new_region;
    }
  }
 
  Found:
  bin_page->region = om_CurrentBinPageRegion;
  om_CurrentBinPageRegion->used_pages++;
 
  om_Info.UsedPages++;
  om_Info.AvailPages--;
  if (om_Info.UsedPages > om_Info.MaxPages)
    om_Info.MaxPages = om_Info.UsedPages;
 
  OM_ALLOC_BINPAGE_HOOK;
  return bin_page;
}

omAllocBinPages()

omBinPage omAllocBinPages

(

int

how_many

)

Definition at line 149 of file omBinPage.c.

{
  omBinPage bin_page;
  omBinPageRegion region;
 
  if (om_CurrentBinPageRegion == NULL)
    om_CurrentBinPageRegion = omAllocNewBinPagesRegion(how_many);
 
  region = om_CurrentBinPageRegion;
  while (1)
  {
    if (region->init_pages >= how_many)
    {
      bin_page = (omBinPage)region->init_addr;
      region->init_pages -= how_many;
      if (region->init_pages)
        region->init_addr += how_many*SIZEOF_SYSTEM_PAGE;
      else
        region->init_addr = NULL;
      goto Found;
    }
    if ((bin_page = omTakeOutConsecutivePages(region, how_many)) != NULL)
    {
      goto Found;
    }
    if (region->next != NULL)
    {
      region = region->next;
    }
    else
    {
      omBinPageRegion new_region = omAllocNewBinPagesRegion(how_many);
      region->next = new_region;
      new_region->prev = region;
      region = new_region;
    }
  }
  /*while (1) */
 
  Found:
  bin_page->region = region;
  region->used_pages += how_many;
 
  if (region != om_CurrentBinPageRegion && OM_IS_EMPTY_REGION(region))
  {
    omTakeOutRegion(region);
    omInsertRegionBefore(region, om_CurrentBinPageRegion);
  }
  om_Info.UsedPages += how_many;
  om_Info.AvailPages -= how_many;
  if (om_Info.UsedPages > om_Info.MaxPages)
    om_Info.MaxPages = om_Info.UsedPages;
 
  OM_ALLOC_BINPAGE_HOOK;
  return bin_page;
}

omAllocNewBinPagesRegion()

static omBinPageRegion omAllocNewBinPagesRegion ( int  min_pages )

static

Definition at line 294 of file omBinPage.c.

{
  omBinPageRegion region = omAllocFromSystem(sizeof(omBinPageRegion_t));
  om_Info.InternalUsedBytesMalloc+=sizeof(omBinPageRegion_t);
  void* addr;
  int pages = (min_pages>om_Opts.PagesPerRegion ? min_pages : om_Opts.PagesPerRegion);
  size_t size = ((size_t)pages)*SIZEOF_SYSTEM_PAGE;
 
  addr = _omVallocFromSystem(size, 1);
  if (addr == NULL)
  {
    pages = min_pages;
    size = min_pages*SIZEOF_SYSTEM_PAGE;
    addr = omVallocFromSystem(size);
  }
 
  omRegisterBinPages(addr, pages);
  region->addr = addr;
  region->pages = pages;
  region->used_pages = 0;
  region->init_addr = addr;
  region->init_pages = pages;
  region->current = NULL;
  region->next = NULL;
  region->prev = NULL;
 
  om_Info.AvailPages += pages;
 
  om_Info.CurrentRegionsAlloc++;
  if (om_Info.CurrentRegionsAlloc > om_Info.MaxRegionsAlloc)
    om_Info.MaxRegionsAlloc = om_Info.CurrentRegionsAlloc;
 
  return region;
}

omBinPageIndexFault()

static void omBinPageIndexFault ( unsigned long  low_index, unsigned long  high_index  )

static

Definition at line 349 of file omBinPage.c.

{
  unsigned long index_diff = high_index - low_index;
  omAssume(low_index <= high_index &&
           (high_index > om_MaxBinPageIndex || low_index < om_MinBinPageIndex));
 
  if (om_BinPageIndicies == NULL)
  {
    unsigned long i;
    om_BinPageIndicies = (unsigned long*) omAllocFromSystem((index_diff + 1)*SIZEOF_LONG);
    om_Info.InternalUsedBytesMalloc+=(index_diff + 1)*SIZEOF_LONG;
    om_MaxBinPageIndex = high_index;
    om_MinBinPageIndex = low_index;
    for (i=0; i<=index_diff; i++) om_BinPageIndicies[i] = 0;
  }
  else
  {
    unsigned long old_length = om_MaxBinPageIndex - om_MinBinPageIndex + 1;
    unsigned long new_length = (low_index < om_MinBinPageIndex ?
                                om_MaxBinPageIndex - low_index :
                                high_index - om_MinBinPageIndex) + 1;
    om_BinPageIndicies  = (unsigned long*) omReallocSizeFromSystem(om_BinPageIndicies, old_length*SIZEOF_LONG,
                                                                   new_length*SIZEOF_LONG);
    om_Info.InternalUsedBytesMalloc+= (new_length-old_length)*SIZEOF_LONG;
    if (low_index < om_MinBinPageIndex)
    {
      long i;
      unsigned long offset = new_length - old_length;
      for (i=old_length - 1; i >= 0; i--) om_BinPageIndicies[i+offset] = om_BinPageIndicies[i];
      for (i=offset-1; i>=0; i--)  om_BinPageIndicies[i] = 0;
      om_MinBinPageIndex = low_index;
    }
    else
    {
      unsigned long i;
      for (i=old_length; i<new_length; i++) om_BinPageIndicies[i] = 0;
      om_MaxBinPageIndex = high_index;
    }
  }
}

omCheckBinPageRegion()

omError_t omCheckBinPageRegion	(	omBinPageRegion	region,
		int	level,
		omError_t	report,
		OM_FLR_DECL
	)

Definition at line 505 of file omBinPage.c.

{
  if (level <= 0) return omError_NoError;
 
  omCheckReturn(omCheckPtr(region, report, OM_FLR_VAL));
  omCheckReturnCorrupted(! omIsKnownMemoryRegion(region));
  omCheckReturnCorrupted(! omIsAddrPageAligned(region->addr) || ! omIsAddrPageAligned(region->current));
  omCheckReturnCorrupted(region->used_pages < 0);
  omCheckReturnCorrupted(region->init_pages < 0 || region->init_pages > region->pages);
 
  if (region->init_pages)
  {
    omCheckReturnCorrupted(! omIsAddrPageAligned(region->init_addr));
    omCheckReturnCorrupted(! (region->init_addr >= region->addr
                              && region->init_addr <= region->addr + (region->pages -1)*SIZEOF_SYSTEM_PAGE));
    omCheckReturnCorrupted(region->init_addr !=
                           region->addr + (region->pages - region->init_pages)*SIZEOF_SYSTEM_PAGE);
  }
 
  omCheckReturn(omCheckList(region->current, level, report, OM_FLR_VAL));
  omCheckReturnCorrupted(region->current == NULL && region->used_pages + region->init_pages != region->pages);
  omCheckReturnCorrupted(level > 1 &&
                         omListLength(region->current)+region->used_pages+region->init_pages != region->pages);
  return omError_NoError;
}

omCheckBinPageRegions()

omError_t omCheckBinPageRegions	(	int	level,
		omError_t	report,
		OM_FLR_DECL
	)

Definition at line 531 of file omBinPage.c.

{
  omBinPageRegion iter = om_CurrentBinPageRegion;
 
  if (level <= 0) return omError_NoError;
  if (iter == NULL) return omError_NoError;
 
  omCheckReturnError(om_CurrentBinPageRegion->next != NULL && OM_IS_EMPTY_REGION(om_CurrentBinPageRegion->next),
                     omError_InternalBug);
  omCheckReturnError(om_CurrentBinPageRegion->prev != NULL && ! OM_IS_EMPTY_REGION(om_CurrentBinPageRegion->prev),
                     omError_InternalBug);
 
 
  if (level > 1)
  {
    omBinPageRegion prev_last = (omBinPageRegion) omGListLast(om_CurrentBinPageRegion, prev);
    omBinPageRegion next_last = (omBinPageRegion) omGListLast(om_CurrentBinPageRegion, next);
 
    omCheckReturn(omCheckGList(iter, next, level, report, OM_FLR_VAL));
    omCheckReturn(omCheckGList(iter, prev, level, report, OM_FLR_VAL));
 
    omCheckReturnCorrupted(omGListLength(prev_last, next)
                          !=
                          omGListLength(next_last, prev));
 
    omCheckReturn(omCheckBinPageRegion(om_CurrentBinPageRegion, level - 1, report, OM_FLR_VAL));
 
    iter = om_CurrentBinPageRegion->next;
    while (iter)
    {
      omCheckReturnError(OM_IS_EMPTY_REGION(iter), omError_InternalBug);
 
      omCheckReturn(omCheckBinPageRegion(iter, level - 1, report, OM_FLR_VAL));
      iter = iter->next;
    }
 
    iter = om_CurrentBinPageRegion->prev;
    while (iter)
    {
      omCheckReturnError( !OM_IS_EMPTY_REGION(iter), omError_InternalBug);
      omCheckReturn(omCheckBinPageRegion(iter, level - 1, report, OM_FLR_VAL));
      iter = iter->prev;
    }
  }
  return omError_NoError;
}

omFindRegionOfAddr()

omBinPageRegion omFindRegionOfAddr

(

void *

addr

)

Definition at line 578 of file omBinPage.c.

{
  omBinPageRegion region = om_CurrentBinPageRegion;
 
  if (region == NULL) return 0;
  region = omGListLast(region, prev);
  do
  {
    if ((char *)addr >= region->addr
    && (char *)addr < region->addr + (region->pages)*SIZEOF_SYSTEM_PAGE)
      return region;
    region = region->next;
  }
  while (region != NULL);
  return NULL;
}

omFreeBinPages()

void omFreeBinPages	(	omBinPage	bin_page,
		int	how_many
	)

Definition at line 206 of file omBinPage.c.

{
  omBinPageRegion region = bin_page->region;
 
  region->used_pages -= how_many;
  if (region->used_pages == 0)
  {
    if (region == om_CurrentBinPageRegion)
    {
      if (region->next != NULL)
        om_CurrentBinPageRegion = region->next;
      else
        om_CurrentBinPageRegion = region->prev;
    }
    omTakeOutRegion(region);
    omFreeBinPagesRegion(region);
  }
  else
  {
    if (region != om_CurrentBinPageRegion && OM_IS_EMPTY_REGION(region))
    {
      omTakeOutRegion(region);
      omInsertRegionAfter(region, om_CurrentBinPageRegion);
    }
    if (how_many > 1)
    {
      int i = how_many;
      char* page = (char *)bin_page;
 
      while (i > 1)
      {
        NEXT_PAGE(page) = page + SIZEOF_SYSTEM_PAGE;
        page = NEXT_PAGE(page);
        i--;
      }
      NEXT_PAGE(page) = region->current;
    }
    else
    {
      NEXT_PAGE(bin_page) = region->current;
    }
    region->current = (void*) bin_page;
  }
  om_Info.AvailPages += how_many;
  om_Info.UsedPages -= how_many;
  OM_FREE_BINPAGE_HOOK;
}

omFreeBinPagesRegion()

static void omFreeBinPagesRegion ( omBinPageRegion  region )

static

Definition at line 330 of file omBinPage.c.

{
  omAssume(region != NULL && region->used_pages == 0);
 
  om_Info.AvailPages -= region->pages;
  om_Info.CurrentRegionsAlloc--;
 
  omUnregisterBinPages(region->addr, region->pages);
  omVfreeToSystem(region->addr, region->pages*SIZEOF_SYSTEM_PAGE);
  omFreeSizeToSystem(region, sizeof(omBinPageRegion_t));
  om_Info.InternalUsedBytesMalloc-=sizeof(omBinPageRegion_t);
}

omInsertRegionAfter()

OM_INLINE_LOCAL void omInsertRegionAfter	(	omBinPageRegion	insert,
		omBinPageRegion	after
	)

Definition at line 66 of file omBinPage.c.

{
  omAssume(insert != NULL && after != NULL && insert != after);
  insert->next = after->next;
  insert->prev = after;
  after->next = insert;
  if (insert->next != NULL)
  {
    omAssume(insert->next != insert && insert->next != after);
    insert->next->prev = insert;
  }
}

omInsertRegionBefore()

OM_INLINE_LOCAL void omInsertRegionBefore	(	omBinPageRegion	insert,
		omBinPageRegion	before
	)

Definition at line 79 of file omBinPage.c.

{
  omAssume(insert != NULL && before != NULL && insert != before);
  insert->prev = before->prev;
  insert->next = before;
  before->prev = insert;
  if (insert->prev != NULL)
    insert->prev->next = insert;
}

omIsAddrOnFreeBinPage()

int omIsAddrOnFreeBinPage

(

void *

addr

)

Definition at line 595 of file omBinPage.c.

{
  char *c_addr=(char *)addr;
  omBinPageRegion region = om_CurrentBinPageRegion;
 
  if (region == NULL) return 0;
  do
  {
    if (c_addr > region->addr && c_addr < region->addr + (region->pages)*SIZEOF_SYSTEM_PAGE)
    {
      if (omIsOnList(region->current, omGetPageOfAddr(addr))) return 1;
      return 0;
    }
    region = region->next;
  }
  while (region != NULL);
  return 0;
}

omIsKnownMemoryRegion()

int omIsKnownMemoryRegion

(

omBinPageRegion

region

)

Definition at line 489 of file omBinPage.c.

{
  omBinPageRegion iter = om_CurrentBinPageRegion;
 
  if (region == NULL || iter == NULL) return 0;
  iter = omGListLast(om_CurrentBinPageRegion, prev);
  do
  {
    if (region == iter) return 1;
    iter = iter->next;
  }
  while (iter != NULL);
  return 0;
}

omRegisterBinPages()

static void omRegisterBinPages ( void *  low_addr, int  pages  )

static

Definition at line 390 of file omBinPage.c.

{
  unsigned long low_index = omGetPageIndexOfAddr(low_addr);
  char* high_addr = (char *)low_addr + (pages-1)*SIZEOF_SYSTEM_PAGE;
  unsigned long high_index = omGetPageIndexOfAddr(high_addr);
  unsigned long shift;
 
  if (low_index < om_MinBinPageIndex || high_index > om_MaxBinPageIndex)
    omBinPageIndexFault(low_index, high_index);
 
  shift = omGetPageShiftOfAddr(low_addr);
  if (low_index < high_index)
  {
    if (shift == 0)
    {
      om_BinPageIndicies[low_index-om_MinBinPageIndex] = ULONG_MAX;
    }
    else
    {
      om_BinPageIndicies[low_index-om_MinBinPageIndex] |= ~ ((((unsigned long) 1) << shift) - 1);
    }
    for (shift = low_index+1; shift < high_index; shift++)
    {
      om_BinPageIndicies[shift-om_MinBinPageIndex] = ULONG_MAX;
    }
    shift = omGetPageShiftOfAddr(high_addr);
    if (shift == BIT_SIZEOF_LONG - 1)
    {
      om_BinPageIndicies[high_index - om_MinBinPageIndex] = ULONG_MAX;
    }
    else
    {
      om_BinPageIndicies[high_index-om_MinBinPageIndex] |= ((((unsigned long) 1) << (shift + 1)) - 1);
    }
  }
  else
  {
    high_index = omGetPageShiftOfAddr(high_addr);
    while (high_index > shift)
    {
      om_BinPageIndicies[low_index-om_MinBinPageIndex] |= (((unsigned long) 1) << high_index);
      high_index--;
    }
    om_BinPageIndicies[low_index-om_MinBinPageIndex] |= (((unsigned long) 1) << shift);
  }
}

omTakeOutConsecutivePages()

static void * omTakeOutConsecutivePages ( omBinPageRegion  region, int  how_many  )

static

Definition at line 254 of file omBinPage.c.

{
  void* current;
  char* iter;
  void* prev = NULL;
  void* bin_page;
  int found;
  current = region->current;
  while (current != NULL)
  {
    found = 1;
    iter = current;
    while (NEXT_PAGE(iter) == (iter + SIZEOF_SYSTEM_PAGE))
    {
      iter = NEXT_PAGE(iter);
      /* handle pathological case that iter + SIZEOF_SYSTEM_PAGE == 0 */
      if (iter == NULL) return NULL;
      found++;
      if (found == pages)
      {
        bin_page = current;
        if (current == region->current)
        {
          region->current = NEXT_PAGE(iter);
        }
        else
        {
          omAssume(prev != NULL);
          NEXT_PAGE(prev) = NEXT_PAGE(iter);
        }
        return bin_page;
      }
    }
    prev = iter;
    current = NEXT_PAGE(iter);
  }
  return NULL;
}

omTakeOutRegion()

OM_INLINE_LOCAL void omTakeOutRegion

(

omBinPageRegion

region

)

Definition at line 49 of file omBinPage.c.

{
  omAssume(region != NULL);
 
  if (region->prev != NULL)
  {
    omAssume(region->prev != region && region->prev != region->next);
    region->prev->next = region->next;
  }
 
  if (region->next != NULL)
  {
    omAssume(region->next != region && region->prev != region->next);
    region->next->prev = region->prev;
  }
}

omUnregisterBinPages()

static void omUnregisterBinPages ( void *  low_addr, int  pages  )

static

Definition at line 437 of file omBinPage.c.

{
  unsigned long low_index = omGetPageIndexOfAddr(low_addr);
  char* high_addr = (char *)low_addr + (pages-1)*SIZEOF_SYSTEM_PAGE;
  unsigned long high_index = omGetPageIndexOfAddr(high_addr);
  unsigned long shift;
 
  shift = omGetPageShiftOfAddr(low_addr);
  if (low_index < high_index)
  {
    if (shift == 0)
    {
      om_BinPageIndicies[low_index-om_MinBinPageIndex] = 0;
    }
    else
    {
      om_BinPageIndicies[low_index-om_MinBinPageIndex] &= ((((unsigned long) 1) << shift) - 1);
    }
    for (shift = low_index+1; shift < high_index; shift++)
    {
      om_BinPageIndicies[shift-om_MinBinPageIndex] = 0;
    }
    shift = omGetPageShiftOfAddr(high_addr);
    if (shift == BIT_SIZEOF_LONG - 1)
    {
      om_BinPageIndicies[high_index - om_MinBinPageIndex] = 0;
    }
    else
    {
      om_BinPageIndicies[high_index-om_MinBinPageIndex] &= ~ ((((unsigned long) 1) << (shift + 1)) - 1);
    }
  }
  else
  {
     high_index = omGetPageShiftOfAddr(high_addr);
     while (high_index > shift)
     {
       om_BinPageIndicies[low_index-om_MinBinPageIndex] &= ~(((unsigned long) 1) << high_index);
       high_index--;
     }
     om_BinPageIndicies[low_index-om_MinBinPageIndex] &= ~(((unsigned long) 1) << shift);
  }
}

Variable Documentation

om_BinPageIndicies

unsigned long* om_BinPageIndicies = NULL

Definition at line 38 of file omBinPage.c.

om_CurrentBinPageRegion

omBinPageRegion om_CurrentBinPageRegion = NULL

static

Definition at line 35 of file omBinPage.c.

om_MaxBinPageIndex

unsigned long om_MaxBinPageIndex = 0

Definition at line 36 of file omBinPage.c.

om_MinBinPageIndex

unsigned long om_MinBinPageIndex = ULONG_MAX

Definition at line 37 of file omBinPage.c.