Skip to content

Instantly share code, notes, and snippets.

@Memresable

Memresable/win32_page_merging.md

Last active January 8, 2024 12:42
Show Gist options
  • Save Memresable/be472be9e817ac0773f829fd890e0f9f to your computer and use it in GitHub Desktop.
Save Memresable/be472be9e817ac0773f829fd890e0f9f to your computer and use it in GitHub Desktop.
Download ZIP
Combining Memory Pages in Windows
Raw
win32_page_merging.md

NOTE: I've realized that this is overly written, it could be significantly simplified by now but i've moved to linux for now, will refactor this when i get back to windows, it also contains a shit load of errors so be aware of that and use docs!!!

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

So lately i've been playing around the idea of merging pages together to be a single linear writable memory, I've searched through the web a lot and i've never seen anyone actually doing it in a way i did, the reason behind researching around this topic was i was curious, but also it seemed useful to just merge stuff together and eliminate memory fragmentation by merging multiple chunks together to form one contigues memory you can write to

the idea seemed "extreme" and "terrible to apply" to some when i asked this, but tbh, maybe it's not that bad (maybe... dunno about the page caches and faults that could worsen the performance significantly, and i don't know much about these underlying systems and how they work as much as i should)

what i basically need to do is create a file mapping object that is multiple of 64KB pages of total size, each file map created is an object returned by the OS that is a "file" but can be treated as a regular memory that can be written to as well, then i allocate a virtual memory that is "reserved" to be replaced by mapping one of the objects to that virtual memory using VirtualAlloc2, and with that i can just call MapViewOfFile3 function to map one of the file objects addresses to the virtual memory by offsets (depending on how many object to map) and tada!

it works suprisangly well and really simple to do, but the big problem is that it requires us to track these objects manually and make sure everything gets flushed and unmapped later which is a tedious task

and it can also lead to large waste of memory if smaller buffers were written to and that requires a workaround to deal with this problem which is putting the buffers in a one single linear buffer, but that also means you can't "free" those buffers one by one because they are sharing the same memory/chunks together, so it may seem beneficial mostly to larger buffers only

the example i took from to do this page merging trick is from MSDN's VirtualAlloc2 Scenario 1: https://learn.microsoft.com/en-us/windows/win32/api/memoryapi/nf-memoryapi-virtualalloc2

it was about ring buffers in general, but it contained useful info there that led me to here

i'm just thinking someone could think of a good use of this memory merging method because i have no clue what this can be used for in a good way, which is part of the reason why i made this article in the first place

the following example is just trying to manage resources in a group, each group doesn't create more than given chunks though and i could've easily done that but too lazy to continue making this now, maybe later

EDIT: also sorry for the horrible example, it's waay to dense to show the point

// TODO(Memresable): deal with parallel resource loading
// TODO(Memresable): figure out how to cache resources

struct chunk
{
  bool IsUsed;

  struct chunk* Previous;
  struct chunk* Next;

  void* Memory;
  usize GroupOffset;
};

struct chunk
CreateChunk(usize Size, usize BlockOffset)
{
  struct chunk Chunk = {};
  Chunk.IsUsed = true;
  Chunk.Memory = CreateFileMapping(INVALID_HANDLE_VALUE, nullptr, PAGE_READWRITE, 0, Size, nullptr);
  Chunk.GroupOffset = BlockOffset;
  return(Chunk);
}

void
FreeChunk(struct chunk* Chunk)
{
  CloseHandle(Chunk->Memory);
  DWORD ErrorCode = GetLastError();
  assert(ErrorCode == 0);
  MemoryZeroStruct(Chunk);
}

struct block
{
  struct chunk* Chunks;
  usize ChunkCount;
};

enum resource_type
{
  Resource_Type_Null = 0,
  Resource_Type_Image = 1,
};

struct resource
{
  usize Hash;
  usize IsUsed;

  struct resource* Previous;
  struct resource* Next;

  enum resource_type Type;
  struct group* GroupPtr;
  struct chunk* ChunkList;
  usize PerChunkSize;
  void* Memory;
  usize Size;
};

struct group
{
  usize Hash;
  bool IsUsed;

  struct block* Blocks;
  usize BlockCount;
  usize PerChunkSize;
  usize MemoryLimit;

  struct resource* Resources; // NOTE(Memresable): Hash table
  u16 ResourceCount;
  u16 ResourcesInUseCount;
};

constexpr u16 MaxGroupCount = 1024;
struct group Groups[MaxGroupCount] = {};
usize GroupCount = 0;

