Program Listing for File PageHeap.h

↰ Return to documentation for file (ADS/memory/PageHeap.h)

/*--------------------------------------------------------------------------*/
/*---------------------------- File PageHeap.h -----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_PageHeap
 #define __ADS_PageHeap
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"
#include "ADS/memory/HugePageAllocator.h"

#include <cstddef>
#include <cstdint>
#include <new>
#include <vector>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS::detail {

/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS PageHeap ------------------------------*/
/*--------------------------------------------------------------------------*/

template< std::size_t C >
class alignas( 64 ) PageHeap {

/*--------------------------------------------------------------------------*/
 public:

 static constexpr std::size_t GRAIN = 8;
 static constexpr std::size_t PAGE = std::size_t( 1 ) << 16;
 static constexpr std::size_t SEGMENT = std::size_t( 1 ) << 21;
 static constexpr std::size_t HEADER = 64;

 static_assert( C * GRAIN <= ( PAGE - HEADER ) / 8 ,
                "a page holds at least 8 slots of the largest class" );

 struct Free {
  Free * next;
  };

 struct Page {
  Free * free;
  char * next;
  char * end;
  Page * link;
  void * owner;
  std::uint32_t c;
  bool listed;
  };

 static_assert( sizeof( Page ) <= HEADER );

 explicit PageHeap( void * owner = nullptr );

 PageHeap( const PageHeap & ) = delete;
 PageHeap & operator=( const PageHeap & ) = delete;

 ~PageHeap();

 [[nodiscard]] static Page * pageOf( void * p ) {
  return( reinterpret_cast< Page * >( reinterpret_cast< std::uintptr_t >(
           p ) & ~std::uintptr_t( PAGE - 1 ) ) );
  }

 [[nodiscard]] void * local( std::size_t c ) {
  Page * const p = f_class[ c ].current;
  if( Free * const f = p->free ) [[likely]] {
   p->free = f->next;
   ++f_live;
   return( f );
   }
  if( p->next != p->end ) {                 // a slot never given
   void * const s = p->next;
   p->next += ( c + 1 ) * GRAIN;
   ++f_live;
   return( s );
   }
  return( nullptr );
  }

 [[nodiscard]] void * more( std::size_t c );

 void give( Page * g , void * p ) {
  Free * const f = static_cast< Free * >( p );
  f->next = g->free;
  g->free = f;
  --f_live;
  if( ! g->listed ) [[unlikely]] {          // back among the pages to use
   g->listed = true;
   g->link = f_class[ g->c ].avail;
   f_class[ g->c ].avail = g;
   }
  }

 [[nodiscard]] std::size_t live( void ) const { return( f_live ); }

 [[nodiscard]] std::size_t bytes( void ) const {
  return( f_segments.size() * SEGMENT );
  }

/*--------------------------------------------------------------------------*/
 private:

 struct Class {
  Page * current;
  Page * avail = nullptr;
  };

 inline static Page s_none{ nullptr , nullptr , nullptr , nullptr ,
                            nullptr , 0 , true };

 Page * fresh( std::size_t c );

 Class f_class[ C ];
 char * f_page = nullptr;
 char * f_last = nullptr;
 std::size_t f_live = 0;
 void * f_owner;
 std::vector< char * > f_segments;

 };  // end( class PageHeap )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

template< std::size_t C >
PageHeap< C >::PageHeap( void * owner ) : f_owner( owner )
{
 for( Class & k : f_class )
  k.current = &s_none;
 }

template< std::size_t C >
PageHeap< C >::~PageHeap()
{
 for( char * s : f_segments )
  HugePageAllocator< char >().deallocate( s , SEGMENT );
 }

template< std::size_t C >
typename PageHeap< C >::Page * PageHeap< C >::fresh( std::size_t c )
{
 if( f_page == f_last ) {                   // a new segment
  f_segments.reserve( f_segments.size() + 1 );
  char * s = HugePageAllocator< char >().allocate( SEGMENT );
  f_segments.push_back( s );
  f_page = s;
  f_last = s + SEGMENT;
  }
 char * const p = f_page;
 f_page += PAGE;
 const std::size_t b = ( c + 1 ) * GRAIN;
 return( ::new( static_cast< void * >( p ) ) Page{ nullptr , p + HEADER ,
          p + HEADER + ( ( PAGE - HEADER ) / b ) * b , nullptr , f_owner ,
          std::uint32_t( c ) , true } );
 }

template< std::size_t C >
void * PageHeap< C >::more( std::size_t c )
{
 Class & k = f_class[ c ];
 for( ; ; ) {
  Page * const p = k.current;
  if( Free * f = p->free ) {
   p->free = f->next;
   ++f_live;
   return( f );
   }
  if( p->next != p->end ) {                 // a slot never given
   void * s = p->next;
   p->next += ( c + 1 ) * GRAIN;
   ++f_live;
   return( s );
   }
  if( p != &s_none )                        // exhausted: off the list
   p->listed = false;
  if( Page * q = k.avail ) {
   k.avail = q->link;
   k.current = q;
   }
  else
   k.current = fresh( c );
  }
 }

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS::detail )

/*--------------------------------------------------------------------------*/

#endif  /* PageHeap.h included */

/*--------------------------------------------------------------------------*/
/*---------------------------- End File PageHeap.h -------------------------*/
/*--------------------------------------------------------------------------*/