struct group
InitializeGroup(
  usize Hash,
  usize ResourceCount,
  usize DefaultBlockCount,
  usize DefaultChunkCount, usize PerChunkSize,
  usize MemoryLimit)
{
  struct group Result = {};
  Result.Hash = Hash;
  Result.IsUsed = true;

  Result.Resources = new struct resource[ResourceCount]{};
  Result.ResourceCount = ResourceCount;

  Result.Blocks = new struct block[DefaultBlockCount]{};
  Result.BlockCount = DefaultBlockCount;
  for(usize BlockIdx = 0; BlockIdx < DefaultBlockCount; BlockIdx++)
  {
    struct block* Block = Result.Blocks + BlockIdx;
    Block->ChunkCount = DefaultChunkCount;
    Block->Chunks = new struct chunk[DefaultChunkCount]{};
  }

  Result.PerChunkSize = PerChunkSize;
  Result.MemoryLimit = MemoryLimit;
  return(Result);
}

struct group*
CreateGroup(
  str Name,
  usize ResourceCount,
  usize DefaultBlockCount,
  usize DefaultChunkCount, usize PerChunkSize,
  usize MemoryLimit)
{
  assert((DefaultChunkCount % 2) == 0);
  assert((PerChunkSize % KBSIZE(64)) == 0);

  usize Hash = StrHash(Name, 0);
  struct group* Group = Groups + (Hash % MaxGroupCount);
  if((Group->IsUsed) && (Group->Hash != Hash))
  {
    for(usize GroupIdx = 1; GroupIdx < MaxGroupCount; GroupIdx++)
    {
      Hash = StrHash(Name, GroupIdx);
      Group = Groups + (Hash % MaxGroupCount);
      if(Group->Hash == Hash)
      {
        return(Group);
      }
      else if(Group->IsUsed == false)
      {
        *Group = InitializeGroup(Hash, ResourceCount, DefaultBlockCount, DefaultChunkCount, PerChunkSize, MemoryLimit);
        GroupCount++;
        return(Group);
      }
    }
  }
  else if(Group->IsUsed == false)
  {
    *Group = InitializeGroup(Hash, ResourceCount, DefaultBlockCount, DefaultChunkCount, PerChunkSize, MemoryLimit);
    GroupCount++;
    return(Group);
  }
  else
  {
    return(Group);
  }
  return(nullptr);
}

struct group*
GetGroup(str Name)
{
  usize Hash = StrHash(Name, 0);
  struct group* Group = Groups + (Hash % MaxGroupCount);
  if(Group->Hash != Hash)
  {
    for(usize GroupIdx = 1; GroupIdx < MaxGroupCount; GroupIdx++)
    {
      Hash = StrHash(Name, GroupIdx);
      Group = Groups + (Hash % MaxGroupCount);
      if(Group->Hash != Hash) continue;
      else return(Group);
    }
  }
  else
  {
    return(Group);
  }
  return(nullptr);
}

// win32 interrupting here
#undef LoadImage

u8*
LoadImage(struct group* Group, str Name, str FilePath)
{
  assert(Group->ResourcesInUseCount < Group->ResourceCount);

  i32 Width, Height, NRChannels;
  u8* Image = stbi_load(FilePath, &Width, &Height, &NRChannels, 0);
  usize ImageMemorySize = ((Width*Height)*NRChannels);
  if(Image)
  {
    Group->ResourcesInUseCount++;

    usize Hash = StrHash(Name, 0);
    struct resource* Resource = Group->Resources + (Hash % Group->ResourceCount);
    if(Resource->Hash != Hash)
    {
      for(usize ResourceIdx = 1; ResourceIdx < Group->ResourceCount; ResourceIdx++)
      {
        Hash = StrHash(Name, ResourceIdx);
        Resource = Group->Resources + (Hash % Group->ResourceCount);
        if(Resource->IsUsed == false)
        {
          Resource->Hash = Hash;
          Resource->IsUsed = true;
          break;
        }
      }
    }
    else if(Resource->IsUsed == false)
    {
      Resource->Hash = Hash;
      Resource->IsUsed = true;
    }

    assert(Resource->Hash == Hash);

    Resource->Type = resource_type::Resource_Type_Image;
    Resource->Size = ImageMemorySize;
    Resource->PerChunkSize = Group->PerChunkSize;
    Resource->GroupPtr = Group;

    usize ChunksToWrite = ((usize)(ImageMemorySize / Group->PerChunkSize)) + 1; // FIXME(Memresable): hack
    void* Memory = VirtualAlloc2(nullptr, nullptr,
                                 (ChunksToWrite + 1) * Group->PerChunkSize,
                                 MEM_RESERVE | MEM_RESERVE_PLACEHOLDER,
                                 PAGE_NOACCESS, nullptr, 0);
    Resource->Memory = Memory;
    if(ChunksToWrite == 1)
    {
      for(usize BlockIdx = 0; BlockIdx < Group->BlockCount; BlockIdx++)
      {
        struct block* Block = Group->Blocks + BlockIdx;
        for(usize ChunkIdx = 0; ChunkIdx < Block->ChunkCount; ChunkIdx++)
        {
          struct chunk* Chunk = Block->Chunks + ChunkIdx;
          if(Block->Chunks[ChunkIdx].IsUsed == false)
          {
            *Chunk = CreateChunk(Group->PerChunkSize, ChunkIdx * Group->PerChunkSize);
            Resource->ChunkList = Chunk;
            goto ChunkFound;
          }
        }
      }
    }
    else
    {
      struct chunk** ChunkPtrs = (struct chunk**)alloca(ChunksToWrite * sizeof(void*));
      MemoryZeroStructArray(ChunkPtrs, ChunksToWrite);
      usize ChunkPtrsIdx = 0;
      for(usize BlockIdx = 0; BlockIdx < Group->BlockCount; BlockIdx++)
      {
        struct block* Block = Group->Blocks + BlockIdx;
        for(usize ChunkIdx = 1; ChunkIdx < Block->ChunkCount; ChunkIdx++)
        {
          struct chunk* Chunk = Block->Chunks + ChunkIdx;
          if(ChunkPtrs[0] == nullptr)
          {
            ChunkPtrs[0] = Chunk;
            ChunkPtrsIdx++;
            continue;
          }
          if(ChunkPtrsIdx == ChunksToWrite) goto ChunksFilled;
          if(Chunk->IsUsed == false)
          {
            *Chunk = CreateChunk(Group->PerChunkSize, ChunkIdx * Group->PerChunkSize);
            if(ChunkPtrs[ChunkPtrsIdx - 1]) ChunkPtrs[ChunkPtrsIdx - 1]->Next = Chunk;
            Chunk->Previous = ChunkPtrs[ChunkPtrsIdx - 1];
            ChunkPtrs[ChunkPtrsIdx++] = Chunk;
          }
        }
      }
ChunksFilled:
      Resource->ChunkList = ChunkPtrs[0]; // NOTE(Memresable): copy the first chunk pointer off of the list
    }
ChunkFound:
    struct chunk* CurrentChunk = Resource->ChunkList;
    for(usize ChunkIdx = 0; ChunkIdx < ChunksToWrite; ChunkIdx++)
    {
      void* MemOffset = (void*)((u8*)Memory + (ChunkIdx * Group->PerChunkSize));
      VirtualFree(MemOffset, Group->PerChunkSize, MEM_RELEASE | MEM_PRESERVE_PLACEHOLDER);
      {
        MapViewOfFile3(CurrentChunk->Memory, nullptr, MemOffset, 0, Group->PerChunkSize, MEM_REPLACE_PLACEHOLDER, PAGE_READWRITE, nullptr, 0);
      }
      CurrentChunk->IsUsed = true;
      CurrentChunk = CurrentChunk->Next;
      DWORD ErrorCode = GetLastError();
      assert(ErrorCode == 0);
    }
    MemoryCopy(Memory, Image, (Width*Height)*NRChannels);
    stbi_image_free(Image);
    return((u8*)Memory);
  }
  return(nullptr);
}

struct resource*
GetResource(struct group* Group, str Name)
{
  usize Hash = StrHash(Name, 0);
  struct resource* Resource = Group->Resources + (Hash % Group->ResourceCount);
  if(Resource->Hash != Hash)
  {
    for(usize ResourceIdx = 1; ResourceIdx < Group->ResourceCount; ResourceIdx++)
    {
      Hash = StrHash(Name, ResourceIdx);
      Resource = Group->Resources + (Hash % Group->ResourceCount);
      if(Resource->Hash != Hash) continue;
      else return(Resource);
    }
  }
  else
  {
    return(Resource);
  }
  return(nullptr);
}

void
FreeResource(struct resource* Resource)
{
  struct chunk* Chunk = Resource->ChunkList;
  usize ChunkIdx = 0;
  while(Chunk)
  {
    void* MemOffset = (void*)((u8*)Resource->Memory + ((ChunkIdx++) * Resource->PerChunkSize));
    FlushViewOfFile(MemOffset, Resource->PerChunkSize);
    UnmapViewOfFile(MemOffset);
    FreeChunk(Chunk);
    Chunk = Chunk->Next;
  }
  Resource->GroupPtr->ResourcesInUseCount--;
  MemoryZeroStruct(Resource);
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Examples

/*
* TODO(Memresable): we can use sort of a binding system, and just bind whatever group we have
* and then continue allocating resourecs from there with such bound group in the manager
* it's a global state anyways so we can take advantage of that
*/
struct group* Group = CreateGroup("SomeGroup", 10, 4, 16, KBSIZE(128), MBSIZE(32));

u8* First = LoadImage(Group, "UI_Font", "../memreclub_resources/textures/bitmap_font.bmp");
u8* SecondImage = LoadImage(Group, "Nuh uh", "../memreclub_resources/textures/bitmap_font.bmp");
u8* A = (u8*)GetResource(Group, "UI_Font")->Memory;
u8* B = (u8*)GetResource(Group, "Nuh uh")->Memory;
FreeResource(GetResource(Group, "UI_Font"));
FreeResource(GetResource(Group, "Nuh uh"));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment